Cryptography Reference
In-Depth Information
Thus, the receiver knows
f
−
1
(
y
i
)=
x
i
, but cannot predict
α
b
(
f
−
1
=
i
. Of course, the last assertion presumes
that the receiver follows the protocol (i.e., is semi-honest).
Step S2
:
Upon receiving (
y
1
,y
2
, ..., y
k
), using the inverting-with-
trapdoor algorithm and the trapdoor
t
, the sender computes
z
j
=
f
−
1
(
y
j
)) for any
j
α
. It sends the
k
-tuple
(
σ
1
⊕ b
(
z
1
)
,σ
2
⊕ b
(
z
2
)
, ..., σ
k
⊕ b
(
z
k
)) to the receiver.
Step R2
(
y
j
), for every
j
∈{
1
, ..., k
}
α
:
Upon receiving (
c
1
,c
2
, ..., c
k
), the receiver locally outputs
c
i
⊕
b
(
x
i
).
We first observe that the above protocol correctly computes 1-out-of-
k
Oblivious Transfer; that is, the receiver's local output (i.e.,
c
i
⊕
b
(
x
i
))
b
(
f
−
1
indeed equals (
σ
i
⊕
b
(
x
i
)=
σ
i
. Next, we offer some
intuition as to why the above protocol constitutes a privately-secure
implementation of 1-out-of-
k
Oblivious Transfer. Intuitively, the sender
gets no information from the execution because, for any possible value
of
i
, the sender sees the same distribution; specifically, a sequence of
k
uniformly and independently distributed elements of
D
α
. (Indeed, the
key observation is that applying
f
α
to a uniformly distributed element
of
D
α
yields a uniformly distributed element of
D
α
.) Intuitively, the
receiver gains no computational knowledge from the execution because,
for
j
(
f
α
(
x
i
))))
⊕
α
=
i
, the only information that the receiver has regarding
σ
j
is
the triplet (
α, x
j
,σ
j
⊕ b
(
f
−
α
(
x
j
))), where
x
j
is uniformly distributed
in
D
α
, and from this information it is infeasible to predict
σ
j
better
than by a random guess. The latter intuition presumes that sampling
D
α
is trivial (i.e., that there is an easily computable correspondence
between the coins used for sampling and the resulting sample), whereas
in general the coins used for sampling may be hard to compute from the
corresponding outcome (which is the reason that an enhanced hardness
assumption is used in the general analysis of the the above protocol).
(See (67, Sec. 7.3.2) for a detailed proof of security.)
7.3.2
Compilation of passively-secure protocols into actively-
secure ones
We show how to transform any passively-secure protocol into a corre-
sponding actively-secure protocol. The communication model in both
