property is called perfect. The set of all allowed

The de¬nition of a one-way function was given

coalitions is called an access structure.

in 1976 by Dif¬e and Hellman [1]. Second preim-

The history of SSS began in 1979 when this

age resistance of hash functions has been intro-

problem was introduced and partially solved by

duced by Rabin in [5]; further work on this topic

Blakley [1] and Shamir [2] for the case of (n, k)-

can be found in [2“4, 7, 8]. For a complete for-

threshold schemes where the access structure con-

malization and a discussion of the relation be-

sists of all sets of k or more participants. Consider

tween the variants and between hash functions

the simplest example of (n, n)-threshold scheme.

properties, the reader is referred to Rogaway and

There is a dealer who wants to distribute a secret

Shrimpton [6].

s0 among n participants. Let s0 be an element of

B. Preneel some ¬nite additive group G. For instance, G is

the group of binary strings of length m with addi-

tion by modulo 2, i.e., G = GF(2)m (see ¬nite ¬eld).

References

The dealer generates a random sequence s1 , . . . , sn

n

such that i=1 si = s0 (for instance, by generating

[1] Dif¬e, W. and M.E. Hellman (1976). “New directions

independently elements s1 , . . . , sn’1 ∈ G and then

in cryptography.” IEEE Transactions on Informa- n’1

putting sn := s0 ’ i=1 si ). Then the dealer sends

tion Theory, IT-22 (6), 644“654.

privately to each ith participant the elements si

[2] Merkle, R. (1979). Secrecy, Authentication, and Pub-

called share, i.e., other participants have no infor-

lic Key Systems. UMI Research Press.

mation about the value of si . It is easy to see that

[3] Preneel, B. (1993). “Analysis and Design of Cryp-

tographic Hash Functions.” Doctoral Dissertation, any coalition of less then n participants has no in-

Katholieke Universiteit Leuven. formation except of a priori information about s0

[4] Preneel, B. (1999). “The state of cryptographic hash and all participants together recover the value of

functions.” Lectures on Data Security, Lecture Notes n

the secret as i=1 si . These simple schemes ap-

˚

in Computer Science, vol. 1561, ed. I. Damgard.

pear to be enough for the realization of arbitrary

Springer-Verlag, Berlin, 158“182.

monotone (i.e., if A ∈ and A ‚ B then B ∈ ) ac-

[5] Rabin, M.O. (1978). “Digitalized signatures.” Foun-

cess structure . Namely, for any allowed coali-

dations of Secure Computation, eds. R. Lipton and

tion A ∈ let the above realize (independently)

R. DeMillo. Academic Press, New York, 155“166.

an (|A|, |A|)-threshold scheme, i.e., send to the

[6] Rogaway, P. and T. Shrimpton (2004). “Crypto-

ith, participant as many shares siA) as the num-

graphic hash function basics: De¬nitions, impli-

ber of allowed coalitions to which this participant

cations, and separations for preimage resistance,

Secret sharing schemes 545

belongs it is enough to consider only maximum al- is at least n/ ln n times larger than the size of the

lowed coalitions). secret [11].

The probabilistic model of an SSS for the general To generate shares the dealer of an SSS has to

case is the following (see [4, 5]). There are n + 1 use some source of randomness, say r ∈ X, where

sets S0 , S1 , . . . , Sn and the probability distribution X is in some probabilistic space, and any share

P on their Cartesian product S = S0 — · · · — Sn . A si is a function of s0 and r , i.e., si = fi (s0 , r ). A

pair (P, S) is called a perfect probabilistic SSS re- linear realization of SSS (or, linear SSS) means

alizing the access structure if the following two that all functions fi (·) are linear. To make it for-

mal: let s0 , . . . , sn be elements in mi -dimensional

properties hold:

r participants of an allowed set A ( i.e., A ∈ ) to- vector spaces (i = 0, 1, . . . , n) over some ¬nite ¬eld

gether can recover the secret exactly (formally, GF(q) of q elements, let r be an element of the

P(S0 = c0 | Si = ci , i ∈ A) ∈ {0, 1} if A ∈ ); l-dimensional vector space over the same ¬eld.

r participants forming a non-allowed set A (A ∈ / Then a linear SSS is generated by some (m0 +

l) — m matrix G according to the formula s =

) cannot get additional information beyond

n

their a priori information about s0 , i.e., P(S0 = (s0 , . . . , sn ) = xG, where m = i=0 mi and vector

c0 | Si = ci , i ∈ A) = P(S0 = co) if A ∈ . These con-

