Cryptography Reference
In-Depth Information
Intuitively, the access structure is the set of all subsets of participants who can recon-
struct
S
. If a subset
A
of participants can reconstruct
S
, putting their shares together
provides a zero entropy to
S
, which is expressed by
H
(
S
0. The secret
sharing scheme is said to be perfect when no subset
A
of participants which is not in
|
S
i
;
i
∈
A
)
=
can gain any information on
S
by putting their shares together, which is expressed
by
H
(
S
H
(
S
). This last condition is very similar to the notion of
perfect
secrecy
which was used for encryption.
|
S
i
;
i
∈
A
)
=
We can now formalize the security result of the Shamir secret sharing scheme.
Theorem 11.2.
For any threshold t , the Shamir threshold secret sharing scheme is
perfect, with the access structure which consists of all subsets of at least t participants.
We have already seen how to reconstruct
S
as long as we have at least
t
shares. Therefore
the entropy of
S
is zero given these shares.
We should now prove that for any
i
1
,...,
i
t
−
1
, the distribution of
S
restricted to val-
ues of
S
i
1
,...,
S
i
t
−
1
is still uniform. We know (thanks to interpolation) that the function
which maps (
S
,
A
1
,...,
A
t
−
1
)to(
S
,
S
i
1
,...,
S
i
t
−
1
) is one to one. This means that for
any (
s
,
s
i
1
,...,
s
i
t
−
1
), the probability that we have
S
=
s
and
S
i
j
=
s
i
j
simultaneously
is (#
K
)
−
t
.Nowwehave
Pr[
S
i
j
=
s
i
j
;
j
=
1
,...,
t
−
1]
=
Pr[
S
=
s
,
S
i
j
=
s
i
j
;
j
=
1
,...,
t
−
1]
s
(#
K
)
−
t
+
1
=
and
(#
K
)
−
1
Pr[
S
=
s
|
S
i
j
=
s
i
j
;
j
=
1
,...,
t
−
1]
=
.
Therefore the distribution of
S
is still uniform when we fixed
S
i
1
,...,
S
i
t
−
1
: we gained
no information by having these shares only.
11.2.3
Access Structure of Perfect Secret Sharing Schemes
An interesting question is for which access structure does a perfect secret sharing
scheme exist? We have already seen that it exists for a threshold access structure,
thanks to the Shamir scheme. Obviously, if
is an access structure for which there
exists a perfect secret sharing scheme,
must fulfill the following requirement.
For any
A
. (If we can reconstruct
S
from the shares of
A
, we can still do it with more shares in
B
.)
∈
and any
B
such that
A
⊂
B
,wehave
B
∈
We call this the monotonicity property.
Search WWH ::
Custom Search