Cryptography Reference
In-Depth Information
scientists are working on a secret project and want to conceal their results in
a vault so that none of them can have individual access. The secret document
can only be retrieved when a majority of the 11 scientists, that is, any permu-
tation of six or more of them, are present. Liu's vault question is: If a key can
only open one lock, what is the minimum number of locks and keys needed
to grant this form of access? The answer can be easily calculated to be 462
locks on the vault, and 252 keys per scientist or a total of 2772 keys.
In general where there are
n
scientists and at least
k
of them have to
collaborate to open the vault, the total number of locks is
C
k
−
1
=
n
!
/((
k
−
!), and each scientist has to carry
C
n
−
1
k
1
1
keys. It becomes clear from
this example that this kind of protocol is impractical when working within
the mechanical paradigm. Resource requirements become exponentially large
when the number of scientists increases.
Shamir [1] and Blakley [4] independently formalized Liu's problem in
1979. Their goal was to divide some secret information
D
into
n
shares
D
1
,
D
2
,
)
!
(
n
+
1
−
k
)
−
...
,
D
n
in such a way that
•
The knowledge of
k
or more
D
i
(where
k
n
) makes
D
easily com-
putable. The ensemble of all the permutations of such shares is referred
to as the
access structure
.
≤
•
The knowledge of
k
1 or fewer
D
i
gives absolutely no information
on
D
. The ensemble of these shares is known as the
adversary structure
.
−
Such schemes are called (
k, n
)
threshold secret sharing
. Shamir's idea is
based on polynomial interpolation [1]. The dealer, who wants to share some
secret information, chooses a polynomial
P
(
x
)
of degree
k
−
1, and distributes
n
pairs of values (
x
1
,P
to the players. The
secret information can be, for instance, the
y
-axis intercept of the polynomial
P
(
x
1
))
,
(
x
2
,P
(
x
2
))
,
...
,
(
x
n
,P
(
x
n
))
. It is then clear that any
k
or more players are able to recover the original
polynomial using interpolation of their values (see Figure 8.3(a)). On the
other hand, any subset of
k
(
0
)
−
1 or fewer players face an infinite possibility
of polynomials that have all their values included. Therefore no information
about the secret can be recovered (see Figure 8.3(b)).
Blakley's secret sharing protocol, on the other hand, is based on projective
spaces [4]. In his scheme, the dealer distributes a point in a projective space of
dimension
k
to each player. Each of the
n
players therefore receives a subspace
of dimension
k
1 (i.e., a hyperplane) comprising the secret data point.
k
or
more players can then intersect their hyperplanes together to retrieve the
secret. Similar to Shamir's protocol,
k
−
1 or fewer players will not be able to
obtain a unique point by the intersection of their hyperplanes and are thus
unable to recover the secret.
Apart from avoiding the explosion of resources required by a mechanical
implementation of secret sharing, both Shamir's and Blakley's mathematical
methods present several additional advantages. First, the size of information
distributed to each player does not exceed the size of the secret. This allows
−
