Efficient Fully-Simulatable Oblivious Transfer^{∗}

Yehuda Lindell^{†}

Department of Computer Science Bar-Ilan University, Israel.

                           lindell@cs.biu.ac.il

Abstract

Oblivious transfer, first introduced by Rabin, is one of the basic building blocks of cryptographic protocols. In an oblivious transfer (or more exactly, in its 1-out-of-2 variant), one party known as the sender has a pair of messages and the other party known as the receiver obtains one of them. Somewhat paradoxically, the receiver obtains exactly one of the messages (and learns nothing of the other), and the sender does not know which of the messages the receiver obtained. Due to its importance as a building block for secure protocols, the efficiency of oblivious transfer protocols has been extensively studied. However, to date, there are almost no known oblivious transfer protocols that are secure in the presence of malicious adversaries under the real/ideal model simulation paradigm (without using general zero-knowledge proofs). Thus, efficient protocols that reach this level of security are of great interest. In this paper we present efficient oblivious transfer protocols that are secure according to the ideal/real model simulation paradigm. We achieve constructions under the DDH, Nth residuosity and quadratic residuosity assumptions, as well as under the assumption that homomorphic encryption exists.

1 Introduction

In an oblivious transfer, a sender with a pair of strings m_{0}, m_{1} interacts with a receiver so that at the end the receiver learns exactly one of the strings, and the sender learns nothing [27, 12]. This is a somewhat paradoxical situation because the receiver can only learn one string (thus the sender cannot send both) whereas the sender cannot know which string the receiver learned (and so the receiver cannot tell the sender which string to send). Surprisingly, it is possible to achieve oblivious transfer under a wide variety of assumptions and adversary models [12, 16, 20, 24, 1, 18].

Oblivious transfer is one of the most basic and widely used protocol primitives in cryptography. It stands at the center of the fundamental results on secure two-party and multiparty computation showing that any efficient functionality can be securely computed [28, 16]. In fact, it has even been shown that oblivious transfer is complete, meaning that it is possible to securely compute any efficient function if given a box that computes oblivious transfer [19]. Thus, oblivious transfer has great importance to the theory of cryptography. In addition to this, oblivious transfer has been widely used to construct efficient protocols for problems of interest (e.g., it is central to almost all of the work on privacy-preserving data mining).

∗An extended abstract of this work appeared at CT-RSA 2008.

†Most of this work was carried out for Aladdin Knowledge Systems.

Due to its general importance, the task of constructing efficient oblivious transfer protocols has attracted much interest. In the semi-honest model (where adversaries follow the protocol specification but try to learn more than allowed by examining the protocol transcript), it is possible to construct efficient oblivious transfer from (enhanced) trapdoor permutations [12] and homomorphic encryption [20, 1]. However, the situation is significantly more problematic in the malicious model where adversaries may arbitrarily deviate from the protocol specification. One possibility is to use the protocol compiler of Goldreich, Micali and Wigderson [16] to transform oblivious transfer protocols for semi-honest adversaries into protocols that are also secure in the presence of malicious adversaries. However, the result would be a highly inefficient protocol. The difficulties in obtaining secure oblivious transfer in this model seem to be due to the strict security requirements of simulation-based definitions that follow the ideal/real model paradigm.^{1} Thus, until recently, the only known oblivious transfer protocols that were secure under this definition, and thus were fully simulatable, were protocols that were obtained by applying the compiler of [16]. In contrast, highlyefficient oblivious transfer protocols that guarantee privacy (but not simulatability) in the presence of malicious adversaries have been constructed. These protocols guarantee that even a malicious sender cannot learn which string the receiver learned, and that a malicious receiver can learn only one of the sender’s input strings. Highly efficient protocols have been constructed for this setting under the DDH and N-residuosity assumptions and using homomorphic encryption [20, 24, 1, 18].

This current state of affairs is highly unsatisfactory. The reason for this is that oblivious transfer is often used as a building block in other protocols. However, oblivious transfer protocols that only provide privacy are difficult – if not impossible – to use as building blocks. Thus, the vast number of protocols that assume (fully simulatable) oblivious transfer do not have truly efficient instantiations today. For example, this is true of the protocol of [21] that in turn is used in the protocol of [2] for securely computing the median. The result is that [2] has no efficient instantiation, even though it is efficient when ignoring the cost of the oblivious transfers. We conclude that the absence of efficient fully-simulatable oblivious transfer acts as a bottleneck in numerous other protocols.

Our results. In this paper, we construct oblivious transfer protocols that are secure (i.e., fullysimulatable) in the presence of malicious adversaries. Our constructions build on those of [24, 1, 18] and use cut-and-choose techniques. It is folklore that the protocols of [24, 1, 18] can be modified to yield full simulatability by adding proofs of knowledge. To some extent, this is what we do. However, a direct application of proofs of knowledge does not work. This is because the known efficient protocols are all information-theoretically secure in the presence of a malicious receiver. This means that only one of the sender’s inputs is defined by the protocol transcript and thus a standard proof of knowledge cannot be applied. Therefore, without modifying the protocol in any way, we do not know how to have the sender prove that its message is “well formed”. Of course, it is always possible to follow the GMW paradigm [16] and have the sender prove that it behaved honestly according to some committed input and committed random tape, but this will not be efficient at all. We therefore modify the underlying protocol in a way that enables an efficient proof of good behavior. Our proof uses cut-and-choose techniques because the statement being proved is compound (relating to two different Diffie-Hellman type tuples), and so direct zero-knowledge proofs would be less efficient. Our protocols yield full simulatability and we provide a full proof of security.

1According to this paradigm, a real execution of a protocol is compared to an ideal execution in which a trusted third party receives the parties’ inputs and sends them their outputs.

As we show, our protocols are in the order of ℓ times the complexity of the protocols of [24, 1, 18], where ℓ is such that the simulation fails with probability 2^{−ℓ+2}. Thus, ℓ can be taken to be relatively small (say, in the order of 30 or 40). This is a considerable overhead. However, our protocols are still by far the most efficient known without resorting to a random oracle.

Related work. There has been much work on efficient oblivious transfer in a wide range of settings. However, very little has been done regarding fully-simulatable oblivious transfer that is also efficient (without using random oracles). Despite this, recently there has been some progress in this area. In [6], fully simulatable constructions are presented. However, these rely on strong and relatively non-standard assumptions (q-power DDH and q-strong Diffie-Hellman). Following this, protocols were presented that rely on the Decisional Bilinear Diffie-Hellman assumption [17]. Our protocols differ from those of [6] and [17] in the following ways:

1. Assumptions: We present protocols that can be constructed assuming that DDH is hard, that there exist homomorphic encryption schemes, and more. Thus, we rely on far more standard and long-standing hardness assumptions.

2. Complexity: Regarding the number of exponentiations, it appears that our protocols are of a similar complexity to [6, 17]. However, as pointed out in [11], bilinear curves are considerably more expensive than regular Elliptic curves. Thus, the standard decisional Diffie-Hellman assumption is much more efficient to use (curves that provide pairing need keys that are similar in size to RSA, in contrast to regular curves that can be much smaller).

3. The problem solved: We solve the basic 1-out-of-2 oblivious transfer problem, although our protocols can easily be extended to solve the static k-out-of-n oblivious transfer problem (where static means that the receiver must choose which k elements it wishes to receive at the onset). In contrast, [6] and [17] both solve the considerably harder problem of adaptive k-out-of-n oblivious transfer where the receiver chooses the elements to receive one at a time, and can base its choice on the elements it has already received.

In conclusion, if adaptive k-out-of-n oblivious transfer is needed, then [6, 17] are the best solutions available. However, if (static) oblivious transfer suffices, then our protocols are considerably more efficient and are based on far more standard assumptions.

Subsequently to this work, a highly efficient oblivious transfer protocol was presented in [26]. Their work assumes a common reference string and achieves universal composability, in contrast to the plain model and stand-alone security as considered by us. We remark that their protocol can be transformed into one that is secure in the stand-alone model without a common reference string by running a coin-tossing protocol to generate the reference string.

2 Definitions

In this section we present the definition of security for oblivious transfer, that is based on the general simulation-based definitions for secure computation; see [15, 22, 5, 7]. We refer the reader to [13, Chapter 7] for full definitions, and provide only a brief overview here. Since we only consider oblivious transfer in this paper, our definitions are tailored to the secure computation of this specific function only.

