Cryptography Reference
In-Depth Information
7.2 Receiver's Privacy
Theorem 4.
The proposed (
k
,
m
)-DOT-
1
protocol, which is depicted in Fig.
1, is (
k
−
1
)-private.
Proof.
The index
σ
chosen by the receiver is represented under the form of a
vector (
δ
σ
1
,...,δ
σn
) of private values, where
δ
σi
=
i
and
δ
σi
=1if
σ
=
i
. The receiver's input to the protocol consists of shares of these values.
That is, each element
δ
σi
, which is either zero or one, is distributed amongst
the set of
k
servers
S
(
=0if
σ
∈I
k
), using Shamir's (
k
,
k
)-threshold scheme. This is
achieved by generating a vector
=(
Z
1
,...,Z
n
)of
n
quasi-random polynomials
of IK
k−
1
[
X
], such that
Z
i
(0) =
δ
σi
.
In order to breach the privacy of the receiver, a set of
k
Φ
1 colluding servers
(along the execution of the protocol, or after completion of the protocol) should
be able to determine at least one of the values
δ
σi
.Thesetof
k
−
−
1 collaborating
servers, however, owns
k
1 shares corresponding to each values
δ
σi
associated
with a Shamir's (
k
,
k
)-threshold scheme. Due to the perfectness of Shamir's
threshold scheme, every set of
k
−
1 shares provides the coalition with absolutely
no information about the relevant secret. That is, the inputs of the receiver
guarantees her privacy, during Step 2 of the protocol. Although in the next
step of the protocol, the set of
k
servers redistribute the private values
δ
σi
,to
2
k
−
−
1 servers, this transformation does not leak any information to a set of
k
1 servers (see Theorem 3). In the same way, the redistribution presented in
Sect. 6.4 preserves the privacy of the receiver.
One may argue that, after completion of the protocol, the knowledge of the
output
ω
σ
may help the set of
k
−
1 servers to determine the choice of the secret.
However, this is not the case, since the shares held by the
k
−
1serversafterthe
redistribution may be considered as generated from a (
k
,
m
)-threshold scheme,
and thus
k
−
−
1 shares of any secret provides no information about the secret.
Consequently, the condition
C
2 is guaranteed.
7.3
Sender's Security with Respect to
k −
1Serversandthe
Receiver
At the level of the servers, the role of the vector
Ω
is the same as the role of
Φ
.Thatis,asetof
k
the vector
1 colluding servers cannot learn any of the
secrets
ω
1
,...,ω
n
(see previous section). Note that, in this scenario, there is no
advantage for the coalition of
k
−
1 servers to collude with the receiver to breach
the sender's security, since the receiver has no input to contribute in this attack.
Indeed, even if the receiver initiates the protocol by contacting only
k
−
−
1servers
(no matter what her input to the
k
th
selected server is), she cannot learn any
of the secrets. This is because, the
k
1 shares she receives from the servers
are considered as generated by a (
k
,
m
)-threshold scheme, and thus provide no
information about the secrets.
−
Remark 1.
Actually, this level of security, which is expressed as condition
C
3,
is achievable easily. Our claim, however, is that the security of the sender can
Search WWH ::
Custom Search