Cryptography Reference
In-Depth Information
A natural question now is: Is any set of subsets with the monotonicity property
an access structure for a perfect secret sharing scheme? This question is addressed in
Section 11.2.4.
Before continuing we define the notion of access structure spanned by a given set
of subsets. Given a set of subsets
0
, we define
=
0
as the set of all supersets of
any set in
0
. This clearly has the monotonicity property. It is also clearly the smallest
set of subsets with the monotonicity property which includes
0
. For this reason we
say that
is spanned by
0
.
11.2.4
The Benaloh-Leichter Secret Sharing Scheme
The
Benaloh-Leichter
secret sharing scheme enables the construction of a perfect secret
sharing scheme for any access structure with a monotonicity property (see Ref. [27]).
It works as follows.
1. Given an access structure
with the monotonicity property, we first express
as an algebraic expression with only
∪
and
∩
operations from all
i
access
structures defined as follows:
i
is the set of all participant subsets which include
the
i
-th participant. In other words,
.
2. To each subexpression we recursively attach variables in a top-down way:
if
X
is attached to some subexpression
t
i
={
i
}
t
, we attach
X
to both
t
and
∪
t
,
if
X
is attached to some subexpression
t
t
, we attach a new random variable
∩
Y
to
t
.
3. For each participant
i
we collect all variables attached to occurrences of
Y
to
t
and
X
−
i
, and
we define them as the share of the participant.
We have the following result.
Theorem 11.3.
The above construction builds a perfect secret sharing scheme of ac-
cess structure
.
As an example, let us define a perfect secret sharing scheme among a set of four
participants
P
1
,
P
2
,
P
3
,
P
4
such that
P
1
and
P
2
can reconstruct the secret,
P
1
and
P
3
can reconstruct the secret,
P
2
,
P
3
, and
P
4
can reconstruct the secret.
Clearly, the access structure expresses into
=
((
1
∩
2
)
∪
(
1
∩
3
))
∪
((
2
∩
3
)
∩
4
)
Search WWH ::
Custom Search