Cryptography Reference
In-Depth Information
2. For each
j
=1
,
2
,...,t
, select
n
(
j
1
,...,n
(
j
)
∈
F
p
at random and set
t
−
1
t
−
1
n
(
j
i
m
i
(mod
p
)
.
c
j
≡
m
t
−
i
=1
t
p
as
3. Each of the
t
participants is given the equation for a hyperplane in
F
follows:
t
−
1
n
(
j
i
x
i
−
x
t
≡−
c
j
(mod
p
)
,
i
=1
for
j
=1
,
2
,...,t
, where the intersection of the
t
hyperplanes must be the
point
m
.
Pooling Stage
: The participants convene to recover the secret message as
follows. In matrix terminology, the pooling of their equations translates into
the following:
n
(1)
1
n
(1)
2
n
(1)
t
···
−
1
x
1
x
2
.
.
.
x
t
−
c
1
−
1
n
(2)
1
n
(2)
2
n
(2)
t
≡
−
c
2
.
.
.
−
···
−
1
−
1
AX
≡
(mod
p
)
.
(5.4)
.
.
.
.
.
.
.
.
.
.
.
.
c
t
n
(
t
)
1
n
(
t
)
2
n
(
t
)
t
−
···
−
1
1
It follows from Theorem A.26 on page 494 that, if det(
A
)
= 0, then there is the
unique solution,
X
=(
m
1
,...,m
t
)
,
so the secret
m
1
is recovered.
= 0 in (5.4), if
we choose
p
large enough, then it is highlyprobable that
A
is indeed invert-
ible. Shamir's method is essentiallya special case of the Blakelymethod since
Shamir's method effectivelydeals with a Vandermonde matrix (see page 494)
for
A
, the determinant of which is zero if and onlyif some
x
k
≡
Analysis
: Although we cannot be certain that det(
A
)
x
i
(mod
p
), but
we chose these values to be distinct in step 3 of the algorithm. This gives
Shamir's method an advantage over Blakely's method. Moreover, Shamir's
method clearlyrequires each participant to have less information in their re-
spective shares.
When we look to applications involving electronic elections in the next sec-
tion, secret-sharing schemes will playa role. It is one of the highlyimportant
modern-dayapplications of crptographic protocols to ensure a secure and le-
gitimate voting process in a free society.
Search WWH ::
Custom Search