Preliminaries. We denote by s ∈_{R} S the process of randomly choosing an element s from a set S. A function μ(·) is negligible in n, or just negligible, if for every positive polynomial p(·) and all sufficiently large n’s it holds that μ(n) < 1/p(n). A probability ensemble X = {X(n, a)}_{a∈{0,1}^{∗};n∈N} is an infinite sequence of random variables indexed by a and n ∈ N. (The value a will represent the parties’ inputs and n the security parameter.) Two distribution ensembles X = {X(n, a)}_{n∈N} and Y = {Y (n, a)}_{n∈N} are said to be computationally indistinguishable, denoted X ≡^{c} Y, if for every non-uniform polynomial-time algorithm D there exists a negligible function μ(·) such that for every a ∈ {0, 1}^{∗},

|Pr[D(X(n, a), a) = 1] − Pr[D(Y (n, a), a) = 1]| ≤ μ(n)

All parties are assumed to run in time that is polynomial in the security parameter. (Formally, each party has a security parameter tape upon which that value 1^{n} is written. Then the party is polynomial in the input on this tape.)

Oblivious transfer. The oblivious transfer functionality is formally defined as a function f with two inputs and one output. The first input is a pair (m_{0}, m_{1}) and the second input is a bit σ. The output is the string m_{σ}. Party P_{1}, also known as the sender, inputs (m_{0}, m_{1}) and receives no output. In contrast, party P_{2}, also known as the receiver, inputs the bit σ and receives m_{σ} for output. Formally, we write f((m_{0}, m_{1}), σ) = (λ, m_{σ}) where λ denotes the empty string. Stated in words, in the oblivious transfer functionality party P_{1} receives no output, whereas party P_{2} receives m_{σ} (and learns nothing about m_{1−σ}).

Adversarial behavior. Loosely speaking, the aim of a secure two-party protocol is to protect an honest party against dishonest behavior by the other party. In this paper, we consider malicious adversaries who may arbitrarily deviate from the specified protocol. Furthermore, we consider the static corruption model, where one of the parties is adversarial and the other is honest, and this is fixed before the execution begins.

Security of protocols (informal). The security of a protocol is analyzed by comparing what an adversary can do in the protocol to what it can do in an ideal scenario that is secure by definition. This is formalized by considering an ideal computation involving an incorruptible trusted third party to whom the parties send their inputs. The trusted party computes the functionality on the inputs and returns to each party its respective output. Loosely speaking, a protocol is secure if any adversary interacting in the real protocol (where no trusted third party exists) can do no more harm than if it was involved in the above-described ideal computation.

Oblivious transfer in the ideal model. An ideal oblivious transfer execution proceeds as follows:

Inputs: Party P_{1} obtains an input pair (m_{0}, m_{1}) with |m_{0}| = |m_{1}|, and party P_{2} obtains an input bit σ.

Send inputs to trusted party: An honest party always sends its input unchanged to the trusted party. A malicious party may either abort, in which case it sends ⊥ to the trusted party, or send some other input to the trusted party.

Trusted party computes output: If the trusted party receives ⊥ from one of the parties, then it sends ⊥ to both parties and halts. Otherwise, upon receiving some (m′_{0}, m′_{1}) from P_{1} and a bit σ′ from P_{2}, the trusted party sends m′_{σ′} to party P_{2} and halts.

Outputs: An honest party always outputs the message it has obtained from the trusted party (⊥ or nothing in the case of P_{1}, and ⊥ or m′_{σ′} in the case of P_{2}). A malicious party may output an arbitrary (probabilistic polynomial-time computable) function of its initial input and the message obtained from the trusted party.

Denote by f the oblivious transfer functionality and let \overline{M} = (M_{1}, M_{2}) be a pair of non-uniform probabilistic expected polynomial-time machines (representing parties in the ideal model). Such a pair is admissible if for at least one i ∈ {1, 2} we have that M_{i} is honest (i.e., follows the honest party instructions in the above-described ideal execution). Then, the joint execution of f under \overline{M} in the ideal model (on input ((m_{0}, m_{1}), σ)), denoted ideal_{f,\overline{M}}((m_{0}, m_{1}), σ), is defined as the output pair of M_{1} and M_{2} from the above ideal execution.

Execution in the real model. We next consider the real model in which a real two-party protocol is executed and there exists no trusted third party. In this case, a malicious party may follow an arbitrary feasible strategy; that is, any strategy implementable by non-uniform probabilistic polynomial-time machines. Let π be a two-party protocol. Furthermore, let \overline{M} = (M_{1}, M_{2}) be a pair of non-uniform probabilistic polynomial-time machines (representing parties in the real model). Such a pair is admissible if for at least one i ∈ {1, 2} we have that M_{i} is honest (i.e., follows the strategy specified by π). Then, the joint execution of π under \overline{M} in the real model (on input ((m_{0}, m_{1}), σ)), denoted real_{π,\overline{M}}((m_{0}, m_{1}), σ), is defined as the output pair of M_{1} and M_{2} resulting from the protocol interaction.

Security as emulation of a real execution in the ideal model. Having defined the ideal and real models, we can now define security of protocols. Loosely speaking, the definition asserts that a secure two-party protocol (in the real model) emulates the ideal model (in which a trusted party exists). This is formulated by saying that admissible pairs in the ideal model are able to simulate admissible pairs in an execution of a secure real-model protocol.

Definition 1 Let f denote the oblivious transfer protocol and let π be a two-party protocol. Protocol π is said to be a secure oblivious transfer protocol if for every pair of admissible non-uniform probabilistic polynomial-time machines \overline{A} = (A_{1}, A_{2}) for the real model, there exists a pair of admissible non-uniform probabilistic expected polynomial-time machines \overline{B} = (B_{1}, B_{2}) for the ideal model, such that for every m_{0}, m_{1} ∈ {0, 1}^{∗} of the same length and every σ ∈ {0, 1},

\{ideal_{f,\overline{B}}(n, (m_{0}, m_{1}), σ)\} ≡^{c} \{real_{π,\overline{A}}(n, (m_{0}, m_{1}), σ)\}

Note that we allow the ideal adversary/simulator to run in expected (rather than strict) polynomial-time. This is essential for achieving constant-round protocols; see [4].

3 Oblivious Transfer Under the DDH Assumption

In this section we present an oblivious transfer protocol that is secure in the presence of malicious adversaries, under the DDH assumption. The protocol is a variant of the two-round protocol of [24] with some important changes. Before proceeding, we recall the protocol of [24]. Basically, this protocol works by the receiver generating a tuple (g^{a}, g^{b}, g^{c}, g^{d}) with the following property: if the receiver’s input equals 0 then c = ab and d is random, and if the receiver’s input equals 1 then d = ab and c is random. The sender receives this tuple and carries out a manipulation that randomizes the tuple so that if c = ab then the result of the manipulation on (g^{a}, g^{b}, g^{c}) is still a DDH tuple and the result of the manipulation on (g^{a}, g^{b}, g^{d}) yields a completely random tuple (if d = ab then the same holds in reverse). The sender then derives a secret key from the manipulation of each of (g^{a}, g^{b}, g^{c}) and (g^{a}, g^{b}, g^{d}), and sends information that enables the receiver to derive the same secret key from the DDH tuple, whereas the key from the non-DDH tuple remains completely random. In addition, the sender encrypts its first message under the key derived from (g^{a}, g^{b}, g^{c}) and its second message under the key derived from (g^{a}, g^{b}, g^{d}). The receiver is able to decrypt the message derived from the DDH tuple but has no information about the other key and so cannot learn anything about the other message. We remark that the sender checks that g^{c} ≠ g^{d}. This ensures that only one of (g^{a}, g^{b}, g^{c}) and (g^{a}, g^{b}, g^{d}) is a DDH tuple. We describe the protocol in more detail in Appendix A.

The secret key that is derived from the non-DDH tuple above is information-theoretically hidden from the receiver. This causes a problem when attempting to construct a simulator for the protocol because the simulator must learn both of the sender’s inputs in order to send them to the trusted party (and for whatever first message the simulator sends, it can only learn one of the sender’s inputs). We remark that if rewinding is used to obtain both messages then this causes a problem because the sender can make its input depend on the first message from the receiver. We therefore change the protocol of [24] so that instead of sending (g^{a}, g^{b}, g^{c}, g^{d}) where at most one of c or d equals a · b, the receiver sends two tuples: one of the tuples is a DDH type and the other is not. The parties then interact to ensure that indeed only one of the tuples is of the DDH type. As we will see, this ensures that the receiver obtains only one message. The “interaction” used to prove this is of the simplest cut-and-choose type.

