Cryptographic Protocols - A Classical Introduction to Cryptography: Applications for Communications Security - page 277

only a few combinations of participants enable the reconstruction of S by putting their
shares together. These cryptographic schemes are called secret sharing schemes .

We can illustrate it by an easy case: when the key is shared among n participants who
all need to cooperate in order to reconstruct S . In this case we can give a random S i = X i

as a share to the i -th participant for i X n − 1

to the n -th participant. In this case no proper subset of the n participants can reconstruct
S . In fact, no proper subset of the n participants can learn any information about S .

= 1 ,..., n − 1, and give S ⊕ X 1 ⊕···⊕

11.2.1 The Shamir Threshold Scheme

Adi Shamir proposed the first secret sharing scheme with an elaborate access structure
(see Ref. [163]). This secret sharing scheme allows to share S among n participants
so that any subset of t participants can reconstruct S , but no subset of at most t

− 1

participants learn any information about S . Here t is called the threshold .

We have already seen the t = n case.

Another easy case is t = 1: we just give S i = S as a share to the i -th participant.

2 case. We now assume that S is encoded as an element of
a field K . We also assume that each participant has a non-zero identity string x i which
is also a field element. Let A be a random element of K with uniform distribution. We
define S i =

Let us start with the t =

Ax i +

S . For any user, the share distribution is uniform, and independent
of S . Therefore, no single user can reconstruct S . Furthermore, any two users x i and
x j can reconstruct S by

S i − S j

S = S i −

x j x i . x i −

The system is depicted in Fig. 11.3. For a user who corresponds to x 3 , the system is
depicted by a straight line which goes through the ( x 3 , S 3 ) point, but the user has no

clue which line it is. If another user joins (say x 6 ) they can together reconstruct the
straight line and deduce S .

Generalization is now straightforward. We let A 1 ,..., A t − 1 be independent ran-

A t − 1 x t − 1 domly distributed field elements. We define S i = +···+ A 1 x + S .Wecan

i

=

A t − 1 x t − 1

+···+ +

S and we have S i =

define P ( x ) A 1 x P ( x i ). For any t partici-

pants, we have t points ( x i ,

S i ) on the graph of the polynomial mapping P ( x ), which
is of degree less than t , and therefore we can reconstruct it by interpolation. Indeed,
putting the x i 1 ,...,

x i t shares together, the polynomial is

t

S i j
k = i j

x k
x i j −

x −

P ( x ) =

x k .

j = 1