Cryptography Reference
In-Depth Information
(1
1 of its shares is not sucient to learn all other shares. This
is because in Step 4, the value and the shares are associated with a (2
k
≤
i
≤
n
)and
k
−
−
2)-
degree polynomial (see Sect. 6.4), generated in a (2
k
1)-threshold
scheme. Consequently, the receiver cannot learn any useful information about
ω
i
(1
−
1, 2
k
−
≤
i
≤
n
,
i
=
σ
). Note that the redistribution of secrets from a (2
k
−
1
,
2
k
−
1)-
threshold scheme to a (
k
,
k
)-threshold scheme is completely secure (see Sect. 5.2)
and therefore provides the receiver with no information about
ω
1
,...,ω
n
.
Finally, in Step 5, the data held by servers
S
c
(
c
∈I
C
)arenotmodified;
The servers
S
j
∈I
k
) transmit to the receiver
k
shares of
ω
σ
, generated by a
(
k
,
k
)-threshold scheme and the receiver learns the secret
ω
σ
.Thatis,thereis
no way for the receiver to learn more than the requested secret, and thus the
following is proved.
Theorem 5.
The proposed (
k
,
m
)-DOT-
1
protocol, which is depicted in Fig.
1, is (
k
(
j
−
1
)-secure.
7.5
Eciency Considerations
In this paper, we have presented a new polynomial-based unconditionally secure
(
k
,
m
)-DOT-
1
protocol. Our result significantly improves the security of DOT
protocols. If we compare the eciency of our protocol to the eciency of the
(
k
,
m
)-DOT-
1
protocol presented in [3,4], we observe that our protocol requires
more computation on the servers' sides, but less computation on the sender and
receiver's sides, as shown in Table 1.
Table 1.
Eciency of DOT protocols
Party
Blundo et al.'s protocol
Our protocol
Sender
S
1 distribution of
n
secrets
c
0
ω
0
,...,c
n
−
1
ω
n
−
1
,
n
masks
c
0
,...,c
n
−
1
and 2
×
(
n −
1) masks
r
1
,...,r
n
−
1
,r
1
,...,r
n
−
1
1 distribution of
n
secrets
ω
1
,...,ω
n
Receiver
R
1 distribution of
n
private values (0 or
1) and 4 polynomial interpolations
1 distribution of
n
private values
δ
σi
(1
≤ i ≤ n
) and one polynomial interpolation
Server
S
(worst case)
1 generation of 2 shares from degree 1
polynomials
n
transformations from a (
k
,
k
)toa
(
k
,2
k −
1)-threshold scheme, 1
transformation from a (2
k −
1, 2
k −
1)- to a
(
k
,
k
)-threshold scheme, 1 generation of the
scalar product of 2 vectors of length
n
Acknowledgments.
We would like to thank the anonymous referees for their
helpful comments.
References
1. Beaver, D.: Multiparty protocols tolerating half faulty processors. In: Brassard,
G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 560-572. Springer, Heidelberg
(1990)
Search WWH ::
Custom Search