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