Cryptography Reference
In-Depth Information
5.5 Secret Sharing
I share no one's ideas. I have my own.
Ivan Turgenev (
1818
-
1883
)
,
Russian novelist
— from
Fathers and Sons
(1862), Chapter 9
When we discuss e-commerce on page 228, look at splitting secrets for the
digital cash schemes discussed therein. That application is the simplest form,
namely, the sharing of two pieces of a secret by two entities who add their
respective pieces modulo 2 to recover the secret. This notion is easilygeneralized
to anyfinite number of entities who maypiece together the information to
retrieve the secret information. Herein we look at two secret-sharing schemes,
which will serve us well, especiallyin Section 5.6 when we talk about electronic
voting.
The two schemes that we describe in this section are ideas from the two
preeminent pioneers in the area, who independentlyworked out the schemes
that have found numerous applications. We begin with Shamir's idea from
1979 (see [246]). We begin bygeneralizing and formalizing the notion of secret
splitting that we have alreadyencountered.
Threshold Schemes
Let
t, w
w
, and
m
is the secret. A (
t, w
)-threshold
scheme invovles Trent computing the pieces
m
j
, for
j
=1
,
2
,...
, called
shares
(sometimes called
shadows
of
m
), among a set of
w
entities. Each
t
of the
entities can recover
m
from their shares. It is not possible for
t
∈
N
such that
t
≤
−
1 or fewer of
the entities to recover
m
using their shares.
The first question that mayarise is that of the existence of such schemes. A
mere definition does not mean theywill always exist. But in fact, theyalways do
since it can be shown that for any
t
w
and
t>
1, there exists a (
t, w
)-threshold
scheme (see [141, Theorem 1.7, page 8]). The secret splitting discussed on page
228 is an example of a (2
,
2) threshold scheme. The following is also known as
Lagrange Interpolation Scheme
. In fact, the reader must be familiar with the
Lagrange interpolation formula, Theorem A.20, given in Appendix A on page
486, as well as the notions surrounding Definition A.39 on page 490. We require
good old trusted Trent again.
≤
Shamir's Threshold Scheme
Trent distributes shares of
m
to
w
∈
N
participants of whom any
t
≤
w
of
them will be able to recover
m
.
Trent's Actions
:
1. Choose a prime
p>
max(
m, w
), where
p
is public, and set
m
0
=
m
∈
Z
/p
Z
.
2. Select
t
−
1 random integers
c
j
for
j
=1
,
2
,...,t
−
1 and set
t
−
1
t
−
1
c
j
x
j
c
j
x
j
(mod
p
)
,
≡
≡
p
(
x
)
m
+
j
=1
j
=0
Search WWH ::
Custom Search