Cryptography Reference
In-Depth Information
where
c
0
=
m
.
3. Compute
p
(
x
k
)
≡
m
k
(mod
p
) for distinct integers
x
k
≤
p
−
1 and securely
distribute the share (
x
k
,m
k
) to participant
P
k
for 1
≤
k
≤
w
.
Pooling Shares
: Without loss of generality, suppose a group of
t
partic-
ipants
P
k
for 1
≤
k
≤
t
get together and plug their shares into the Lagrange
interpolation formula:
t
t
m
k
1
x
x
k
−
x
−
f
(
x
)=
x
=
m
k
K
k
(
x
)
,
k
=1
k
=1
≤
≤
t
=
k
where
K
k
(
x
)=
1
x
x
k
−
x
−
x
.
≤
≤
t
=
k
In the analysis following, we will show that the next equation must hold:
f
(
x
i
)
≡
m
i
(mod
p
), for 1
≤
i
≤
t
(5.2)
and from it the following crucial equation must hold:
t
p
(0)
≡
f
(0)
≡
m
k
K
k
(0)
≡
m
(mod
p
)
,
(5.3)
k
=1
so the shares have been pooled to retrieve the secret.
Analysis
Verification of (5.2) and (5.3)
: To show that (5.2) is valid, we observe
that
K
k
(
x
i
)=
1
≤
≤
t
=
k
x
i
−
x
x
≡
0(mod
p
)
x
k
−
−
−
if
i
=
k
since
K
k
(
x
i
) has a factor (
x
i
x
i
)
/
(
x
k
x
i
). Also,
K
k
(
x
k
)
≡
1(mod
p
)
since all factors are of the form (
x
k
−
x
)
/
(
x
k
−
x
) = 1. We note that
x
)
−
1
(mod
p
)
,
1
/
(
x
k
−
x
)
≡
(
x
k
−
so as long as
k
=
, such inverses exist. Therefore,
t
f
(
x
i
)
≡
m
k
K
k
(
x
i
)
≡
m
i
(mod
p
)
k
=1
Search WWH ::
Custom Search