Cryptographic Protocols - Codes: The Guide to Secrecy from Ancient to Modern Times - page 214

for i =1 , 2 ,...,t , which is (5.2). Therefore,

p ( x ) ≡ f ( x )(mod p )

since the Lagrange interpolation formula, given on page 486, tells us that f is
the unique polynomial with f ( x )

∈ F p [ x ] such that

f ( x i ) ≡ m i (mod p ) for 1 ≤ i ≤ t.

In particular, Equation (5.3) holds with x =0.
Security : In Shamir's scheme, no fewer than t participants can recover m ,a
propertythat makes it an example of what is sometimes called a perfect thresh-
old scheme . The securityof Shamir's scheme does not relyupon the assumed
intractabilityof such problems as the DLP or the IFP. Hence, in practice, the
scheme is as secure as a one-time pad in the sense that an exhaustive search of
all possible shares will reveal to an adversarythat any message m could be the
secret.
Variations : Let us assume that a bank president wants to control the ma-
jorityof the shares in a scheme for secret-sharing the combination to the bank's
vault. Suppose that t = 9 shares are required and the president has 7 shares
while other participants have only1 share. Therefore, the president gets together
with two underlings to recover the combination, but without participation by
the president, it takes 9 participants to recover it.
Another variation on Shamir's scheme is depicted bythe next setting. As-
sume that two banks A and B hold their securities in the same vault. Theywish
to create a scheme where 2 participants from bank A and 3 participants from
bank B hold shares. Here is how theyaccomplish the task. Form the product
of a linear polynomial p 1 and a quadratic polynomial p 2 . Then give w 1 ≥

2

≤ ≤ ≥

employees of bank A a share p 1 ( x i ) for 1 i w 1 , and give w 2 3 employees

from bank B a share p 2 ( y i ) for 1 w 2 . Then anytwo participants from

bank A can get together and recover p 1 but not p 2 , and any3 participants from
bank B can get together and recover p 2 but not p 1 . Participants from both
banks A and B must work together to recover the full combination determined
bythe product p 1 p 2 acting on the individual shares.
The last secret-sharing scheme is due to the second pioneer who developed
his idea in the same year as Shamir. In 1979, Blakely came up with a scheme
(see [25]) based upon vectors and matrices (see pages 490-494 in Appendix A).
It is not a ( t, w )-secret-sharing scheme.

≤ i ≤

Blakely's Secret-Sharing Vector Scheme
The secret message is m 1 to be reconstructed by t> 2 participants.
Setup Stage : The following are executed.

1. Choose a large prime p>m 1 , where p is made public, and select
m 2 ,m 3 ,...,m t ∈ F p at random. Then m =( m 1 ,m 2 ,...,m t )isapointin
the t -dimensional vector space

t p .

F