The protocol below uses two commitment schemes for the purpose of coin tossing: a perfectly hiding commitment scheme denoted Com_{h}, and a perfectly binding commitment scheme, denoted Com_{b}. The perfectly-hiding commitment can be Pedersen’s commitment [25] and the perfectlybinding commitment can be obtained by essentially providing an El Gamal encryption [10]. Thus, these commitments can be obtained efficiently under the DDH assumption (Pedersen commitments are perfectly hiding under the Discrete Log assumption which is implied by the DDH assumption). We assume that the input values m_{0}, m_{1} of the sender are in the group G that we are working with for the DDH assumption. If they cannot be mapped to G (e.g., they are too long), then the oblivious transfer can be used to exchange secret keys k_{0} and k_{1} that are used to encrypt m_{0} and m_{1}, respectively.

Protocol 1

• Input: The sender has a pair of group elements (m_{0}, m_{1}) and the receiver has a bit σ.

• Auxiliary input: The parties have the description of a group G of order q, and a generator g for the group. In addition, they have a statistical error parameter ℓ.

• The protocol:

1. For i = 1, …, ℓ, the receiver P_{2} chooses a random bit σ_{i} ∈_{R} {0, 1} and random values a_{i}^{0}, b_{i}^{0}, c_{i}^{0}, a_{i}^{1}, b_{i}^{1}, c_{i}^{1} ∈_{R} {1, …, q} under the constraint that c_{i}^{σ_{i}} = a_{i}^{σ_{i}} · b_{i}^{σ_{i}} and c_{i}^{1−σ_{i}} ≠ a_{i}^{1−σ_{i}} · b_{i}^{1−σ_{i}}. Then, P_{2} computes the tuples γ_{i}^{0} = (g^{a_{i}^{0}}, g^{b_{i}^{0}}, g^{c_{i}^{0}}) and γ_{i}^{1} = (g^{a_{i}^{1}}, g^{b_{i}^{1}}, g^{c_{i}^{1}}). Note that γ_{i}^{σ_{i}} is a DDH tuple and γ_{i}^{1−σ_{i}} is not. P_{2} sends all of the pairs ⟨(γ_{1}^{0}, γ_{1}^{1}), …, (γ_{ℓ}^{0}, γ_{ℓ}^{1})⟩ to the sender P_{1}.

2. Coin tossing:

(a) P_{1} chooses a random s ∈_{R} {0, 1}^{ℓ} and sends Com_{h}(s) to P_{2}.

(b) P_{2} chooses a random s′ ∈_{R} {0, 1}^{ℓ} and sends Com_{b}(s′) to P_{1}.

(c) P_{1} and P_{2} send decommitments to Com_{h}(s) and Com_{b}(s′), respectively, and set r =

s ⊕ s′. Denote r = r_{1}, …, r_{ℓ}.

3. For every i for which r_{i} = 1, party P_{2} sends a_{i}^{0}, b_{i}^{0}, c_{i}^{0}, a_{i}^{1}, b_{i}^{1}, c_{i}^{1} to P_{1}.

In addition, for every j for which r_{j} = 0, party P_{2} sends a “reordering” of γ_{j}^{0} and γ_{j}^{1} so that all of the γ_{j}^{σ} tuples are DDH tuples and all of the γ_{j}^{1−σ} tuples are not. It suffices for P_{2} to send a bit b_{j} for every j, such that if b_{j} = 0 then the tuples are left as is, and if b_{j} = 1 then γ_{j}^{0} and γ_{j}^{1} are interchanged.

4. P_{1} checks that for every i for which r_{i} = 1 it received the appropriate values and that they define γ_{i}^{0} and γ_{i}^{1}. Furthermore, it checks that exactly one of γ_{i}^{0} and γ_{i}^{1} is a DDH tuple as defined above and the other is not. If any of the checks fail, P_{1} halts and outputs ⊥. Otherwise it continues as follows:

(a) Denote γ_{j}^{0} = (x_{j}^{0}, y_{j}^{0}, z_{j}^{0}) and γ_{j}^{1} = (x_{j}^{1}, y_{j}^{1}, z_{j}^{1}). Then, for every j for which r_{j} = 0, party P_{1} chooses random u_{j}^{0}, u_{j}^{1}, v_{j}^{0}, v_{j}^{1} ∈_{R} {1, …, q} and computes the following four values:

w_{j}^{0} = (x_{j}^{0})^{u_{j}^{0}} · g^{v_{j}^{0}}  k_{j}^{0} = (z_{j}^{0})^{u_{j}^{0}} · (y_{j}^{0})^{v_{i}^{0}}
w_{j}^{1} = (x_{j}^{1})^{u_{j}^{1}} · g^{v_{j}^{1}}  k_{j}^{1} = (z_{j}^{1})^{u_{j}^{1}} · (y_{j}^{1})^{v_{j}^{1}}

(b) Let j_{1}, …, j_{t} be the indices j for which r_{j} = 0. Then, P_{1} “encrypts” m_{0} under all of the keys k_{j}^{0}, and m_{1} under all of the keys k_{j}^{1}, as follows:

c_{0} =(∏_{i=1}^{t} k_{j_{i}}^{0}) · m_{0}  c_{1} = (∏_{i=1}^{t} k_{j_{i}}^{1}) · m_{1}

P_{1} sends P_{2} all of the w_{j}^{0}, w_{j}^{1} values, as well as the pair (c_{0}, c_{1}).

5. For every j for which r_{j} = 0, party P_{2} computes k_{j}^{σ} = (w_{j}^{σ})^{b_{j}^{0}}. Then, P_{2} outputs m_{σ} =

c_{σ} · (∏_{i=1}^{t} k_{j_{i}}^{σ})^{−1}.

Before proceeding to the proof, we show that the protocol “works”, meaning that when P_{1} and P_{2} are honest, the output is correctly obtained. We present this to “explain” the computations that take place in the protocol, although these are exactly as in the protocol of [24]. First, notice that

(w_{j}^{σ})^{b_{j}^{σ}} = (x_{j}^{σ})^{u_{j}^{σ}·b_{j}^{σ}} · (g^{v_{j}^{σ}})^{b_{j}^{σ}} = (g^{a_{j}^{σ}·b_{j}^{σ}})^{u_{j}^{σ}} · (g^{b_{j}^{σ}})^{v_{j}^{σ}}

By the fact that γ_{j}^{σ} is a DDH tuple we have that g^{a_{j}^{σ}·b_{j}^{σ}} = z_{j}^{σ} and so

(w_{j}^{σ})^{b_{j}^{σ}} = (z_{j}^{σ})^{u_{j}^{σ}} · (y_{j}^{σ})^{v_{j}^{σ}} = k_{j}^{σ}

Thus P_{2} correctly computes each key k_{j}^{σ} for j such that r_{j} = 0. Given all of these keys, it immediately follows that P_{2} can decrypt c_{σ}, obtaining m_{σ}. We now proceed to prove the security of the protocol.

Theorem 1 Assume that the decisional Diffie-Hellman problem is hard in G with generator g, that Com_{h} is a perfectly-hiding commitment scheme, and that Com_{b} is a perfectly-binding commitment scheme. Then, Protocol 1 securely computes the oblivious transfer functionality in the presence of malicious adversaries.

Proof: We separately prove the security of the protocol for the case that no parties are corrupted, P_{1} is corrupted, and P_{2} is corrupted. In the case that both P_{1} and P_{2} are honest, we have already seen that P_{2} obtains exactly m_{σ}. Thus, security holds. We now proceed to the other cases.

P_{1} is corrupted. Let A_{1} be a non-uniform probabilistic polynomial-time real adversary that controls P_{1}. We construct a non-uniform probabilistic expected polynomial-time ideal-model adversary/simulator S_{1}. The basic idea behind how S_{1} works is that it uses rewinding in order to ensure that all of the “checked” tuples are valid (i.e., one is a DDH tuple and the other is not), whereas all of the “unchecked” tuples have the property that they are both of the DDH type. Now, since the protocol is such that a receiver can obtain a key k_{j}^{σ} as long as γ_{j}^{σ} was a DDH tuple, it follows that S_{1} can obtain all of the k_{j}^{0} and k_{j}^{1} keys. This enables it to decrypt both c_{0} and c_{1} and obtain both messages input by A_{1} into the protocol. S_{1} then sends these inputs to the trusted party, and the honest party P_{2} in the ideal model will receive the same message that it would have received in a real execution with A_{1} (or more accurately, a message that is computationally indistinguishable from that message).

