Cryptography Reference
In-Depth Information
The equation has a unique solution if the determinant of the matrix is nonzero
mod p. It can be shown that the determinant of the matrix is nonzero mod p
if all xi, i , i = 1, 2,, t, are dierent. After the polynomial is reconstructed,
the secret s is obtained by the output of q(0).
15.2.2 Lagrange Interpolation Scheme
An ecient method to obtain the sharing polynomial f is to use the Lagrange
interpolation. Assume that the pairs (x 1 ;y 1 ), (x 2 ;y 2 ),, (x t ;y t ) are used to
reconstruct the polynomial q(x). For k = 1, 2,, t, let
l k (x) = Q i=1;i6=k xx i
x k x i mod p
We know that
l k (x j ) = f 1;when k = j
0;when k 6= j
Then, the Lagrange interpolation polynomial is formed as follows:
q 0 x = P k=1 y k l k mod p
Because y i q 0 (x i )(modp) for i = 1, 2,, t and q 0 (x) has degree t 1,
q 0 (x) is equal to the polynomial q(x). Finally, the secret s can be obtained by
evaluating q(x) at x = 0. That is,
s P k=1 y k Q j=1;j6=b x i
x k x i mod p
In fact, all coecients in q(x) can be seen as secrets. We show an example
for the Lagrange interpolation polynomial.
Example 1.
Take a (2; 4)-threshold scheme. In the share generation phase, assume that
the pixels of the target secret image S indexed in order of left-to-right and
top-to-down is S i , I = 0; 1; 2; ;n. The rst two pixels, for instance, S 0 =
100 and S 1 = 200 are set in this case. First of all, a polynomial of q(x) =
200x + 100 mod 251 is given according to the S 0 i s. Compute the shares y 0 j s
associated with each participants as y 1 = q(x 1 =1) = 49, y 2 = q(x 2 =2) =
249, y 3 = q(x 3 =3) = 198, and y 4 = q(x 4 =4) = 147, where x 0 i s are the identity
numbers of the four participants. Next, consider the recovery of the pixels of
the target secret image in this case. In the (2; 4)-threshold scheme, any two
participants who own the shares y 0 j s can gather to recover the secret, for ex-
ample, the participants nos. x 2 and x 4 . There are two pairs of (x 2 , y 2 ) = (2,
249) and (x 4 , y 4 ) = (4, 147) offered from the participants. In such a way that
 
 
Search WWH ::




Custom Search