Cryptography Reference
In-Depth Information
where i = 1, 2,...,n.
Step 1:
Select the number k, k n.
Step 2:
Choose the (k-1) integers a
1
;a
2
;:::;a
k1
randomly.
Step 3:
For the i-th secret sharing participant, choose a value of xi
i
freely, i
= 1, 2,..., n. Note that all xi
i
must be distinct from one another.
Step 4:
For each chosen x
i
, compute the corresponding F(x
i
) by using
Equation 16.13.
Step 5:
Deliver each pair of (xi,
i
;F(x
i
)) as a secret share to each participant.
In this secret sharing process, the values of a
i
, i = 1, 2, ..., k 1, need not be
kept after all secret shares are generated. As well as the secret value s, each
a
i
can be recovered from the n secret shares in the secret recovery steps listed
below.
Step 1:
Collect at least k secret shares from the n ones to form a system of
equations as shown in Equation 16.13. Note that the xi and F(x
i
)
in Equation 16.13 with i =1, 2, ..., k can all be extracted from the
k secret shares.
Step 2:
Use a polynomial interpolation technique, e.g., Lagrange scheme, to
solve s and a
i
, i = 1, 2, ..., k 1. Reconstruct the (k 1)-degree
polynomial F(x) described by Equation 16.14.
(xx
2
)(xx
3
):::(xx
k
)
(x
1
x
2
)(x
1
x
3
):::(x
1
x
k
)
F(x) = F(x
1
)
(xx
1
)(xx
3
):::(xx
k
)
(x
2
x
1
)(x
2
x
3
):::(x
2
x
k
)
+ F(x
2
)
(16.14)
+ :::
(xx
1
)(xx
2
):::(xx
k1
)
(x
k
x
1
)(x
k
x
2
):::(x
k
x
k1
)
+ F(x
k
)
Step 3:
Compute the solution for the secret value s by Equation 16.15.
Search WWH ::
Custom Search