We now describe S_{1} formally. Upon input 1^{n} and a pair (m_{0}, m_{1}),^{2} the machine S_{1} invokes A_{1} upon the same input and works as follows:

1. S_{1} chooses a random r ∈_{R} {0, 1}^{ℓ} and generates tuples γ_{1}^{0}, γ_{1}^{1}, …, γ_{ℓ}^{0}, γ_{ℓ}^{1} with the following property:

(a) For every i for which r_{i} = 1, S_{1} constructs γ_{i}^{0} and γ_{i}^{1} like an honest P_{2} (i.e., one of them being a DDH tuple and the other not, in random order).

(b) For every j for which r_{j} = 0, S_{1} constructs γ_{j}^{0} and γ_{j}^{1} to both be DDH tuples.

S_{1} hands the tuples to A_{1}.

2. Simulation of the coin tossing: S_{1} simulates the coin tossing so that the result is r, as follows:

(a) S_{1} receives a commitment c_{h} from A_{1}.

(b) S_{1} chooses a random s′ ∈_{R} {0, 1}^{ℓ} and hands c_{b} = Com_{b}(s′) to A_{1}.

(c) If A_{1} does not send a valid decommitment to c_{h}, then S_{1} simulates P_{2} aborting and sends ⊥ to the trusted party. Then S_{1} outputs whatever A_{1} outputs and halts. Otherwise, let s be the decommitted value. S_{1} proceeds as follows: i. S_{1} sets s′ = r ⊕ s, rewinds A_{1}, and hands it Com_{b}(s′). ii. If A_{1} decommits to s, then S_{1} proceeds to the next step. If A_{1} decommits to a value s̃ ≠ s, then S_{1} outputs fail. Otherwise, if it does not decommit to any value, S_{1} returns to the previous step and tries again until A_{1} does decommit to s. (We stress that in every attempt, S_{1} hands A_{1} a commitment to the same value s′. However, the randomness used to generate the commitment Com_{b}(s′) is independent each time.)^{3}

2The pair (m_{0}, m_{1}) is the input received by A_{1}. However one should not confuse this with the actual values used by A_{1} which must be extracted by S_{1} in the simulation. Thus, although S_{1} invokes A_{1} upon this input, this is ignored for the rest of the simulation.

3. Upon receiving a valid decommitment to s from A_{1}, simulator S_{1} decommits to A_{1}, revealing s′. (Note that r = s ⊕ s′.)

4. For every i for which r_{i} = 1, simulator S_{1} hands A_{1} the values a_{i}^{0}, b_{i}^{0}, c_{i}^{0}, a_{i}^{1}, b_{i}^{1}, c_{i}^{1} used to generate γ_{i}^{0} and γ_{i}^{1}. In addition, S_{1} hands A_{1} a random reordering of the pairs.

5. If A_{1} does not reply with a valid message, then S_{1} sends ⊥ to the trusted party, outputs whatever A_{1} outputs and halts. Otherwise, it receives a series of pairs (w_{j}^{0}, w_{j}^{1}) for every j for which r_{j} = 0, as well as ciphertexts c_{0} and c_{1}. S_{1} then follows the instructions of P_{2} for deriving the keys. However, unlike an honest P_{2}, it computes k_{j}^{0} = (w_{j}^{0})^{b_{j}^{0}} and k_{j}^{1} = (w_{j}^{1})^{b_{j}^{1}} and uses the keys it obtains to decrypt both c_{0} and c_{1}. (Note that for each such j, both γ_{j}^{0} and γ_{j}^{1} are DDH tuples; thus this makes sense.)

Let m_{0} and m_{1} be the messages obtained by decrypting. S_{1} sends the pair to the trusted party as the first party’s input, outputs whatever A_{1} outputs and halts.

We now prove that the joint output distribution of S_{1} and an honest P_{2} in an ideal execution is computationally indistinguishable from the output distribution of A_{1} and an honest P_{2} in a real execution. First, note that the view of A_{1} in the simulation with S_{1} is indistinguishable from its view in a real execution. The only difference in its view is due to the fact that the tuples γ_{j}^{0} and γ_{j}^{1} for which r_{j} = 0 are both of the DDH type. The only other difference is due to the coin tossing (and the rewinding). However, by the binding property of the commitment sent by A_{1} and the fact that P_{2} generates its commitment after receiving A_{1}’s, we have that the outcome of the coin tossing in a real execution is statistically close to uniform (where the only difference is due to the negligible probability that A_{1} will break the computational binding property of the commitment scheme.) In the simulation by S_{1}, the outcome is always uniformly distributed, assuming that S_{1} does not output fail. Since S_{1} outputs fail when A_{1} breaks the computational binding of the commitment scheme, this occurs with at most negligible probability (a rigorous analysis of this is given in [14]). We therefore have that, apart from the negligible difference due to the coin tossing, the only difference is due to the generation of the tuples. Intuitively, indistinguishability therefore follows from the DDH assumption. More formally, this is proven by constructing a machine D that distinguishes many copies of DDH tuples from many copies of non-DDH tuples.^{4} D receives a series of tuples and runs in exactly the same way as S_{1} except that it constructs the γ_{j}^{0} and γ_{j}^{1} tuples (for r_{j} = 0) so that one is a DDH tuple and the other is from its input, in random order. Furthermore, it provides the reordering so that all of the DDH tuples it generates are associated with σ and all of the ones it receives externally are associated with 1−σ. (For the sake of this mental experiment, we assume that D is given the input σ of P_{2}.) It follows that if D receives a series of DDH tuples, then the view of A_{1} is exactly the same as in the simulation with S_{1} (because all the tuples are of the Diffie-Hellman type). In contrast, if D receives a series of non-DDH tuples, then the view of A_{1} is exactly the same as in a real execution (because only the tuples associated with σ are of the Diffie-Hellman type). This suffices for showing that the output of A_{1} in a real execution is indistinguishable from the output of S_{1} in an ideal execution (recall that S_{1} outputs whatever A_{1} outputs). However, we have to show this for the joint distribution of the output of A_{1} (or S_{1}) and the honest P_{2}. In order to see this, recall that the output of P_{2} is m_{σ} where σ is the honest P_{2}’s input. Now, assume that there exists a polynomial-time distinguisher D′ that distinguishes between the real and ideal distributions with non-negligible probability. We construct a distinguisher D as above that distinguishes DDH from non-DDH tuples. The machine D receives the input σ of P_{2} and a series of tuples that are either DDH or non-DDH tuples. D then works exactly as above (i.e., constructing the γ_{j}^{0} and γ_{j}^{1} tuples so that in the reordering step, all the γ_{j}^{σ} tuples are those it generated itself and all the γ_{j}^{1−σ} tuples are those it received as input). Since D generated all of the γ_{j}^{σ} tuples, it is able to “decrypt” c_{σ} and obtain m_{σ}. Machine D therefore does this, and invokes D′ on the output of A_{1} and the message m_{σ} (which is the output that an honest P_{2} would receive). Finally D outputs whatever D′ does. It is clear that if D receives non-DDH tuples, then the output distribution generated is exactly like that of a real execution between A_{1} and P_{2}. In contrast, if it receives DDH tuples, then the output distribution is exactly like of an ideal execution with S_{1}. (A subtle point here is that the distribution over the γ tuples generated by D who knows σ is identical to the distribution generated by S_{1} who does not know σ. The reason for this is that when all the tuples are of the DDH type, their ordering makes no difference.) We conclude that D solves the DDH problem with non-negligible probability, in contradiction to the DDH assumption. Thus, the real and ideal output distributions must be computationally indistinguishable, as required.

3This strategy by S_{1} is actually over-simplified and does not guarantee that it runs in expected polynomial-time.

This technicality will be discussed below, and we will show how S_{1} can be “fixed” so that its expected running-time is polynomial.

4The indistinguishability of many copies of DDH tuples from many copies of non-DDH tuples follows from the indistinguishability of a single copy (which is the standard DDH assumption), using a straightforward hybrid argument.

