Cryptography Reference
In-Depth Information
S
6
S
3
S
x
1
x
2
x
3
x
4
x
5
x
6
x
7
Figure 11.3.
Shamir threshold secret sharing scheme with
t
=
2.
(It is easy to check that this polynomial maps
x
i
onto
S
i
, therefore
P
(
x
) minus this
polynomial has at least
t
roots
x
i
1
,...,
1, the
difference must be zero, so this must be the
P
(
x
) polynomial.) The interpolation now
yields
S
x
i
t
. Since it is of degree at most
t
−
=
P
(0). Finally, the reconstruction formula is simply
t
S
i
j
1
x
k
x
k
−
S
=
x
i
j
.
j
=
1
≤
k
≤
t
k
=
i
j
It is by far more technical to prove that no set of
t
−
1 participants have any
knowledge about
S
. Before doing this, we need more theory.
11.2.2
Perfect Secret Sharing Schemes
Here we treat the secret
S
and the shares
S
i
as random variables. We use again the
Shannon entropy
.
Definition 11.1.
Let n be an integer and let
be a set of subsets of
{
1
,...,
n
}
. A secret
sharing scheme among n participants P
1
,...,
P
n
and based on an access structure
is said to be perfect when
∀
A
(
H
(
S
|
S
i
;
i
∈
A
)
=
0
⇐⇒
A
∈
)
∀
A
(
H
(
S
|
S
i
;
i
∈
A
)
=
H
(
S
)
⇐⇒
A
∈
)
where S is the secret and S
i
is the share of P
i
.
Search WWH ::
Custom Search