Cryptography Reference
In-Depth Information
(
x
−
x
1
)(
x
−
x
3
)
···
(
x
−
x
k
)
+
y
2
(
x
2
−
x
1
)(
x
2
−
x
3
)
···
(
x
2
−
x
k
)
+
...
(
x
−
x
1
)(
x
−
x
2
)
···
(
x
−
x
k−
1
)
+
y
k
x
k−
1
)
.
(
x
k
−
x
1
)(
x
k
−
x
2
)
···
(
x
k
−
In Shamir's
k
-out-of-
n
secret sharing system, the secret (to be shared) repre-
sents the coefficient
r
0
. The dealer randomly selects
k
1 coefficients
r
1
,...,r
k−
1
to define a polynomial according to formula (19.1). For every player
P
i
, the dealer
then assigns a fixed nonzero field element
x
i
and computes
y
i
=
f
(
x
i
). The pair
(
x
i
,f
(
x
i
)) is then taken for
P
i
's share.
Anybody who is given
k
shares can compute the secret
r
0
by evaluating the
Lagrange interpolating polynomial at point zero (i.e.,
s
=
r
0
=
P
(0)). Anybody
who is given fewer than
k
shares cannot compute the secret. More precisely, anybody
who is given fewer than
k
shares does not obtain any (partial) information about the
secret. This means that Shamir's
k
-out-of-
n
secret sharing system is perfect.
K
-out-of-
n
secret sharing systems are interesting from a theoretical view-
point. This is particularly true if the systems are perfect. From a more practical
viewpoint, however, there are at least two problems that must be addressed and
considered with care:
−
•
If a malicious player is not honest and provides a wrong share, then the secret
that is reconstructed is also wrong.
•
If the dealer is malicious or untrusted, then the players may want to have a
guarantee that they can in fact put together the correct secret.
A
verifiable secret sharing system
can be used to overcome these problems.
For example, Shamir's
k
-out-of-
n
secret sharing system can be made verifiable by
having the dealer make commitments to the coefficients of the polynomial
f
(
x
) and
providing the players with help-shares they can use to verify shares. We don't delve
deeper into secret sharing systems and verifiable secret sharing systems in this topic.
Note, however, that (verifiable) secret sharing systems play a central role in many
cryptographic systems and applications, such as electronic cash or electronic voting.
Most importantly, verifiable secret sharing systems are at the core of many protocols
to implement secure MPC (see Chapter 18).
19.4
KEY RECOVERY
If one uses cryptographic techniques for data encryption, then one may also be
concerned about the fact that (encryption and decryption) keys get lost. What