It remains to prove that S_{1} runs in expected polynomial-time. Unfortunately, this is not true! In order to see this, denote by p the probability that A_{1} decommits correctly to s when it receives a commitment to a random s′. Next, denote by q the probability that A_{1} decommits correctly when it receives a commitment to s′ = s ⊕ r. (Note that this is not random because r is implicit in the way that S_{1} generated the tuples. That is, if r_{i} = 1 then γ_{i}^{0} and γ_{i}^{1} are honestly generated, and otherwise they are both of the DDH type.) Now, by the hiding property of the commitment scheme Com_{b}, the difference between p and q can be at most negligible. Furthermore, the expected running-time of S_{1} in the rewinding stage equals p/q times some fixed polynomial factor. In order to see this, observe that S_{1} enters the rewinding stage with probability p, and concludes after an expected 1/q number of rewindings. It thus remains to bound p/q. (We remark that S_{1}’s running time in the rest of the simulation is a fixed polynomial and so we ignore this from now on). Unfortunately, even though p and q are at most negligibly far from each other, as we have discussed, the value p/q may not necessarily be polynomial. For example, if p = 2^{−n} and q = 2^{−n} + 2^{−n/2} then p/q ≈ 2^{n/2}. Thus, the expected running-time of S_{1} is not necessarily polynomial. Fortunately, this can be solved using the techniques of [14] who solved an identical problem. Loosely speaking, the technique of [14] works by first estimating p and then ensuring that the number of rewinding attempts does not exceed a fixed polynomial times the estimation of p. It is shown that this yields a simulator that is guaranteed to run in expected polynomial time. Furthermore, the output of the simulator is only negligibly far from the original (simplified) strategy described above. Thus, these techniques can be applied here and the simulator appropriately changed, with the result being that the output is only negligibly different from before, as required.

P_{2} is corrupted. As before, we let A_{2} be any non-uniform probabilistic polynomial-time adversary controlling P_{2} and we construct a non-uniform probabilistic expected polynomial-time simulator S_{2}. The simulator S_{2} extracts the bit σ used by A_{2} by rewinding it and obtaining the reordering of tuples that it had previously opened. Formally, upon input 1^{n} and some σ, the simulator S_{2} invokes A_{2} upon the same input and works as follows (note that this σ is the input received by A_{2}, but not necessarily the value that it uses in the protocol; see Footnote 2):

1. S_{2} receives a series of tuples γ_{1}^{0}, γ_{1}^{1}, …, γ_{ℓ}^{0}, γ_{ℓ}^{1} from A_{2}.

2. S_{2} hands A_{2} a commitment c_{h} = Com_{h}(s) to a random s ∈_{R} {0, 1}^{ℓ}, receives back c_{b}, decommits to c_{h} and receives A_{2}’s decommitment to c_{b}. S_{2} then receives all of the a_{i}^{0}, b_{i}^{0}, c_{i}^{0}, a_{i}^{1}, b_{i}^{1}, c_{i}^{1} values from A_{2}, for i where r_{i} = 1, and the reorderings for j where r_{j} = 0. If the values sent by A_{2} are not valid (as checked by P_{1} in the protocol) or A_{2} did not send valid decommitments, S_{2} sends ⊥ to the trusted party, outputs whatever A_{2} outputs, and halts. Otherwise, it continues to the next step.

3. S_{2} rewinds A_{2} back to the beginning of the coin-tossing, hands A_{2} a commitment c̃_{h} = Com_{h}(s̃) to a fresh random s̃ ∈_{R} {0, 1}^{ℓ}, receives back some c̃_{b}, decommits to c̃_{h} and receives A_{2}’s decommitment to c̃_{b}. In addition, S_{2} receives the a_{i}^{0}, b_{i}^{0}, c_{i}^{0}, a_{i}^{1}, b_{i}^{1}, c_{i}^{1} values and reorderings.

If any of the values are not valid, S_{2} repeats this step using fresh randomness each time, until all values are valid.

4. Following this, S_{2} rewinds A_{2} to the beginning and resends the exact messages of the first coin tossing (resulting in exactly the same transcript as before).

5. Denote by r the result of the first coin tossing (Step 2 above), and r̃ the result of the second coin tossing (Step 3 above). If r = r̃ then S_{2} outputs fail and halts. Otherwise, S_{2} searches for a value t such that r_{t} = 0 and r̃_{t} = 1. (Note that by the definition of the simulation, exactly one of γ_{t}^{0} and γ_{t}^{1} is a DDH tuple. Otherwise, the values would not be considered valid.) If no such t exists (i.e., for every t such that r_{t} ≠ r̃_{t} it holds that r_{t} = 1 and r̃_{t} = 0), then S_{2} begins the simulation from scratch with the exception that it must find r and r̃ for which all values are valid (i.e., if for r the values sent by A_{2} are not valid it does not terminate the simulation but rather rewinds until it finds an r for which the responses of A_{2} are all valid).

If S_{2} does not start again, we have that it has a_{t}^{0}, b_{t}^{0}, c_{t}^{0}, a_{t}^{1}, b_{t}^{1}, c_{t}^{1} and can determine which of γ_{t}^{0} and γ_{t}^{1} is a DDH tuple. Furthermore, since r̃_{t} = 1, the reordering that S_{2} receives from A_{2} after the coin tossing indicates whether the DDH tuple is associated with 0 or with 1. S_{2} sets σ = 0 if after the reordering γ_{t}^{0} is of the DDH type, and sets σ = 1 if after the reordering γ_{t}^{1} is of the DDH type. (Note that exactly one of the tuples is of the DDH type because this is checked in the second coin tossing.)

6. S_{2} sends σ to the trusted party and receives back a string m = m_{σ}. Simulator S_{2} then computes the last message from P_{1} to P_{2} honestly, while encrypting m_{σ} under the keys k_{j}^{σ} (and encrypting any arbitrary string of the same length under the keys k_{1−σ}^{j}). S_{2} hands A_{2} these messages and outputs whatever A_{2} outputs and halts.

We now prove that the output distribution of A_{2} in a real execution with an honest P_{1} (with input (m_{0}, m_{1})) is computationally indistinguishable from the output distribution of S_{2} in an ideal execution with an honest P_{1} (with the same input (m_{0}, m_{1})). We begin by showing that S_{2} outputs fail with probability at most 2^{−ℓ}, ignoring for now the probability that r = r̃ in later rewindings (which may occur if S_{2} has to start again from scratch). Recall that this event occurs if everything is “valid” after the first coin tossing (where the result is r), and the result of the second coin-tossing after which everything is valid is r̃ = r.^{5} First, observe that the distributions of the strings r and r̃ are identical. This is because S_{2} runs the coin tossing in the same way each time (using fresh random coins), and accepts r̃ when all is valid, exactly as what happened with r. Next, note that the distribution over the result of the coin tossing – without conditioning over A_{2} sending valid decommitments – is uniform. This holds because the commitment that S_{2} hands to A_{2} is perfectly hiding and the commitment returned by A_{2} to S_{2} is perfectly binding. Let R be a random variable that denotes the result of the first coin tossing between A_{2} and S_{2} in the simulation, and let valid be the event that A_{2} replies with valid decommitments and values after the first coin tossing. Finally, for a given r ∈ {0, 1}^{ℓ}, let obtain_{r} denote the event that the result of one of the coin tossing attempts in the second stage equals r. (Note that this does not mean that r̃ = r because r̃ is the result that is finally accepted after A_{2} sends valid values. However, the decision of A_{2} to send valid values may also depend on the randomness used to generate Com_{h}(s). Thus, r̃ may not equal r, even though r is obtained in one of the coin tossing attempts in the second stage.) Clearly, fail can only occur if r is obtained at least once as the result of a coin tossing attempt in the second stage (because fail can only occur if r̃ = r). We therefore have the following:

Pr[fail] ≤ ∑_{r∈{0,1}^{ℓ}} Pr[R = r & valid] · Pr[obtain_{r}]  (1)

Before analyzing this probability, we compute Pr[obtain_{r}] for a fixed r. Let p denote the probability (over A_{2} and S_{2}’s coin tosses) that A_{2} sends valid values after the coin tossing. It follows that the expected number of trials by S_{2} in the second coin tossing is 1/p. Letting X_{r} be a Boolean random variable that equals 1 if and only if the result of the second coin tossing attempt equals the fixed r, we have that E[X_{r}] = 2^{−ℓ}. By Wald’s equation (e.g., see [23, Page 300]), it follows that the expected number of times that r is obtained as the result of a coin tossing attempt in the second stage by S_{2} is 1/p · 2^{−ℓ}. Using Markov’s inequality, we have that the probability that r is obtained at least once as the result of a coin tossing attempt in the second stage is at most 1/p · 2^{−ℓ}. That is:

