Cryptography Reference
In-Depth Information
secret value
δ
σi
shared thanks to a polynomial
Z
i
(1
n
), they execute
the redistribution protocol described in Sect. 5.2, and reshare that secret value
using a (
k,
2
k
≤
i
≤
1)-threshold scheme. This process is shown in Fig. 1 for vectors
of secret values. The new shares associated with a secret value
δ
σi
(1
−
≤
i
≤
n
)
are considered as generated from a new polynomial that we denote
Z
i
(we also
Φ
=(
Z
1
,...,Z
n
) the vector of sharing polynomials related to the vec-
denote
tor
Φ
=(
δ
σ
1
,...,δ
σn
) of private values). Therefore, each server
S
(
∈I
2
k−
1
)
obtains a vector
Φ
=(
Z
1
(
)
,...,Z
n
(
)) of shares of (
δ
σ
1
,...,δ
σn
).
6.4 Computation of the Requested Secret
Now, each server
S
(
∈I
2
k−
1
) holds a vector
Ω
=(
F
1
(
)
,...,F
n
(
)) as its
Φ
=(
Z
1
(
)
,...,Z
n
(
)) as its
share of the secrets (
ω
1
,...,ω
n
), and a vector
share of (
δ
σ
1
,...,δ
σn
).
The elements of the two vectors
Φ
Ω
and
are polynomials belonging to
Ω
Φ
is a polynomial of degree at most
IK
k−
1
[
X
]. It follows (Corollary 1) that
Ω
Φ
)(0) =
ω
σ
Ω
Φ
2
k
−
2, that (
and that for
i
∈I
2
k−
1
,
λ
=
is a share of
Ω
Φ
.
ω
σ
, generated by the sharing polynomial
Ω
Φ
So, each server
S
(
∈I
2
k−
1
) calculates the new share
λ
=
.Sinceat
least 2
k
1 servers participate in the computation, they redistribute the resulting
shares
λ
,(
−
∈I
2
k−
1
), thanks to a (
k
,
k
)-threshold scheme (using the method
described in Sect. 5.2), to the servers
S
j
(
j
∈I
k
).
6.5 Oblivious Transfer of the Requested Secret
After redistribution of the secret shares in the previous step, the set of contacted
servers
S
j
(
j
Ω
0
Φ
0
, under the form of
shares generated by a (
k
,
k
)-threshold scheme. Each server
S
j
(
j
∈I
k
) collectively owns the value of
∈I
k
) responds
to the receiver's request with the value
μ
j
, which is its share of
Ω
0
Φ
0
generated
from a sharing polynomial
μ
of degree at most
k
−
R
1. The receiver
interpolates
a(
k
−
1)-degree polynomial corresponding to the
k
responses, and obtains
ω
σ
.
7 Evaluation of the Protocol
In this section we demonstrate that the proposed protocol satisfies all desirable
conditions listed in [3,4] (i.e., conditions
C
1,
C
2,
C
3, and
C
4).
7.1 Correctness
We demonstrate that
μ
(0) =
ω
σ
.
The degree of the polynomial
μ
is at most
k
−
1. So, the
k
shares
μ
j
(
j
∈I
k
)
are sucient to interpolate
μ
.
The redistribution procedure, in Sect. 6.4, does not modify the shared secret.
Thus, the sharing polynomials
Ω
Φ
(before the redistribution) and
μ
(after
Ω
Φ
)(0) =
μ
(0). Because (
Ω
Φ
)(0) =
ω
σ
,
the redistribution) are such that (
it follows
μ
(0) =
ω
σ
.
Therefore, condition
C
1 is guaranteed.
Search WWH ::
Custom Search