Cryptography Reference
In-Depth Information
the members of the coalition belong to
. First, the coalition cannot interpolate
f
and calculate
f
(0) since
k
1
shares
f
(
i
) would be necessary, and the coalition
only holds
k
2
−
U
1
≤
k
1
−
1
<k
1
shares. Second, with only
k
2
−
1values
g
(
i
), and
g
being a polynomial of degree
k
2
−
1, the coalition cannot either interpolate
g
and calculate
g
(0). Consequently, a coalition of
k
2
−
1users
u
i
∈V
is unable to
gainanyinformationonthesecret
ω
.
6AS cu e
k
,
m
)-DOT-
1
Protocol
In this section we present our (
k
,
m
)-DOT-
1
protocol, which is (
k
−
1)-private
and (
k
1)-secure. Our protocol, depicted in Fig. 1, is composed of five steps,
described in the following sections.
−
6.1
Setup Phase
This step is straightforward. The sender,
, distributes the shares of the se-
crets
ω
1
,...,ω
n
amongst the servers
S
1
,...,S
m
, using Shamir's (
k
,
m
)-threshold
scheme. That is, for each secret
ω
i
S
(1
≤
i
≤
n
), the sender generates a quasi-
random polynomial
F
i
∈
IK
k−
1
[
X
] such that
k−
1
f
i,j
X
j
+
ω
i
,
F
i
=
where
f
i,j
∈
R
IK
,
1
≤
i
≤
n,
1
≤
j
≤
k
−
1
,
j
=1
and computes the shares of
ω
i
for all servers
S
(
∈I
m
). Then,
S
transmits to
each server
S
the vector
Ω
=(
F
1
(
)
,...,F
n
(
)). The sender does not intervene
in the rest of the protocol.
6.2
Elaboration of the Receiver's Requests
The receiver,
R
, chooses the index
σ
of the secret she wishes to obtain, as well
I
k
⊂I
m
of
k
indices of the servers she intends to contact. Then, the
receiver generates
n
quasi-random polynomials
Z
i
∈
as a subset
IK
k−
1
[
X
] such that
k−
1
z
i,j
X
j
+
δ
σi
,
Z
i
=
where
z
i,j
∈
R
IK
,
1
≤
i
≤
n,
1
≤
j
≤
k
−
1
,
j
=1
and transmits to each server
S
(
∈I
k
) the vector
Φ
=(
Z
1
(
)
,...,Z
n
(
)).
6.3
Redistribution of the Receiver's Input
In this step the
k
contacted servers, which have received from
shares gen-
erated by a (
k
,
k
)-threshold scheme, redistribute them as shares considered as
generated by a (
k
,2
k
R
−
1)-threshold scheme. To perform this redistribution,
the servers
S
(
∈I
k
) select a subset
I
2
k−
1
⊂I
m
of servers. Then for every
Search WWH ::
Custom Search