Pr[obtain_{r}] ≤ \frac{1}{p · 2^{ℓ}}

We are now ready to return to Eq. (1). Denote by p_{r} the probability that A_{2} sends valid values conditioned on the outcome of the coin tossing being r. It follows that

p = ∑_{r∈\{0,1\}^{ℓ}} Pr[R = r] · p_{r} = ∑_{r∈\{0,1\}^{ℓ}} \frac{p_{r}}{2^{ℓ}}

Furthermore,

5It is very easy to prove that the probability that S_{2} outputs fail is at most 2^{−ℓ/2}. However, in order to keep ℓ to a low value, we present a more subtle analysis that demonstrates that S_{2} outputs fail with probability at most 2^{−ℓ}.

Pr[R = r & valid] = Pr[valid | R = r] · Pr[R = r] = p_{r} · \frac{1}{2^{ℓ}}

Combining the above, we have:

Pr[fail] ≤ ∑_{r∈{0,1}^{ℓ}} Pr[R = r & valid] · Pr[obtain_{r}]

≤ ∑_{r∈\{0,1\}^{ℓ}} \frac{p_{r}}{2^{ℓ}} · \frac{1}{p · 2^{ℓ}}

= \frac{1}{p · 2^{ℓ}} · ∑_{r∈\{0,1\}^{ℓ}} \frac{p_{r}}{2^{ℓ}}

= \frac{1}{p · 2^{ℓ}} · p = \frac{1}{2^{ℓ}}

We conclude that S_{2} outputs fail with probability at most 2^{−ℓ}, as required. Recall that this analysis doesn’t take into account the probability that S_{2} starts the simulation from scratch. Rather, it just shows that S_{2} outputs fail in any simulation attempt (between starts from scratch) with probability at most 2^{−ℓ}. Below, we will show that the probability that S_{2} starts from scratch is at most 1/2. Denote by fail_{i} the probability that S_{2} outputs fail in the ith attempt, given that there is such an attempt. Likewise, denote by repeat_{i} the probability that S_{2} has an ith attempt. We have shown that for every i, Pr[fail_{i}] = 2^{−ℓ}, and below we show that every repeat happens with probability 1/2 and so for every i, Pr[repeat_{i}] = 2^{i−1} (repeat_{1} = 1 because we always have one attempt). We therefore have:

Pr[fail] = ∑_{i=1}^{∞} Pr[fail_{i}] · Pr[repeat_{i}] = \frac{1}{2^{ℓ}} ∑_{i=1}^{∞} \frac{1}{2^{i−1}} = \frac{1}{2^{ℓ}} · 2 = \frac{1}{2^{ℓ−1}}

Given the above, we proceed to show indistinguishability of the ideal and real distributions. Notice that in the case that S does not output fail, the final transcript as viewed by A_{2} consists of the first coin tossing (that is distributed exactly as in a real execution) and the last message from S_{2} to A_{2}. This last message is not generated honestly, in that c_{σ} is indeed an encryption of m_{σ}, but c_{1−σ} is an encryption of an arbitrary value (and not necessarily of m_{1−σ}). However, as shown in [24], for any tuple γ_{j}^{1−σ} that is not a DDH tuple, the value k_{j}^{1−σ} is uniformly distributed in G (even given w_{j}^{1−σ} as received by A_{2}). This implies that c_{1−σ} is uniformly distributed, independent of the value m_{1−σ}. Thus, A_{2}’s view in the execution with S_{2} is statistically close to its view in a real execution with P_{1} (the only difference being if S_{2} outputs fail). This completes the proof regarding indistinguishability.

It remains to prove that S_{2} runs in expected polynomial-time. We begin by analyzing the rewinding by S_{2} in the coin tossing phase (clearly, the running-time of S_{2} outside of the rewinding is strictly polynomial, and so it suffices to bound the expected number of rewinding attempts). Denote by p the probability that A_{2} completes the coin tossing phase and provides valid values to S_{2}. The important point to note here is that each rewinding attempt is successful with probability exactly p (there is no difference between the distribution over the first and second coin tossing attempts, in contrast to the simulation where P_{1} is corrupted). Thus, with probability p there are rewinding attempts, and in such a case there are an expected 1/p such attempts. This yields an expected number of rewindings of 1. We now analyze the number of times that S_{2} is expected to have to begin from scratch (due to there being no t for which r_{t} = 0 and r̃_{t} = 1). The main observation here is that for any pair r and r̃ which forces S_{2} to begin from scratch, interchanging r and r̃ would result in a pair for which S_{2} would be able to continue. Now, since r and r̃ are derived through independent executions of the coin tossing phase, the probability that they are in one order equals the probability that they are in the opposite order. Thus, the probability that S_{2} needs to start from scratch equals at most 1/2. This implies that the expected number of times that S_{2} needs to start from scratch is at most two. We remark that when S_{2} starts from scratch, the expected number of times it needs to rewind in order to obtain each of r and r̃ is 1/p. Thus, overall the expected number of rewinding attempts is p · O(1)/p = O(1). We conclude that the overall expected running time of S_{2} is polynomial, as required.

Efficiency. The complexity of the protocol is in the order of ℓ times the computation of the basic protocol of [24]. Thus, the efficiency depends strongly on the value of ℓ that is taken. It is important to notice that the simulation succeeds except with probability ≈ 2^{−ℓ+1} (as long as the cryptographic primitives are not “broken”). To be more exact, one should take ℓ and n so that the probability of “breaking” the cryptographic primitives (the commitments for the coin tossing or the security of encryption) is at most 2^{−ℓ+1}. In such a case, our analysis in the proof shows that the ideal and real executions can be distinguished with probability at most 2^{−ℓ+2}. This means that ℓ can be chosen to be relatively small, depending on the level of security desired. Specifically, with ℓ = 30 the probability of successful undetected cheating is 2^{−28} ≈ 3.7 × 10^{−9} which is already very very small. Thus, it is reasonable to say that the complexity of the protocol is between 30 and 40 times of that of [24]. This is a non-trivial price; however, this is far more efficient than known solutions. The number of rounds of communication in our protocol is 6, which is constant but more than the 2 rounds of communication in the protocol of [24]. This is inevitable for achieving full simulation (and also far less significant than the additional computation discussed above).

We remark that higher efficiency can be achieved using similar ideas, if it suffices to achieve security in the model of covert adversaries of [3]. In this model, a protocol must have the property that if the adversary can cheat, then it will be caught cheating with some guaranteed probability ϵ. This value ϵ is called the deterrence factor because the higher ϵ is the greater the deterrent from cheating is. Now, in order to achieve deterrent factor of ϵ = 1/2 one can use ℓ = 2 in our protocol and have the sender choose r singlehandedly with one bit of r equalling 0 and the other equalling 1. This yields very high efficiency, together with simulatability (albeit in the weaker model of covert adversaries).

4 Oblivious Transfer using Smooth Hashing

The protocol of [24] was generalized by [18] via the notion of smooth projective hashing of [8]. This enables the construction of oblivious transfer protocols that are analogous to [24] under the Nth residuosity and quadratic residuosity assumptions. Protocol 1 can be extended directly in the same way, yielding oblivious transfer protocols that are secure against malicious adversaries, under the Nth residuosity and quadratic residuosity assumptions. (Note that the commitment schemes must also be replaced and this also has an effect on efficiency.) We remark that as in the protocol of [18], the instantiation of the protocol under the Nth residuosity assumption is still efficient, whereas the instantiation under the quadratic residuosity assumption enables the exchange of a single bit only (but is based on a longer-standing hardness assumption). We remark, however, that using Elliptic curves, the solution based on the DDH assumption is by far the most efficient.

5 Oblivious Transfer from Homomorphic Encryption

In this section, we present a protocol based on the protocol of [1] that uses homomorphic encryption. We assume an additive homomorphic encryption scheme (G, E, D), where G(1^{n}) outputs a key-pair of length n, E is the encryption algorithm and D the decryption algorithm. Note that additive homomorphic operations imply multiplication by a scalar as well. The ideas behind this protocol are similar to above, and our presentation is therefore rather brief.

Protocol 2

• Input: The sender has a pair of strings (m_{0}, m_{1}) of known length and the receiver has a bit σ. Both parties have a security parameter n determining the length of the keys for the encryption scheme, and a separate statistical security parameter ℓ.

