Cryptography Reference
In-Depth Information
5.1
Secret Sharing Scheme
The underlying secret sharing scheme of our DOT protocol is Shamir's threshold
scheme. In [11], Shamir shows how to share a secret
ω ∈
IK amongst
m
users
u
1
,...,u
m
such that
ω
can be reconstructed from any set of
k
(
k ≤ m
)shares.
Shamir suggests the following algorithm for constructing such secret sharing
schemes, called (
k
,
m
)-threshold schemes.
1. A dealer,
, who has a secret
ω
,chooses
m
distinct and non-zero elements
of IK, denoted
x
1
,...,x
m
and sends
x
i
D
to
u
i
via a public channel. For con-
venience, we assume that
x
i
=
i
.
2.
D
secretly chooses
k
−
1 random elements of IK, denoted
a
1
,...,a
k−
1
and
forms the polynomial function
f
(
x
)=
k−
1
=1
a
x
+
ω
.
3.
D
gives (in private) the share
f
(
i
) to the user
u
i
.
In the secret reconstruction phase, a set of at least
k
participants uses the La-
grange interpolation formula to recover the secret. Without loss of generality, let
u
1
,...,u
k
be the set of collaborating users in the secret reconstruction phase.
Then the secret can be recovered, using
k
k
j
ω
=
f
(
i
)
.
j
−
i
i
=1
j
=1
j
=
i
It is well-known that Shamir's threshold scheme is perfect, i.e., the knowledge
of
k
1orlesssharesleaves
ω
completely undetermined (in the sense that all
its possible values are equally likely).
−
5.2
Transformation from One to Another Threshold Scheme
There are many applications that require redistribution of a secret from one set
of users to another set of users, with possibly a different threshold. Desmedt
and Jajodia [6] have considered this problem and proposed some protocols. The
specific case of the reduction of the threshold is commonly discussed in multi-
party computation studies. Indeed, if two secrets are shared (Shamir's scheme)
thanks to two polynomials
P
1
and
P
2
of IK
k−
1
[
X
], then from the polynomial
Q
=
P
1
×
P
2
can be generated shares of the product of the two secrets (See
Theorem 2). But the degree of
Q
(up to 2
k
−
2) corresponds to a threshold
2
k
1, and so a degree reduction is necessary to obtain a sharing polynomial
corresponding to a threshold
k
. Such a reduction was introduced, for example,
by Ben-Or, Goldwasser and Wigderson [2].
Below we present a combined method, allowing a set of
k
1
or more users hold-
ing shares generated by a Shamir's (
k
1
,
m
1
)-threshold scheme to distribute them
under the form of shares generated by a Shamir's (
k
2
,
m
2
)-threshold scheme,
where
k
1
≥
−
k
2
,toasetof
m
2
users.
Let a secret
ω
be shared amongst the group of users
U
=
{
u
1
,...,u
m
1
}
thanks
to a polynomial
f
generated in a (
k
1
,
m
1
)-threshold scheme (
k
1
≤
m
1
). Each
Search WWH ::
Custom Search