/ x is the concatenation of vectors s0 and r. Con-

sider vector spaces V0 , . . . , Vn , where Vi is the lin-

ditions can be reformulated in the language

of entropy (see information theory) as H(Si , ear subspace generated by the columns of G that

i ∈ A ∪ 0) = H(Si , i ∈ A) + δ (A)H(S0 ), where correspond to si , i.e., by columns g j, where j =

δ (A) = 0 if A ∈ , and δ A) = 1, otherwise. m0 + · · · + mi’1 + 1, . . . , m0 + · · · + mi . Then ma-

There are also combinatorial models of SSSs. trix G realizes the access structure perfectly if

An arbitrary set V ‚ S is called the “code” of the and only if [12, 13]:

r for any set A ∈ the linear span of subspaces

combinatorial SSS, and its codewords called “shar-

{Va : a ∈ A} (i.e., the minimal vector subspace

ing rules”. The simplest combinatorial model de-

mands that at ¬rst, for every set A ∈ the 0th containg all these subspaces Va ) contains the

coordinate of any codeword from V is uniquely de- subspace V0 ;

r for any set A ∈ the linear span of subspaces

/

termined by the values of the coordinates from the

set A and, secondly, for every set A ∈ and for any

/ {Va : a ∈ A} intersects with the linear subspace

given selection of values of the coordinates from V0 only by the vector 0.

the set A the number of codewords with given All aforementioned examples of SSS are linear.

value of 0th coordinate does not depend on this Note that if all dimensions mi are equal to 1

value. This model is a particular case of the prob- then the matrix G can be considered as a gener-

abilistic model, namely, when all nonzero values of ator matrix of a linear error-correcting code (see

P are equal. The most general de¬nition of combi- cyclic codes). In particular, it gives another de-

natorial models, which contain probabilistic ones scription of Shamir™s threshold schemes via Reed“

as a particular case, was given in [6, 7]. Solomon codes [14]. This “coding theory approach”

For both types of models the “size” of share, pro- was further developed and generalized to the case

vided to any participant, cannot be smaller than of arbitrary linear codes and their minimal words

the “size” of the secret, where “size” is de¬ned as as only possible access structures [16]. Surely, a

log|Si | or H(Si ) respectively for combinatorial and linear SSS with all dimensions mi = 1 is ideal, but

multidimensional linear SSSs with all mi = m0

probabilistic statements of the problem. Special

attention has been paid to so-called ideal SSSs, give a larger class of ideal SSS [15]. It is an open

where the size of any share coincides with the question if any ideal SSS can be realized as a (mul-

size of the secret. For example, any (n, k)-threshold tidimensional) linear ideal SSS?

scheme can be realized as an ideal perfect SSS (see Modi¬cations of assumptions of the secret shar-

threshold cryptography). It was shown in a chain ing problem™s statement such as perfectness of the

of papers [6“9] that the access structures of ideal scheme, honesty of the dealer and participants,

perfect SSS correspond to a special class of ma- sending shares via secure, private channels and so

troids [10]. On the other hand, any access struc- on lead to many variations of secret sharing prob-

ture can be realized as a perfect SSS but probably lem. Among them: ramp schemes, publicly veri¬-

not very ef¬cient (ideal). At least the above given able secret schemes, SSS with cheaters, SSS

realization demands for some access structures to with public reconstruction [17], and visual secret

distribute shares which size is exponentially (in sharing schemes.

n) larger than the secret™s size. An in¬nite fam-

Robert Blakley

ily of access structures was constructed such that

Gregory Kabatiansky

for any perfect realization the size of the shares

546 Secure signatures from the “strong RSA” assumption

References Russian Workshop on Information Theory, Molle,

Szweden, 246“249.

[17] Beimel, A. and B. Chor (1998). “Secret sharing with

[1] Blakley, R. (1979). “Safeguarding cryptographic

public reconstruction.” IEEE Transactions on In-

keys.” Proceedings of AFIPS 1979 National Com-

formatiom Theory, 44 (5), 1887“1896.

puter Conference, vol. 48, Va. Arlington, New York,

313“317.

[2] Shamir, A. (1979). “How to share a secret.” Com-

munications of the ACM, 22 (1), 612“613.

SECURE SIGNATURES

[3] Ito, M., A. Saito, and T. Nishizeki (1993). “Multiple

FROM THE “STRONG RSA”

assignment scheme for sharing secret.” Journal of

Cryptology, 6, 15“20.