• The protocol:

1. Receiver’s message:

(a) The receiver P_{2} chooses a key-pair (pk, sk) ← G(1^{n}) from a homomorphic encryption scheme (G, E, D).^{6}

(b) For i = 1, …, ℓ, party P_{2} chooses a random bit b_{i} ∈_{R} {0, 1} and defines

c_{i}^{b_{i}} = E_{pk}(0; r_{i}^{b_{i}}) and c_{i}^{1−b_{i}} = E_{pk}(1; r_{i}^{1−b_{i}}) .

where r_{i}^{0} and r_{i}^{1} are random strings, and E_{pk}(x; r) denotes an encryption of message x using random coins r.

(c) P_{2} sends pk, ⟨c_{1}^{0}, c_{1}^{1}, …, c_{ℓ}^{0}, c_{ℓ}^{1}⟩ to P_{1}.

2. Coin tossing:

(a) P_{1} chooses a random s̃ ∈_{R} {0, 1}^{ℓ} and sends Com_{h}(s̃) to P_{2}.

(b) P_{2} chooses a random ŝ ∈_{R} {0, 1}^{ℓ} and sends Com_{b}(ŝ) to P_{1}.

(c) P_{1} and P_{2} send decommitments to Com_{h}(s̃) and Com_{b}(ŝ), respectively, and set s = s̃⊕ŝ. Denote s = s_{1}, …, s_{ℓ}. Furthermore let S_{1} be the set of all i for which s_{i} = 1, and let S_{0} be the set of all j for which s_{j} = 0. (Note that S_{1}, S_{0} are a partition of {1, …, ℓ}.)

3. Receiver’s message:

(a) For every i ∈ S_{1}, party P_{2} sends the randomness r_{i}^{0}, r_{i}^{1} used to encrypt c_{i}^{0} and c_{i}^{1}.

(b) In addition, for every j ∈ S_{0}, party P_{2} sends a bit β_{j} so that if σ = 0 then β_{j} = b_{j}, and if σ = 1 then β_{j} = 1 − b_{j}.

4. Sender’s message:

(a) For every i ∈ S_{1}, party P_{1} verifies that either c_{i}^{0} = E_{pk}(0; r_{i}^{0}) and c_{i}^{1} = E_{pk}(1; r_{i}^{1}), or c_{i}^{0} = E_{pk}(1; r_{i}^{0}) and c_{i}^{1} = E_{pk}(0; r_{i}^{1}). That is, P_{1} verifies that in every pair, one ciphertext is an encryption of 0 and the other is an encryption of 1. If this does not hold for every such i, party P_{1} halts. If it does hold, it proceeds to the next step.

(b) For every j ∈ S_{0}, party P_{1} defines c_{j} and c′_{j} as follows:

i. If β_{i} = 0 then c_{j} = c_{j}^{0} and c′_{j} = c_{j}^{1}. ii. If β_{i} = 1 then c_{j} = c_{j}^{1} and c′_{j} = c_{j}^{0}. This implies that if σ = 0 then c_{j} = E_{pk}(0) and c′_{j} = E_{pk}(1), and if σ = 1 then c_{j} = E_{pk}(1) and c′_{j} = E_{pk}(0).^{7}

6We assume that it is possible to verify that a public-key pk is in the range of the key generation algorithm G. If this is not the case, then a zero-knowledge proof of this fact must be added.

(c) For every j ∈ S_{0}, party P_{1} chooses random ρ_{j}, ρ′_{j}, uniformly distributed in the group defined by the encryption scheme. Then, P_{1} uses the homomorphic properties of the encryption scheme to compute:

c_{0} = ( ∑_{j∈S_{1}} ρ_{j} · c_{j}) + E_{pk}(m_{0}) and c_{1} = ( ∑_{j∈S_{1}} ρ′_{j} · c′_{j}) + E_{pk}(m_{1})

where addition above denotes the homomorphic addition of ciphertexts and multiplication denotes multiplication by a scalar (again using the homomorphic properties).

(d) P_{1} sends (c_{0}, c_{1}) to P_{2}.

5. Receiver computes output: P_{2} outputs D_{sk}(c_{σ}) and halts.

Before discussing security, we demonstrate correctness:

1. Case σ = 0: In this case, as described in Footnote 7, it holds that for every j, c_{j} = E_{pk}(0) and c′_{j} = E_{pk}(1). Noting that the multiplication of 0 by a scalar equals 0, we have:

c_{0} = ( ∑_{j∈S_{1}} ρ_{j} · c_{j}) + E_{pk}(m_{0}) = E_{pk}(0) + E_{pk}(m_{0}) = E_{pk}(m_{0}).

Thus, when P_{2} decrypts c_{0} it receives m_{0}, as required.

2. Case σ = 1: In this case, it holds that for every j, c_{j} = E_{pk}(1) and c′_{j} = E_{pk}(0). Thus, similarly to before,

c_{1} = · (∑_{j} ρ′_{j} · c′_{j}) + E_{pk}(m_{1}) = E_{pk}(0) + E_{pk}(m_{1}) = E_{pk}(m_{1}),

and so when P_{2} decrypts c_{1}, it receives m_{1}, as required.

We have the following theorem:

Theorem 2 Assume that (G, E, D) is a secure homomorphic encryption scheme, Com_{h} is a perfectlyhiding commitment scheme and Com_{b} is a perfectly-biding commitment scheme. Then, Protocol 2 securely computes the oblivious transfer functionality in the presence of malicious adversaries.

Proof (sketch): In the case that P_{2} is corrupted, the simulator works by rewinding the corrupted P_{2} over the coin tossing phase in order to obtain two different openings and reorderings. In this way, the simulator can easily derive the value of P_{2}’s input σ (σ is taken to be 0 if all the c_{j} ciphertexts for which it obtained both reorderings and openings are encryptions of 0, and is taken to be 1 otherwise). It sends σ to the trusted party and receives back m = m_{σ}. Finally, the simulator generates c_{σ} as the honest party P_{1} would (using m), and generates c_{1−σ} as an encryption to a random string. Beyond a negligible fail probability in obtaining the two openings mentioned, the only difference with respect to a corrupted P_{2}’s view is the way c_{1−σ} is generated. However, notice that:

7In order to see this, note that if σ = 0 then β_{j} = b_{j}. Thus, if β_{j} = b_{j} = 0 we have that c_{j} = c_{j}^{0} = E_{pk}(0) and c′_{j} = c_{j}^{1} = E_{pk}(1). In contrast, if β_{j} = b_{j} = 1 then c_{j} = c_{j}^{1} = E_{pk}(0) and c′_{j} = c_{j}^{0} = E_{pk}(1). That is, in all cases of σ = 0 it holds that c_{j} = E_{pk}(0) and c′_{j} = E_{pk}(1). Analogously, if σ = 1 the reverse holds.

c_{1−σ} = ( ∑_{j∈S_{1}} ρ̂_{j} · ĉ_{j}) + E_{pk}(m_{1−σ})

where ρ̂_{j} = ρ_{j} and ĉ_{j} = c_{j}, or ρ̂_{j} = ρ′_{j} and ĉ_{j} = c′_{j}, depending on the value of σ. Now, if at least one value ĉ_{j} for j ∈ S_{1} is an encryption of 1, then the ciphertext c_{1−σ} is an encryption of a uniformly distributed value (in the group defined by the homomorphic encryption scheme). This is due to the fact that ĉ_{j} is multiplied by ρ̂_{j} which is uniformly distributed. Now, by the cut-and-choose technique employed, the probability that for all j ∈ S_{1} it holds that ĉ_{j} ≠ E_{pk}(1) is negligible. This is due to the fact that this can only hold if for many ciphertext pairs c_{i}^{0}, c_{i}^{1} sent by P_{2} in its first message, the pair is not correctly generated (i.e., it is not the case that one is an encryption of 0 and the other an encryption of 1). However, if this is the case, then P_{1} will abort except with negligible probability, because S_{0} will almost certainly contain one of these pairs (and the sets S_{0} and S_{1} are chosen as a random partition based on the value s output from the coin tossing).

In the case that P_{1} is corrupted, the simulator manipulates the coin tossing so that in the unopened pairs of encryptions, all of the ciphertexts encrypt 0. This implies that both (∑_{j∈S_{1}} ρ_{j} · c_{j}) =

