Computing Functions of a Shared Secret.
In this work we introduce and study threshold (t-out-of-n) secret sharing schemes  for families of functions ${\cal F}$. Such schemes allow any set of at least t parties to compute privately the value f(s) of a (previously distributed) secret s, for any $f\in {\cal F}$. Smaller sets of players get no more information about the secret than what follows from the value f(s). The goal is to make the shares as short as possible. Results are obtained for two different settings:  we study the case when the evaluation is done on a  broadcast channel  without interaction,  and we examine what can be gained by allowing evaluations to be done  interactively via private channels.
Introduction
. Suppose, for example, that we are interested in sharing a
secret le among n parties in a way that will later allow any t of the parties to test
whether a particular string (not known in the sharing stage) appears in this le.
This test should be done without revealing the content of the whole le, or giving
any other information about the le. This problem can be viewed as an extension
of the traditional denition of threshold (t-out-of-n) secret sharing schemes. In the
traditional denition, sets of at least t parties are allowed to reconstruct a (previously
distributed) secret s, while any smaller set gets no information about the secret. We
introduce a more general denition of t-out-of-n secret sharing schemes for a family
of functions F . These schemes allow authorized sets of parties to compute some
information about the secret and not necessarily the secret itself. More precisely, sets
B of size at least t can evaluate f(s) for any function f 2 F ; any set C of size less
than t knows nothing (in the information theoretic sense) about the secret prior to
the evaluation of the function; and, in addition, after f(s) is computed by a set B no
set C of size less than t knows anything more about the secret s than what follows
from f(s). In other words, the parties in C might know the value f(s), but they know
nothing more than that, although they might have heard part of the communication
during the evaluation of f(s).
Clearly, if we consider a family F that includes only the identity function
then we get the traditional notion of secret sharing schemes. These schemes, which
were introduced by Blakley [8] and Shamir [34], were the subject of a considerable
amount of work (e.g., [30, 26, 28, 6, 35, 20]). They were used in many applications
(e.g., [31, 5, 15, 19]) and were generalized in various ways [22, 7, 36]. Surveys are given
in [35, 37]. The question of sharing many secrets simultaneously was considered (with
some dierences in the denitions) by several researchers [30, 26, 21, 11, 23, 10, 24].
Simultaneous sharing of many secrets is also a special case of our setting. 1 Other
Dept. of Mathematics and Computer Science, Ben-Gurion University, Beer Sheva 84105, Israel.
E-mail: beimel@cs.bgu.ac.il. http://www.cs.bgu.ac.il/beimel . This work was done when the
author was a Ph.D. student in the Dept. of Computer Science, Technion.
y Dept. of Mathematics, Royal Holloway { University of London, Egham, Surrey TW20 OEX,
U.K. E-mail: m.burmester@rhbnc.ac.uk.
z Dept. of Computer Science, PO Box 4530, 206 Love Building, Florida State University, Talla-
hassee, FL 32306-4530, USA. E-mail: desmedt@cs.fsu.edu.
x Dept. of Computer Science, Technion, Haifa 32000, Israel. E-mail: eyalk@cs.technion.ac.il.
http://www.cs.technion.ac.il/eyalk .
be the secrets we want to share simultaneously. Construct the concatenated
and the functions which can be evaluated are the functions f
similar scenarios in which sharing is viewed as a form of encryption and the security
is computationally bounded have been considered in [32, 3, 1].
Threshold cryptography [19, 18, 17] is also a special case of secret sharing for a
family of functions. 2 A typical scenario of threshold cryptography is the following:
Every set B of t parties should be able to sign any document such that any coalition
C of less than t parties cannot sign any other document (even if the coalition C knows
signatures of some documents). To achieve this goal the key is shared in such a way
that every t parties can generate a signature from their shares without revealing any
information on the key except the signature. Specically, assume we have a signature
is the domain of messages, K is the domain
of keys, and O is the domain of signatures. For every
k). The previous scenario is simply sharing the key for the family
Mg. These examples show that secret sharing for a family of functions is
a natural primitive.
Obviously one possible solution to the problem of sharing a secret for a family F
is by sharing separately each of the values f(s) (for any f 2 F) using known threshold
schemes. While this solution is valid, it is very ine-cient, in particular when the size
of F is large. Therefore, an important goal is to realize such schemes while using
\small" shares. For example, to share a single bit among n parties, the average (over
the parties) length of shares is at least log(n t
log n bits are su-cient [34]. The obvious solution for sharing ' bits simultaneously
will require ' log n bits. By [26], it can be shown that shares of at least ' bits are
necessary. We shall show that '-bit shares are also su-cient if interactive evaluation
on private channels is allowed, and O(')-bit shares are su-cient if non-interactive
evaluation (on a broadcast channel) is used. 3
We present an interactive scheme in which '-bit secrets are distributed using '-bit
shares; this scheme allows the computation of every linear combination of the bits
(and not only computation of the bits themselves). We use this scheme to construct
schemes for other families of functions. The length of the shares in these schemes can
be much longer than the length of the secret. An interesting family of functions that
we shall consider is the family ALL of all functions of the secret. For this family, we
construct a scheme in which the length of the shares is  2 ' log n (where ' is the length
of the secret and 2 ' is the length of the description of a function which is evaluated).
In this scheme the computation requires no interaction and can be held on a broadcast
channel. If we allow interaction on private channels during the computation, then the
length of the shares can be reduced to 2 ' . Note that the obvious solution of sharing
each bit separately requires in this case 2 2 '
bits.
Our work deals mainly with two models: the private channels model in which the
computation might require a few rounds of communication; and the broadcast channel
model in which the computation is non-interactive. On one hand, the broadcast model
does not require secure private channels and synchronization; hence, the computation
is more e-cient. On the other hand, in the private channels model, a coalition C that
does not intersect the evaluating set B will know nothing about s; not even the value
f(s). Interaction seems to be useful in the computation. It enables us to reduce the
The secrets s i may be dependent: our model allows some information to leak provided it is no more
than what follows from the evaluations of f(s).
2 The functions considered in [19, 18, 17] are, however, very limited and the scenario in [17] is
restricted to computational security.
3 In fact, both results require ' to be \su-ciently large": '  log n in the interactive case and
'  log n log log n in the broadcast model.
length of the shares by a factor of log n in our basic scheme for linear functions.
We also study ideal threshold schemes. These are schemes in which the size of
the shares equals the size of the secrets 4 (see, e.g., [12, 13, 4, 33, 25]). We deal with
the characterization of the families of functions F which can be evaluated by an ideal
threshold scheme. For the interactive private channel model, we prove that every
boolean function that can be evaluated is a linear function. For the broadcast model,
we prove that F cannot contain any boolean function (for every family that contains
the identity function).
An example. To motivate our approach and to clarify the notion of secret sharing
for a family of functions we consider a simple example, which we discuss informally.
Suppose that a dealer shares a secret s among n parties and that at some time later
a set of at least t parties would like to answer the question: \Is the shared secret
equal to the string a?" That is, they want to evaluate the boolean function f a
which is 1 if and only if a. The string a is not known when the dealer shares
the secret. We describe a simple scheme which makes it possible for the parties to
answer such questions. Let be the secret bit-string. The dealer chooses
random strings from f0; 1g 2' , denoted by b shares each of these
strings using Shamir's t-out-of-n threshold scheme [34]. Let b i;j be the share of the
secret b i given to party P j . The dealer computes the sum (i.e., bitwise exclusive-or)
(that is s i , the value of the i-th bit of the secret, selects whether we
take b 2i or b 2i+1 ) and gives  to each party. When a subset B of (at least) t parties
wants to check if s = a for some a = a 1 a computes a \new"
share
Then, the parties in B apply Shamir's secret reconstruction
procedure to compute a \new" secret from these \new" shares. Since this procedure
involves only computing a linear combination of the shares, the \new" secret is simply
. If the \new" secret diers from
then the parties learn that
s 6= a. However, they get no more information on the secret s. If the \new" secret is
equal to
then it is easy to see that with high probability (over the choice
of must have a. In this case, the parties learn the secret and there
is no additional information which should be hidden from them. Observe that in both
cases the parties learn no more than what is revealed by answering the question.
Connection to private computations. In our schemes we require that authorized
sets of parties can compute a function of the secret without leaking any other information
on the secret. This resembles the requirement of (n; k)-private protocols [5, 15]
in which the set of all n parties can evaluate a function of their inputs in a way that
no set of less than k parties will gain any additional information about the inputs of
the other parties. Indeed, in some of our schemes a set B of size t uses a (t; t)-private
protocol. However, it is not necessary to use private protocols in the computation,
since the parties are allowed to leak information about their inputs (the shares) as
long as they do not leak any additional information on the secret. Moreover, using
private protocols does not solve the problem of e-ciently sharing a secret for all func-
tions, since not all functions can be computed (t; t) privately [5, 16]. Furthermore, the
parties cannot use the (t; b(t 1)=2c)-private protocols of [5] or [15] since this means
that coalitions of size greater than t=2 (but still smaller than t) gain information.
Organization. The rest of this paper is organized as follows. In Section 2 we discuss
our model for secret sharing for families of functions and provide the denitions;
denitions which are more delicate than in the case of traditional threshold schemes.
4 The size of each share is always at least the size of the secret [26].
In Section 3 we present interactive and broadcast secret sharing schemes for the family
LIN of linear functions. In Section 4 we use these schemes to construct schemes for
other families. In Section 5 we describe the broadcast scheme for the bit functions
BIT . In Section 6 we characterize ideal schemes in the various models. Finally, in
Section 7 we discuss possible extensions of our work. For completeness we give some
background results in Appendices.
2. Denitions. This section contains a formal denition of secret sharing for a
family of functions. We start by dening the model. We consider a system with n
parties g. In addition to the parties, there is a dealer who has a
secret input s. A distribution scheme is a probabilistic mapping, which the dealer
applies to the secret to generate n pieces of information s are referred
to as the shares . The dealer gives the share s i to party P i . Formally,
Definition 2.1 (Distribution Schemes). Let S be a set of secrets,
sets of shares, and R a set of random inputs. Let  be a probability
distribution on R. A distribution scheme  over S is a mapping
. The i-th coordinate s i of (s; r) is the share of P i . The pair
(; ) can be thought of as a dealer who shares a secret s 2 S by choosing at random
r 2 R (according to the distribution ) and then gives each party P i as a share the
corresponding component of (s; r).
In the scenario we consider, the dealer is only active during the initialization
of the system. After this stage the parties can communicate. We next dene our
communication models.
Definition 2.2 (Communication Models). We consider two models of communication

1. The private channels model in which the parties communicate via a complete
synchronous network of secure and reliable point-to-point communication
channels. In this model a set of parties has access only to the messages
sent to the parties in the set.
2. The broadcast channel model in which the parties communicate via a (public)
broadcast channel. In this model a set of parties can obtain all the messages
exchanged by the communicating parties.
A subset of the parties may communicate in order to compute a function of their
shares. We now dene how they evaluate this function.
Definition 2.3 (Function Evaluation). A set of parties B  U executes a
protocol FB;f to evaluate a function f .
At the beginning of the execution, each party P i in B has an input s i and chooses
a random input r i . To evaluate f , the parties in B exchange messages as prescribed
by the protocol FB;f . In each round every party in B sends messages to every other
party in B. A message sent by P i is determined by s i , r i , the messages received by
and the identity of the receiver. We say that a protocol FB;f evaluates f
(or computes f(s)) if each party in B can always evaluate f(s) from its input and the
communication it obtained.
We denote by MC (hs the messages that an eavesdropping coalition C
can obtain during the communication between the parties in B (this depends on the
communication model). Here hs is the vector of shares of B and hr i i B the vector
of random inputs of B.
A protocol is non-interactive if the messages sent by each party P i depend only on
its input (and not on the messages received during the execution of the protocol). Non-interactive
protocols have only one-round of communication. An interactive protocol
might have more than one round. In this case we require that the protocol terminates
after a nite number of rounds (that is, we do not allow innite runs).
The parties in the system are honest, that is, they send messages according to the
protocol.
A coalition C which eavesdrops on the execution of a protocol FB;f by the parties
in B gains no additional information on the secret s if any information that C may
get is independent of the old information. In our model we shall allow C to gain some
information, but no more than what follows from the evaluation of f . The information
that C gains is determined by the view of C.
Definition 2.4 (The View of a Coalition). Let C  U be a coalition. The view
of C, denoted VIEWC , after the execution of a protocol consists of the information
that C gains. In a distribution scheme the shares of C. In the
evaluation of f(s) by a set of parties B  U the view of C consists of: the inputs
the local random inputs hr i i C\B (only the parties in C \ B are involved in
the computation), and the messages that C obtains from the communication channel
during the evaluation by B, i.e., MB\C (hs That is,
We now dene t-out-of-n secret sharing schemes for a family of functions F .
Such schemes allow any set B of at least t parties to evaluate f(s), for any f 2 F ,
where s is a previously distributed secret, while any set C of less than t parties gains
no more information about the secret than the information inferred from f(s). We
distinguish between three types of schemes depending on the way that the value f(s)
is computed by B and the channels used: (1) interactive private channels schemes
{ where the parties in B engage in a protocol via private channels which computes
non-interactive private channels schemes { where the parties in B engage
in a non-interactive protocol via private channels to compute f(s); and (3) broadcast
non-interactive schemes { where each party in B broadcasts a single message (which
depends only on its share) on a broadcast channel (we do not consider interactive
broadcast schemes in this paper).
The computation of f(s) must be secure. There are two requirements to consider:
(1) the usual requirement for threshold schemes, that is, before the evaluation any set
C of size less than t knows nothing about the secret by viewing their shares; (2) after
the evaluation of f(s) by a set B, any set C of size less than t gains no information
about s that is not implied by f(s). Formally,
Definition 2.5 (Secret Sharing Schemes for a Family). A t-out-of-n secret
sharing scheme for a family of functions F is a distribution scheme (; ) which
satises the following two conditions:
Evaluation. For any set B  U of size at least t and any function f 2 F the parties
in B can evaluate f(s). That is, there is a protocol FB;f which given
the shares of B as inputs will always output the correct value of f(s). The
scheme is called non-interactive if FB;f is non-interactive, and interactive
otherwise. Depending on the communication model, a broadcast channel or
private channels are used.
Security. Let X be a random variable on the set of secrets S and C  U be any
coalition of size less than t.
Prior to evaluation (after the distribution of shares).
For any two secrets s; s 0 2 S and any shares hs i i C (from (s; r)):
After evaluation. For any f 2 F , any B  U of size at least t, any secrets
s; shares hs i i C , any inputs hr i i B\C , and
any messages MB\C (hs from the computation of f(s) by B:
We say that C gains no information that is not implied by the function f
(or simply: gains no additional information) if in the computation of f(s) we
have security after evaluation.
A (traditional) t-out-of-n secret sharing scheme is a secret sharing scheme for the
family that includes only the identity function explained in Observation
2.1 below, the family also contains all renamings of the identity function.)
Remark 2.1. We only require that one function f 2 F can be evaluated securely.
A more desirable property is that the scheme is reusable: any number of functions
can be evaluated securely (possibly by dierent sets). All our schemes, except for the
scheme in Section 5, are reusable.
Remark 2.2. In Denition 2.5 we required that all coalitions C of size less than t
should gain no additional information on the secret. Clearly, it is su-cient to require
this only for coalitions C of size t 1, since any smaller coalition has less information
on the secret, and, hence, will gain no additional information. 5
Remark 2.3. The security in Denition 2.5 is based on the requirement that
the view of a coalition is the same for secrets which have the same evaluation. Alternatively
we could require:
That is, the probability that the secret is s, given the view of the coalition C, equals
the probability of s, given the value In Appendix A we show that the two
denitions are equivalent (see [14] for the analogue claim with respect to traditional
secret sharing schemes).
Obviously any broadcast scheme can be transformed into a scheme in which each
message is sent on private channels. On the other hand, if we take a non-interactive
private channels scheme and broadcast the messages then the security of the computation
may be violated.
A function f 0 is a renaming of f if
Suppose that f 0 is a renaming of f and that f can be evaluated securely, then f 0 can
also be evaluated securely. Indeed, to evaluate f 0 securely we rst evaluate f(s)
securely; after this evaluation s might not be known. Nevertheless, we can nd an
input y such that
Observation 2.1. A secret sharing scheme enables the secure evaluation of a
renaming of f if and only if it enables the secure evaluation of f .
Therefore, we ignore renamings of functions.
We next dene certain classes of functions over which are of particular
interest. Recall the structure of GF(2 ' ). Each element a 2 GF(2 ' ) is an '-bit string
a which may be represented by the polynomial a ' 1 x
Addition and multiplication are as for polynomials, using the structure of GF(2) for
5 This is dierent than what happens in private multi-party computation; there a smaller set has
less inputs and hence expected to learn even less.
the coe-cients and reducing products modulo a polynomial p(x) of degree ', which
is irreducible over GF(2). A function
for every linear function f . Thus,
Observation 2.2. For every linear function f , for every x 2 GF(2 ' ), and for
every a 2 GF(2) it holds that
Notice that we do not require that the
family LIN ' to be the family of all linear functions of
is the family of additive functions). Let e be the function that
returns the i-th bit of x. Then, e i linear. We call
the family fe the bit functions and denote it by BIT ' . We also consider the
family ALL ' of all possible functions of the secret (by Observation 2.1, without loss
of generality, the range of the functions in ALL ' is in GF(2 ' )). We stress that BIT '
contains only boolean functions while both ALL ' and LIN ' contain non-boolean
functions as well.
We will need the following claim concerning linear functions.
2.1. For every linear functions, there are constants c ' such that
string
Proof. Notice that b 1
. Thus, since f is linear, and by
Observation 2.2,
and the claim follows.
3. Schemes for the Linear Functions.
3.1. An Interactive Scheme. In this section we show that Shamir's scheme
over (described in Appendix B) is also a secret sharing scheme for the
family LIN ' { the family of linear functions.
Theorem 3.1 (Basic Interactive Scheme). For every '  1 there exists an
interactive private channels t-out-of-n secret sharing scheme for the family LIN ' in
which the secrets have length ' and the shares have length ' 0 1)eg.
Proof. The dealer uses Shamir's t-out-of-n scheme over GF(2 ' 0
to distribute the
shares. We show how every function f 2 LIN ' can be evaluated securely. Consider a
set B of t 0  t parties with shares hs
that wishes to compute
f(s). By the reconstruction procedure of Shamir's scheme, for each P
exist coe-cients - j such that
simply the
sum of the x j 's. Computing this sum is done using the following interactive protocol
of Benaloh [6] (for a more detailed description of this protocol see Appendix C).
For convenience of notation, we assume that g. In the rst step
of the protocol each party P
sends r i;j to P j 2 B. Then, each party
sends y j to P 1 . Party P 1 now computes
and sends it to all the other parties. By the choice of r i;t 0 , the sum
thus, each party in B computes f(s) correctly.
Let us now prove the security of this scheme. The security prior to evaluation
follows from the security of Shamir's threshold scheme. For the security after the
evaluation it is su-cient to consider a coalition C of size t 1 (by Remark 2.2). Since
each x j is computed locally, and since f(s) is computed using a private protocol [6] (for
a formal denition of privacy see Appendix C), the parties in C gain no information
about the shares of the other parties that is not implied by f(s). That is, for any shares
we have:
(1)
Now for a secret s and shares hs i i C with there are unique shares hs i i BnC
of Shamir's scheme that are consistent with s and hs i i C . Therefore,
(2)
The last equation holds because the shares hs determine the secret s. By Equation
(1), the probability Pr[ hr is independent of
therefore of s, and by the properties of Shamir's scheme the probability
is independent of hs Therefore, by (2), for every s 0 2 S such
that
Pr[view
and the coalition C gains no information about s that is not implied by f(s).
Remark 3.1. In the special cases when
interaction by simply sending the messages x j . For the messages
must be sent via private channels. In this case, only coalitions C  B can get
messages of the evaluating set B. Let g. Then, party P i gains
no additional information from the message x j of P j , because P i knows
and its input x i , and therefore can compute x j . For the messages may be sent
via a public broadcast channel. In this case, any coalition C is a subset of B, and
if C has size n 1 then gains no additional
information from x j , since C can compute x j from f(s) and
Remark 3.2. When 3  t  n 1, the parties evaluate f(s) using an interactive
private channels scheme. It can be shown that for this particular scheme interactive
evaluation is essential. Otherwise, some coalitions C that intersect the evaluating set
B, but are not contained in B, will gain additional information on s when they obtain
the values of x j .
This scheme has the advantage that it is reusable { sets
coalition C does not gain any information on the
secret beside the values f i (s) for every i with C \ B i 6= ;. This is because the
evaluation is done using a private protocol. The private computation assures that C
cannot distinguish between two vectors of shares with the same value f i (s). Hence,
even if C knows some evaluations f i (s), an evaluation of another function will not
reveal extra information.
3.2. A Non-interactive Broadcast Scheme. Next, we present a broadcast
scheme for the family LIN ' of linear functions, in which the length of the shares is
Theorem 3.2 (Basic Broadcast Scheme). For every '  1 there exists a non-interactive
broadcast t-out-of-n secret sharing scheme for the family LIN ' in which
the secrets have length ' and the shares have length ' log
Proof. Let q 1)e. The dealer shares each bit of the secret independently
using Shamir's scheme over GF(2 q ) (this is the smallest possible eld of characteristic
two for Shamir's scheme). Let ' be the secret bit-string and let s i;j 2
be the share of b j given to party P i . Then, the total length of the share of
each party is '
Clearly, every bit of the secret can be securely reconstructed. To evaluate other
linear functions of the secret, we use the homomorphic property of Shamir's scheme,
as observed by Benaloh [6], which enables the evaluation of linear combinations of
a shared secret without revealing other information on the secret. To explain how
this property is used we rst observe that it is su-cient to show the result for a
boolean linear function, since each coordinate of f(s), where f 2 LIN ' , is also a
linear function (we use the property that this scheme is reusable).
Let f be a boolean linear function and let B be a set of (at least) t parties
with shares hs i;j i P i 2B;1j' that wishes to compute the bit f(s). By Claim 2.1,
there are constants c
. Recall that for
Shamir's reconstruction procedure the secret bit b j is computed as b
are appropriate coe-cients. Let x
i;j be a \new" share
of P i . Then,
To evaluate f(s) each party P computes locally the \new" share x i and then
broadcasts it. The \new" secret f(s) is just the linear combination of these \new"
shares. We claim that a coalition C of size t 1 gains no information that is not
implied by f(s) during this process. Indeed, the probability of the view of C is,
Pr[hs
The rst equality holds because the shares of C and f(s) determine the \new" shares
of B and vice-versa. The second equality holds because s determines f(s). Now
Pr[hs is independent of s by the security requirement prior to eval-
uation. So, we get the security requirement after evaluation. Furthermore, if this
process is repeated more than once and dierent linear combinations are evaluated
then C will gain no information that is not implied by these linear combinations, and
the parties in B can evaluate each bit of a non-boolean linear function independently.
Remark 3.3. Observe that in the broadcast scheme there is no need for the
set B to be given as input for the evaluation: each party P i which is available just
outputs an appropriate linear combination of its shares, and its identity P i . Then, a
function can be evaluated so long as there are at least t parties that agree to evaluate
the function. These parties do not need to be available at the same time, or know in
advance which parties would be available.
4. Schemes for Other Families of Functions. We now show how to use
the basic scheme (for linear functions) to construct schemes for other families of
functions. Given a family of functions, we shall construct a longer secret such that
every function in the family can be evaluated as a linear function of the longer secret.
Observe that any boolean function can be represented as a
binary vector over GF(2) of length 2 ' whose i-th coordinate is f(i). Similarly, any
can be represented as an array of ' 0 binary vectors
of length 2 ' in which the j-th vector corresponds to the j-th bit function of f(x).
The rank of a family of functions F is the smallest k for which there exist boolean
functions such that for every function f 2 F there exists a renaming of it
which each of the ' 0 vectors representing f 0 is a linear combination of f
The rank of a family does not change if we add renamings of functions. So, we can
assume that F contains all renamings of its functions.
Theorem 4.1. Let F be any family of functions.
There exists a t-out-of-n interactive private channels secret sharing scheme
for F with shares of length max frank(F); log n 1g.
There exists a t-out-of-n non-interactive broadcast secret sharing scheme for
F with shares of length rank(F)(log
Proof. Let be a basis for the vector space spanned by the functions
in F . To share a secret s the dealer generates a new secret
of length k (where - denotes concatenation of strings). The dealer now shares the
secret E(s) using the basic scheme (either the interactive or broadcast version, depending
on the communication model). Then, f i
f be the function in F to be evaluated. Without loss of generality, we may assume
) is such that the ' 0 vectors representing it are spanned by
Every bit of f(s) is a linear combination of f and therefore of
the bits of E(s) (i.e., e i (E(s))). Since addition in GF(2 k ) is bitwise, concatenation of
linear functions is a linear function too. Thus, f(s) can be computed by evaluating a
linear function of E(s). Thus, Theorem 4.1 follows by Theorems 3.1 and 3.2.
We demonstrate the applicability of the above construction by considering the
family ALL of all possible functions of the secret (boolean and non-boolean).
Corollary 4.2.
There exists a t-out-of-n interactive private channels secret sharing scheme
for ALL ' with shares of length max

There exists a t-out-of-n non-interactive broadcast secret sharing scheme for
ALL ' with shares of length
Proof. By Theorem 4.1 we have to show that the rank of ALL ' is 2 ' 1. Let
1. Consider the d boolean functions f
i: To evaluate a boolean function f we notice that the functions f(x) and f(x)
are renamings of each other, so we can assume that
a basis for ALL ' . In this case, the
secret s is encoded as the vector E(s) of length d in which the s-th coordinate is 1
and all the other coordinates are zero (with the exception
Notice that the length of the secret is ', while the length of the shares is (2 ' 1).
However, there are 2 2 ' 1 dierent boolean functions with domain of cardinality 2 ' such
that every function is not a renaming of another function (leaving aside non-boolean
functions). Therefore, our scheme is signicantly better than the naive scheme in
which we share every function (up to renaming) separately. Also the length of E(s)
for ALL ' must be at least log so the representation for E(s) that we
use is the best possible for the family ALL ' in this particular scheme. It remains
an interesting open question whether there exists a better scheme for this family, or
whether one can prove that this scheme is optimal.
5. Non-interactive Broadcast Scheme for the Bit Family. In this section
we present a non-interactive broadcast scheme for the family of bit functions, whose
shares are of length O(') (compared to O(' log n) of the scheme from Theorem 3.2).
Theorem 5.1. Let '
195 n log log n). There exists a non-interactive broadcast
t-out-of-n secret sharing scheme for the family BIT ' in which the length of the
secrets is ' and the length of the shares is O(').
We rst present a meta scheme (Section 5.1). Then we show a possible implementation
of the meta scheme that satises the conditions of the Theorem.
5.1. A Meta Scheme. Let k and h be integers (to be xed later) such that
1)e and the secret s has length '  kh. We view the secret as a binary
matrix with k rows and h columns and denote its (i; entry by s[i; j]. We construct,
in a way to be specied below, a new binary matrix H with 3k rows and h columns.
Then we share every row of H using Shamir's t-out-of-n scheme over GF(2 h ). Since
the length of every row is h  dlog(n 1)e, Shamir's scheme is ideal and every party
gets 3k shares of length h. The distribution stage of this scheme is illustrated in
Fig. 1. When a set B of cardinality (at least) t wants to reconstruct the bit s[i; j]
of the secret, the parties in B reconstruct a subset T i;j of rows (which depends only
on and not on B). We will guarantee that these rows do not give any additional
information on the secret.
Each party
Shamir
Fig. 1. An illustration of the meta scheme of the non-interactive broadcast scheme for the bit
family.
More specically, for every 1  i  k and 1  j  h, we x a set T i;j
(independently of the secret). The j-th column of H is constructed independently,
and depends only on the j-th column of the secret. It is chosen uniformly at random
among the column vectors such that:
To reconstruct s[i; j] it is enough to reconstruct the T i;j -rows of H , and compute the
sum (modulo 2) of the j-th bit of the reconstructed rows. (Actually, every party can
sum the shares of the T i;j -rows of H , and then the parties reconstruct the secret from
these shares. The j-th bit of the reconstructed secret equals to s[i; j].) That is, the
message of a party in a reconstructing set consists of the shares corresponding to the
T i;j -rows of H . The existence of a matrix H satisfying Equation (3), and the security
requirement after reconstruction depend on the choice of the sets T i;j . On the other
hand, independently of the choice of the sets T i;j , any coalition of size less than t
prior to any reconstruction does not have any information on the rows of H (by the
properties of Shamir's scheme), and, hence, does not have any information on the
secret. That is, the meta scheme is secure prior to the evaluation.
5.2. Implementing the Meta Scheme. We show how to construct sets T i;j
such that the security requirement after reconstruction will hold. Let R 1
3kg be a collection of dierent sets of size k. In particular, no set is
contained in another set (R 1 h is a Sperner family [2]). For
The number of sets of cardinality k which are contained in fk
xing k 4
su-ces. We require that h dlog
hk  ', and choose the smallest possible h. The length of the shares (i.e., 3h dlog he)
is ('). The following Claims are useful for proving the security of a reconstruction:
5.1. For every secret s, the number of matrices H that satisfy Equation (3)
for all j (1  j  h) is at least 1 and is independent of s.
Proof. Set H [i;
Equation (3). To show that the number of matrices satisfying Equation (3)
is independent of s, notice that H is a solution of a non-homogeneous system of linear
equations. Since the system has at least one solution, the number of such matrices is
the number of solutions to the homogeneous linear system of equations, where every
To show that no coalition gains any additional information, we rst consider the
case in which the coalition knows only the T i;j -rows of H . In this case, the coalition
can reconstruct s[i; j]. We prove that the coalition does not gain any information on
the other bits of the secret (i.e., bits s[i
5.2. Let s be a secret and x the T i;j -rows of H such that
The number of matrices H that satisfy Equation (3) for all j (1  j  h) is at least
1 and is independent of s.
Proof. We rst prove that there exists a matrix H satisfying the requirements.
Since the columns of H are constructed independently, it is enough to prove the
existence of every column j 0 . Only the j 0 -th column of the T i;j -rows of H , and the
-th column of s in
uence the j 0 -th column of H , hence, while considering the j 0 -th
column we can ignore the rest of the columns.
We rst consider the j-th column of H (i.e.,
we can assign H [i 0 ; j] a value as follows: for every i 0 such that k
(this is arbitrary); for every i 0 such that 1  i 0  k set
The case j 0 6= j is similar except that we have to be careful about
there is an element . We can assign H [i a value as
follows: for every i 0 such that k
We have shown that there exists a matrix as required. By the same arguments
as in the proof of Claim 5.1, the number of possible matrices given a secret s, is
independent of s.
We are now ready to prove the security requirement (note that this scheme is not
reusable).
5.3. The above implementation of the meta scheme is secure.
Proof. Let B be any set that evaluates a bit s[i; j] of the secret, and C be any
coalition. The security requirement before reconstruction is easy (this was discussed at
the end of Section 5.1). Suppose that C has obtained the messages sent by the parties
in B. That is, the parties in C know the shares of the parties of B corresponding to
the T i;j -rows of H . Therefore, the only information that they gain is the T i;j -rows
of H . Then, given the shares of the coalition and all the messages that were sent,
every matrix H that agrees with these rows is possible. We need to prove that, given
two secrets in which the (i; j)-th bit is the same, and a matrix H in which only the
are xed: the probability that H was constructed from each secret is equally
likely. By Claim 5.1 and Claim 5.2 this probability only depends on s[i; j].
6. Characterization of Families with Ideal Schemes. In this section we
consider ideal secret sharing schemes for a family F . We say that two secrets s; s 0
are distinguishable by F if there exists a function f 2 F for which f(s) 6= f(s 0 ). A
secret sharing scheme for F is ideal if the cardinality of the domain of shares equals
the cardinality of the domain of distinguishable secrets. These are the shortest shares
possible by [26]. The following theorem gives several impossibility results for ideal
schemes for a family F which contains the bit functions.
Theorem 6.1 (Characterization Theorem).
Suppose that there is an ideal interactive t-out-of-n secret
sharing scheme for a family of functions F such that BIT '  F . Then, any
boolean function f 2 F is linear.
ng. Suppose that there is an ideal non-interactive t-out-of-n secret
sharing scheme for a family of functions F such that BIT '  F . Then,
F  LIN ' .
(3) Let 3  t  n 1. In an ideal t-out-of-n secret sharing the evaluation of
every non-constant boolean function requires interaction on private channels.
2. In an ideal non-interactive 2-out-of-n secret sharing every non-constant
boolean function cannot be evaluated via a broadcast channel.
It follows that for families F , with BIT '  F , if interaction is allowed then every
boolean function in F is linear. If interaction is not allowed, then either
the functions in F are linear. In particular when
must be used.
In the Section 6.1 we will discuss some basic properties of ideal schemes that will
be needed for the proof of this Theorem. In Section 6.2 we prove (1) and (2), and in
Section 6.3 we prove (3) and (4).
6.1. Properties of Ideal Schemes. In this section we discuss some simple
properties of ideal schemes which are useful in the sequel.
Proposition 6.2 ([26]). Fix the shares of any t 1 parties in an ideal t-out-of-n
secret sharing scheme. Then, the share of any other party P is a permutation of the
secret. In particular all shares are possible for P .
In our proof, we use the following proposition regarding private functions, that is
functions that can be computed without revealing any other information on the inputs.
formal denition of privacy the reader is referred to Appendix C.) Bivariate
boolean private functions were characterized by Chor and Kushilevitz [16]:
Proposition 6.3 ([16]). Let A 1 ; A 2 be nonempty sets and f : A 1 A 2 ! f0; 1g
be an arbitrary boolean function. Then, f can be computed privately if and only if
there exist boolean functions such that for every
holds that f(x;
6.1. Let f be a boolean function that can be evaluated securely in an ideal
2-out-of-2 secret sharing scheme. Then, there exist boolean functions f 1 and f 2 such
that are the shares of P 1 and P 2 respectively.
Proof. The function f is evaluated from x and y, i.e., there is some function f 0
such that Proposition 6.2 any information that a party gets on
the share of the other party is translated to information on the secret. That is, the
parties must compute f 0 (x; y) in such a way that each party receives only information
implied by f 0 (x; y). In other words, they compute the boolean function f 0 privately.
By Proposition 6.3 there exist f 1 and f 2 such that
Consider an ideal t-out-of-n secret sharing scheme for F . Without loss of gener-
ality, we may assume that all the secrets are distinguishable by F . So, the parties
can reconstruct the secret from their shares. Denote the reconstructing
function by h(s We next prove an important property of the messages
sent in a non-interactive protocol that evaluates f .
6.2. Let f be a function that can be securely evaluated in an ideal t-out-
of-n secret sharing scheme without interaction. Without loss of generality, we may
assume that all the messages sent by P i , while holding the share s i , to the other parties
are identical, and equal to
| {z }
| {z }
Proof. It is su-cient to prove the claim for P 1 . Suppose that the shares of
the parties are s Consider a possible message of P 1 while the set
computes the value f(s). Party P 1 might toss coins, so if there are
several messages choose the rst one lexicographically. When P 1 holds two shares s 1
and s 0
1 such that f(h(s 1
the messages of P 1 to P i have
to be dierent, otherwise P i will compute an incorrect value in one of the cases. On the
other hand, for two shares s 1 and s 0
1 such that f(h(s 1
the messages sent by P 1 to the parties in fP have to be the same in both
cases, otherwise the coalition fP can distinguish between the secrets
loss of
generality, the messages sent by P 1 while holding the share s 1 are identical and equal
to
6.2. Proofs of (1) and (2) of Theorem 6.1. The proofs of Items (1) and (2)
are similar, and have two stages. We consider the following two-party distribution
scheme over GF(2 ' ), denoted XOR. Given a secret s, the dealer chooses at random
The share of the rst party is x, and the share of the second party is
x. In the rst stage (Section 6.2.1) we characterize the functions that can be
evaluated from the shares of XOR. In the second stage (Section 6.2.2) we show that
if there exists an ideal t-out-of-n secret sharing scheme for F , then XOR is a secret
sharing scheme for F . The combination of the two stages implies Items (1) and (2).
6.2.1. Characterizing the Functions which can be Evaluated with XOR.
We rst characterize the functions that can be evaluated with XOR without interac-
tion. It can be seen that every linear function of the secret can be evaluated with XOR
(the details are the same as in Remark 3.1). We prove that no other functions can be
evaluated securely without interaction. Then we characterize the boolean functions
that can be evaluated with XOR with interaction and show that these functions are
exactly the boolean linear functions.
To prove the characterization without interaction, we will prove that f(s) can be
computed from f(x) and f(y) (where x and y are the shares). In the next claim we
prove that every function with this property is a renaming of a linear function.
6.3. function. If there exists a function
g such that f(x is a renaming of
a linear function.
Proof. Let f(0)g. We rst prove that
The \only if" direction follows
Similarly the \if" direction follows from the following simple
equations:
That is, if In other words the set X 0 is a linear space
over the eld GF(2). Now consider a linear transformation
whose null space is X 0 (that is, f is a linear
space, such linear transformations exists. We claim that f is a renaming of f 0 , i.e.,
Equation (4), only if
(by the denition
of f 0 ). Since f 0 is linear, f only if
6.4. Let f be any function that can be evaluated without interaction with
the scheme XOR. Then, f is a renaming of a linear function.
Proof. Assume, without loss of generality, that f :
consider the function of x dened as min fy which is a renaming of f ).
By Claim 6.3 it su-ces to prove that f(x + y) can be computed from f(x) and f(y).
Denote the share of P 1 by x and the share of P 2 by y. Recall that y. By
6.2 the message sent by P 2 while holding a share y to P 1 is f(y), and the message
sent by P 1 while holding a share x to P 2 is f(x). Hence, P 1 can compute
y) from x and f(y). Moreover, for every two shares x 1 and x 2 held by P 1 such that
every share y held by P 2 , party P 1 must compute the same value
of f(s), since P 2 receives the same message from P 1 in both cases, and therefore
computes the same value of f(s). Hence, P 1 can compute f(x + y) from f(x) and
f(y). The computed function is the desired function g with f(x
By Claim 6.3 this implies that f is a renaming of a linear function.
We now prove a similar claim for interactive evaluations. However, this claim
applies only to boolean functions.
6.5. Let f be a boolean function that can be evaluated interactively with
the scheme XOR. Then, f is a renaming of a linear function.
Proof. Since XOR is an ideal scheme, Claim 6.1 implies that there exists boolean
functions In particular
there exists a bit b such that
is a linear function which is a
renaming of f .
The exact family of functions which can be evaluated interactively with XOR
consists of the two-argument functions for which can be computed
privately from x and y (as characterized in [29]).
6.2.2. Reduction to XOR. In this section we prove that if there exists an ideal
t-out-of-n secret sharing scheme for a family F , then there exists an ideal 2-out-of-2
secret sharing scheme for F . We then prove that this implies that XOR is a secret
sharing scheme for F .
6.6. If there exists an interactive (respectively non-interactive) ideal t-
out-of-n secret sharing scheme for F , then there exists an interactive (respectively
non-interactive) ideal 2-out-of-2 secret sharing scheme for F .
Proof. Let be a set of parties. We ignore the shares distributed
to parties not in B. Therefore, we have an ideal t-out-of-t secret sharing
scheme for F . Let hs (xed) vector of shares that is dealt to
B with positive probability. To share a secret s the dealer now generates a random
vector of shares of s (according to the scheme) that agrees with s respectively,
and gives the rst two components of this vector to P 1 and P 2 . Parties P 1 and P 2
know the shares of the other parties (as they are xed) and therefore P 1 , say, can
simulate the parties P in the protocol which evaluates the function f 2 F .
Hence, P 1 and P 2 can evaluate f(s) from their shares and the messages they exchange.
On the other hand, P 1 has no more information than the information known to the
coalition of cardinality t 1 in the t-out-of-t scheme. So, P 1 does not
gain additional information on s. Similar arguments hold for P 2 . This implies that
this scheme is a 2-out-of-2 secret sharing scheme for F .
6.7. Let BIT '  F . If there exists an interactive (respectively non-
ideal t-out-of-n secret sharing scheme for F , then XOR is an interactive
(respectively non-interactive) secret sharing scheme for F .
Proof. By Claim 6.6 we can assume that there exists an ideal 2-out-of-2 secret
sharing scheme for F , say . We transform  into XOR in a way that every function
that can be evaluated in  can also be evaluated in XOR.
6.1 implies that for every j, where 1  j  ', there exist boolean functions
2 such that e j
(y). For as the concatenation
of the values of these functions, that is m i (x) 4
every secret s and random input r of the dealer
Therefore, the scheme  0 dened by  0 (s; is a distribution
scheme equivalent to XOR. We still have to show that the two parties can
evaluate securely every function in F with  0 .
We rst prove that m 1 is invertible. Clearly, the two parties can reconstruct the
secret in  0 , while every single party knows nothing about the secret. Therefore,  0
is a 2-out-of-2 secret sharing scheme and, by [26], the cardinality of the domain of
shares is at least the cardinality of the domain of secrets. Thus, the cardinality of the
range of m 1 is at least as large as 2 ' . The domain of m 1 , which is the set of shares
of P 1 , has cardinality 2 ' . Therefore, m 1 is a bijection and, hence, invertible. So, P 1
can reconstruct the share x from m 1 (x). Similarly, P 2 can reconstruct the share y
from m 2 (y). This implies that the parties P 1 and P 2 , while holding m 1
respectively, can evaluate every function f 2 F . We have proved that every function
can be evaluated with  0 which is equivalent to XOR. Furthermore, if the
evaluation of the original scheme required no interaction, then also the evaluation
with the XOR scheme requires no interaction.
6.3. Proofs of (3) and (4) of Theorem 6.1. Next we prove Item (4). Namely,
in any ideal non-interactive t-out-of-n secret sharing scheme (2  t  n 1) evaluation
of a boolean function requires private channels. The proof is by contradiction. Suppose
that there is an ideal non-interactive t-out-of-n scheme in which the evaluation
can be held on a broadcast channel. Then, by the same arguments as in Claim 6.6,
since t  n 1, there is an ideal 2-out-of-3 scheme with the same property. Our rst
claim is that, without loss of generality, in the evaluation of f(s) every party sends a
one bit message such that the sum of the messages is f(s).
6.8. Assume there exists an ideal 2-out-of-3 secret sharing scheme in
which a non-constant boolean function f can be securely evaluated without interaction
via a broadcast channel. Then, P 1 and P 2 can securely compute f(s) by sending one
Proof. By Claim 6.2 we can assume that the message of P 1 while holding the
share s 1 is the bit Similarly, we assume that the message of P 2
while holding the share s 2 is Furthermore, the value of f(s) is
determined by these two messages. There are two values for f(s) and two values for
each message. Since each party knows nothing about f(s), a change of any message
will result in a change of f(s). The only boolean functions with two binary variables
satisfying this requirement are addition modulo 2, i.e.,
or loss of generality, assume that P 1 sends the message
the claim follows.
6.9. Consider an ideal non-interactive 2-out-of-3 secret sharing scheme
for a family F which contains a non-constant boolean function f . Then, f cannot be
evaluated via a broadcast channel.
Proof. Fix the share of P 3 to be z = 0. By Proposition 6.2, the share x of P 1
is a permutation of the secret. Assume, without loss of generality, that this share is
equal to the secret. (Of course P 1 does not know that z = 0 and does not know the
secret.) Since P 3 does not know f(s) although z = 0, the value of f(s) is not xed,
and the message that P 1 sends to P 2 while P 1 and P 2 evaluate f(s) cannot be constant
will not be able to evaluate f(s)). Furthermore, for any two shares
held by P 1 such that the messages of P 1 to P 2 should be the same
(otherwise P 3 will distinguish between the two secrets). Without loss of generality,
the message m 1 which P 1 sends to P 2 is f(x). By Claim 6.8,
the message that P 2 sends to P 1 is constant and P 1 will not be able to evaluate
f(s), which leads to a contradiction. Hence, f(s) cannot be evaluated on a broadcast
channel.
We conclude this section by proving Item (3). That is, for 3  t  n 1,
the evaluation requires interaction via private channels. Again, we assume towards
contradiction that there exists an ideal non-interactive t-out-of-n scheme for the family
F , and construct an ideal non-interactive 3-out-of-4 scheme for the family F . We show
that this contradicts Claim 6.9.
6.10. Assume there is an ideal 3-out-of-4 secret sharing scheme for a
family F in which a function f 2 F can be evaluated via private channels without
interaction. Then, there is an ideal 2-out-of-3 secret sharing scheme in which f can
be evaluated via a broadcast channel.
Proof. By Claim 6.2 we may assume that the messages sent during the evaluation
by one party to the other two parties are identical. In particular, if fP
evaluates a function, then P i knows the messages that P To construct
a 2-out-of-3 secret sharing scheme, we x a share u for P 4 , and share the secret s
with a random vector of shares such that the share of P 4 is u. When P i and P j want
to evaluate f(s), where 1  i < j  3, then P i simulates P 4 , and all messages and
broadcasted. After this evaluation, every party P k , where k 2 f1; 2; 3g, will have the
same information as the coalition fP had in the original scheme. Hence, P k does
not gain any information that is not implied by f(s). That is, we get a 2-out-of-3
secret sharing scheme for F .
7. Discussion. In this section we consider possible extensions of our work. So
far, we considered only threshold secret sharing schemes. In [22] a general notion of
secret sharing schemes for arbitrary collections of reconstructing sets is dened. That
is, we are given a collection A of sets of parties called an access structure and require
that any set in A can reconstruct the secret, while any set not in A does not know
anything about the secret. Clearly, secret sharing schemes exist only for monotone
collections. Conversely, it is known that for every monotone collection there exists
a secret sharing scheme [22]. More e-cient schemes for general access structures
were presented (e.g., in [7, 36]). However, the length of the shares in these schemes
can be exponential in the number of parties (i.e., of length '2 (n) where n is the
number of parties in the system and ' is the length of the secret). Our denition of
secret sharing for a family F of functions can be naturally generalized for an arbitrary
access structure. To construct such schemes, observe that the schemes of [22, 7, 36]
are \linear": the share of each party is a vector of elements over some eld, and every
set in A reconstructs the secret using a linear combination of elements in their shares.
Thus, if we share every bit of the secret independently, we can evaluate every linear
function of the secret without any interaction (the details are as in Theorem 3.2). This
implies that for every access structure, there exists a scheme for the family ALL ' in
which the length of the shares is O(2 ' 2 n ). However, if the access structure has a more
e-cient linear scheme for sharing a single bit then the length of the shares can be
shorter (but at least 2 ' ).
Another possible extension of the denition is by allowing a weaker \non-perfect"
denition of security. Such extensions in the context of traditional secret sharing
schemes were considered, e.g., in [9]. As remarked, there are several related works
on simultaneous secret sharing. For example, in [23] each set of cardinality at least
t should be able to reconstruct some of the secrets (but not all). In [11] each set B
of cardinality at least t is able to reconstruct any of the distributed secrets. 6 The
security requirement considered in [11, 24, 10] is somewhat weak: after revealing one
of the secrets, limited information about other secrets may be leaked.
Our scheme for the family of functions ALL ' uses shares of size 2 ' . We can
construct an e-cient scheme if we relax the security requirement as follows: every
set of size at least t can evaluate any function f(s) in a way that every coalition of
at most b(t 1)=2c parties gains no information on the secret (but larger coalitions
may get some information). In this case, we can use Shamir's t-out-of-n scheme to
distribute the secret and the interactive protocol of [5] or [15] to securely compute
f(s). In this scenario, the length of the share is the same as the length of the secret.
However, for most functions f , the length of the communication in the evaluation of
f is exponential in '.
6 In fact [11] deals with more general access structures and not only threshold schemes.

Acknowledgment

. The authors would like to thank the referees for several
helpful comments.



--R

On hiding information from an oracle
Combinatorial Theory
Hiding instances in multioracle queries
Universally ideal secret sharing schemes
Completeness theorems for noncrypto- graphic fault-tolerant distributed computations
Keeping shares of a secret secret
in Advances in Cryptology - CRYPTO '88

The security of ramp schemes


Some ideal secret sharing schemes
On the classi
Some improved bounds on the information rate of perfect secret sharing schemes


How to share a function securely
in Advances in Cryptology - AUSCRYPT '92
Shared generation of authenticators and signatures

Communication complexity of secure computation
sharing schemes realizing general access structure
in Advances


On secret sharing systems

Generalized linear threshold scheme
Privacy and communication complexity
Communications of the ACM

On data banks and privacy homomor- phisms

How to share a secret
An introduction to shared secret and/or shared control and their application
The geometry of shared secret schemes
An explication of secret sharing schemes
--TR

--CTR
Christian S. Collberg , Clark Thomborson, Watermarking, tamper-proffing, and obfuscation: tools for software protection, IEEE Transactions on Software Engineering, v.28 n.8, p.735-746, August 2002
secret sharing;private computations;private channels;interaction;broadcast channel