E_{pk}(0) and (∑_{j∈S_{1}} ρ′_{j} · c′_{j}) = E_{pk}(0), in turn implying that c_{0} = E_{pk}(m_{0}) and c_{1} = E_{pk}(m_{1}). Thus, the simulator obtains both m_{0} and m_{1} and sends them to the trusted party. This completes the proof sketch. A full proof follows from the proof of security for Protocol 1.

6 Acknowledgements

We would like to thank Nigel Smart for helpful discussions and Benny Pinkas for pointing out an error in a previous version.

References

[1] W. Aiello, Y. Ishai and O. Reingold. Priced Oblivious Transfer: How to Sell Digital Goods. In EUROCRYPT 2001, Springer-Verlag (LNCS 2045), pages 119–135, 2001.

[2] G. Aggarwal, N. Mishra and B. Pinkas. Secure Computation of the k th-Ranked Element. In EUROCRYPT 2004, Springer-Verlag (LNCS 3027), pages 40–55, 2004.

[3] Y. Aumann and Y. Lindell. Security Against Covert Adversaries: Efficient Protocols for Realistic Adversaries. In the 4th TCC, Springer-Verlag (LNCS 4392), pages 137–156, 2007.

[4] B. Barak and Y. Lindell. Strict Polynomial-Time in Simulation and Extraction. SIAM Journal on Computing, 33(4):783–818, 2004.

[5] D. Beaver. Foundations of Secure Interactive Computing. In CRYPTO’91, Springer-Verlag (LNCS 576), pages 377–391, 1991.

[6] J. Camenisch, G. Neven and A. Shelat. Simulatable Adaptive Oblivious Transfer. In EU-ROCRYPT 2007, Springer-Verlag (LNCS 4515), pages 573–590, 2007.

[7] R. Canetti. Security and Composition of Multiparty Cryptographic Protocols. Journal of Cryptology, 13(1):143–202, 2000.

[8] R. Cramer and V. Shoup. Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption. In EUROCRYPT 2002, Springer-Verlag (LNCS 2332), pages 45–64, 2002.

[9] Y. Dodis, R. Gennaro, J. Håstad, H. Krawczyk and T. Rabin. Randomness Extraction and Key Derivation Using the CBC, Cascade and HMAC Modes. In CRYPTO 2004, Springer-Verlag (LNCS 3152), pages 494–510, 2004.

[10] T. El Gamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory, 31(4):469–472, 1985.

[11] S.D. Galbraith, K.G. Paterson and N.P. Smart. Pairings for Cryptographers. Cryptology ePrint Archive Report 2006/165, 2006.

[12] S. Even, O. Goldreich and A. Lempel. A Randomized Protocol for Signing Contracts. In Communications of the ACM, 28(6):637–647, 1985.

[13] O. Goldreich. Foundations of Cryptography: Volume 2 – Basic Applications. Cambridge University Press, 2004.

[14] O. Goldreich and A. Kahan. How To Construct Constant-Round Zero-Knowledge Proof Systems for NP. Journal of Cryptology, 9(3):167–190, 1996.

[15] S. Goldwasser and L. Levin. Fair Computation of General Functions in Presence of Immoral Majority. In CRYPTO’90, Springer-Verlag (LNCS 537), pages 77–93, 1990.

[16] O. Goldreich, S. Micali and A. Wigderson. How to Play any Mental Game – A Completeness Theorem for Protocols with Honest Majority. In 19th STOC, pages 218–229, 1987. For details see [13].

[17] M. Green and S. Hohenberger. Blind Identity-Based Encryption and Simulatable Oblivious Transfer. In Asiacrypt 2007, Springer-Verlag (LNCS 4833), pages 265–282, 2007.

[18] Y.T. Kalai. Smooth Projective Hashing and Two-Message Oblivious Transfer. In EURO-CRYPT 2005, Springer-Verlag (LNCS 3494), pages 78–95, 2005.

[19] J. Kilian. Founding Cryptograph on Oblivious Transfer. In 20th STOC, pages 20–31, 1988.

[20] E. Kushilevitz and R. Ostrovsky. Replication is NOT Needed: SINGLE Database, Computationally-Private Information Retrieval. In 38th FOCS, pages 364–373, 1997.

[21] Y. Lindell and B. Pinkas. An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries. In EUROCRYPT 2007, Springer-Verlag (LNCS 4515), pages 52–78, 2007.

[22] S. Micali and P. Rogaway. Secure Computation. Unpublished manuscript, 1992. Preliminary version in CRYPTO’91, Springer-Verlag (LNCS 576), pages 392–404, 1991.

[23] M. Mitzenmacher and E. Upfal. Probability and Computing. Cambridge University Press, 2005.

[24] M. Naor and B. Pinkas. Efficient Oblivious Transfer Protocols. In 12th SODA, pages 448– 457, 2001.

[25] T.P. Pedersen. Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. In CRYPTO’91, Springer-Verlag (LNCS 576), pages 129–140, 1991.

[26] C. Peikert, V. Vaikuntanathan and B. Waters. A Framework for Efficient and Composable Oblivious Transfer. In CRYPTO 2008, Springer-Verlag (LNCS 5157), pages 554–571, 2008.

[27] M. Rabin. How to Exchange Secrets by Oblivious Transfer. Tech. Memo TR-81, Aiken Computation Laboratory, Harvard U., 1981.

[28] A. Yao. How to Generate and Exchange Secrets. In 27th FOCS, pages 162–167, 1986.

A The Naor-Pinkas Protocol

For the sake of comparison with our protocol, we describe the protocol of [24] in this appendix.

Protocol 3

• Input: The sender has a pair of strings (m_{0}, m_{1}) and the receiver has a bit σ.

• Auxiliary input: The parties have the description of a group G of order q, and a generator g for the group; the order of the group is known to both parties.

• The protocol:

1. The receiver P_{2} chooses a, b, c ∈_{R} {0, …, q − 1} and computes γ as follows:

(a) If σ = 0 then γ = (g^{a}, g^{b}, g^{ab}, g^{c})

(b) If σ = 1 then γ = (g^{a}, g^{b}, g^{c}, g^{ab})

P_{2} sends γ to P_{1}.

2. Denote the tuple γ received by P_{1} by (x, y, z_{0}, z_{1}). Then, P_{1} checks that z_{0} ≠ z_{1}. If they are equal, it aborts outputting ⊥. Otherwise, P_{1} chooses random u_{0}, u_{1}, v_{0}, v_{1} ∈_{R} {0, …, q − 1} and computes the following four values:

w_{0} = x^{u_{0}} · g^{v_{0}} k_{0} = (z_{0})^{u_{0}} · y^{v_{0}}
w_{1} = x^{u_{1}} · g^{v_{1}} k_{1} = (z_{1})^{u_{1}} · y^{v_{1}}

P_{1} then encrypts m_{0} under k_{0} and m_{1} under k_{1}. For the sake of simplicity, assume that one-time pad type encryption is used. That is, assume that m_{0} and m_{1} are mapped to elements of G. Then, S computes c_{0} = m_{0} · k_{0} and c_{1} = m_{1} · k_{1} where multiplication is in the group G. P_{1} sends P_{2} the pairs (w_{0}, c_{0}) and (w_{1}, c_{1}).

3. P_{2} computes k_{σ} = (w_{σ})^{b} and outputs m_{σ} = c_{σ} · (k_{σ})^{−1}.

The security of Protocol 1 rests on the decisional Diffie-Hellman (DDH) assumption that states that tuples of the form (g^{a}, g^{b}, g^{c}) where a, b, c ∈_{R} {0, …, q − 1} are indistinguishable from tuples of the form (g^{a}, g^{b}, g^{ab}) where a, b ∈_{R} {0, …, q − 1} (recall that q is the order of the group G that we are working in). This implies that an adversarial sender cannot discern whether the message sent by P_{2} is (g^{a}, g^{b}, g^{ab}, g^{c}) or (g^{a}, g^{b}, g^{c}, g^{ab}) and so P_{2}’s input is hidden from P_{1}. The motivation for P_{1}’s privacy is more difficult and it follows from the fact that – informally speaking – the exponentiations computed by P_{1} completely randomize the triple (g^{a}, g^{b}, g^{c}). Interestingly, it is still possible for P_{2} to derive the key k_{σ} that results from the randomization of (g^{a}, g^{b}, g^{ab}). None of these facts are evident from the protocol itself but are demonstrated in the proof of our protocol in Section 3.