key: cord-0061115-xdqk6i2g
authors: Döttling, Nico; Garg, Sanjam; Hajiabadi, Mohammad; Masny, Daniel; Wichs, Daniel
title: Two-Round Oblivious Transfer from CDH or LPN
date: 2020-03-25
journal: Advances in Cryptology - EUROCRYPT 2020
DOI: 10.1007/978-3-030-45724-2_26
sha: 5260605c51619a005f1a71c61a6dcfa072121a12
doc_id: 61115
cord_uid: xdqk6i2g

We show a new general approach for constructing maliciously-secure two-round oblivious transfer (OT). Specifically, we provide a generic sequence of transformations to upgrade a very basic notion of two-round OT, which we call elementary OT, to UC-secure OT. We then give simple constructions of elementary OT under the Computational Diffie-Hellman (CDH) assumption or the Learning Parity with Noise (LPN) assumption, yielding the first constructions of malicious (UC-secure) two-round OT under these assumptions. Since two-round OT is complete for two-round 2-party and multi-party computation in the malicious setting, we also achieve the first constructions of the latter under these assumptions.

Oblivious transfer (OT) [Rab05, EGL85] , is a fundamental primitive in cryptography. An OT protocol consists of two parties: a sender and a receiver. The sender's input is composed of two strings (m 0 , m 1 ) and the receiver's input is a bit c. At the end of the execution of the OT protocol, the receiver should only learn the value m c , but should not learn anything about the other value m 1−c . The sender should gain no information about the choice bit c. This very simple primitive is often used as the foundational building block for realizing secure computation protocols [Yao82, GMW87] . Thus, the efficiency characteristics of the OT protocol directly affect the efficiency of the resulting secure computation

One reason that (two-round) OT is difficult to construct is that this notion is even difficult to define. Simulation-based definitions of security are complex and impose requirements that often seem stronger than necessary and hard to achieve. Unlike (say) public-key encryption, where we have simple game-based definitions that imply simulation-based (semantic) security, we do not have any simpler definitions of malicious OT security that suffice for simulation. All prior attempts from the literature to weaken the definition of OT security are still complex and require some form of extraction/simulation. In particular, to meaningfully define that the malicious receiver only learns one of the two sender values m 0 , m 1 , all known definitions require that we can somehow extract the receiver's choice bit c from the first OT message and then argue that the second message hides the value m 1−c .

To meet any such extraction-based definition, we need to start with an OT where the receiver's choice bit is statistically committed in the first OT message. This seems like a significant restriction. For example there is a natural construction of OT from CDH due to Bellare and Micali [BM90] , which achieves semi-honest security in the standard model or a weak form of malicious security in the random-oracle model. However, in this construction, the first message only commits the receiver computationally to the choice bit and hence there is no hope of extracting it. Therefore, it appears difficult to prove any meaningful notion of malicious security without resorting to the random oracle model.

Overall, we are aware of only two approaches towards achieving maliciouslysecure OT. The first starts with semi-honest OT and then compiles it to malicious OT using zero-knowledge proofs. Unfortunately, if we want two-round OT we would need to use non-interactive zero-knowledge (NIZK) proofs and we do not have instantiations of such NIZKs under many natural assumptions such as CDH or LPN (or LWE). The other approach, used by Peikert, Vaikuntanathan and Waters [PVW08] (and to some extent also e.g., [NP01, AIR01, BD18] ) takes advantage of a statistically "lossy" mode of DDH/LWE based encryption. Unfortunately, we do not have any such analogous "lossy" mode for CDH/LPN based encryption and therefore this approach too appears to be fundamentally stuck.

In this work, we give a new general approach for constructing UC-secure tworound OT. 1 Specifically, we introduce an extremely weak and simple notion of two-round OT, which we call elementary OT. This notion is defined via a gamebased definition and, in contrast to all prior notions of OT, does not rely on an extractor. We then provide a series of generic transformations that upgrade the security of elementary OT, eventually culminating in a UC-secure two-round OT. These transformations are the main technically challenging contributions of the paper. Lastly, we show simple constructions of two-round elementary OT under the Computational Diffie-Hellman (CDH) assumption or the Learning Parity with Noise (LPN) assumption, yielding the first constructions of UC-secure tworound OT under these assumptions. We rely on a variant of LPN with noise-rate 1/n ε for some arbitrary constant ε > 1 2 . 2 Applications to Two-Round MPC. As mentioned earlier, two-round OT is known to be complete for constructing two-round MPC [GS18, BL18] . Thus, our results also yield the first constructions of two-round malicious (UC-secure) MPC under the Computational Diffie-Hellman (CDH) assumption or the Learning Parity with Noise (LPN) assumption.

Open Problems. Interestingly, our generic transformations use garbled circuits that make a non-black-box use of the underlying cryptographic primitives. We leave it as an open problem to obtain a black-box construction or show the impossibility thereof.

Follow-Up Work. Subsequently to our work, techniques and results of our paper were used in some follow-up works. Lombardi et al. [LQR+19] used our main result to obtain the first construction of maliciously-secure designatedverifier NIZK (MDV-NIZK) from CDH. MDV-NIZK may be though of as a two-round ZK protocol in the CRS model with a reusable first-round message. Technically, [LQR+19] gives constructionist of MDV-NIZK from a combination of key-dependent-message (KDM) secure private-key encryption for projection functions and a receiver-extractable two-round OT protocol. (See Definition 15.) They used the main result of our paper in order to realize their OT component. (The KDM component is already known from CDH [BLSV18] .) In another work, Döttling, Garg and Malavolta [DGM19] use and extend techniques form our work (especially those from Sect. 6) in order to build protocols for Malicious Laconic Function Evaluation (among others).

Our results are obtained via a sequence of transformations between various notions of OT. We give an overview of this sequence in Fig. 1 and explain each of the steps below. All of the notions of OT that we consider are two-round and can rely on a common reference string (CRS), which is generated by a trusted third party and given to both the sender and the receiver. For simplicity, we often ignore the CRS in the discussion below.

Elementary OT. We begin by defining an extremely weak and simple notion of OT, called elementary OT. The receiver uses her choice bit c to generate a first round message otr. The sender then uses otr to generate a second-round message ots together with two values y 0 , y 1 . The receiver gets ots and uses it to recover the value y c . Note that, unlike in standard OT, the sender does not choose the two values y 0 , y 1 himself, but instead generates them together with ots. (One may think of this as analogous to the distinction between key-encapsulation and encryption.) The security of elementary OT is defined via the following two game-based requirements:

1. Receiver Security: The receiver's choice bit c is computationally hidden by the first-round OT message otr. 2. Sender Security: A malicious receiver who creates the first-round message otr maliciously and is then given an honestly generated second-round message ots cannot simultaneously output both of the values y 0 , y 1 except with negligible probability.

Note that elementary OT provides a very weak notion of sender security. Firstly, it only provides unpredictability, rather than indistinguishability, based security -the malicious receiver cannot output both values y 0 , y 1 , but may learn some partial information about each of the two values. Second of all, it does not require that the there is a consistent bit w such that the value y w is hidden from the malicious receiver -it may be that, even after the receiver maliciously chooses otr, for some choices of ots she learns y 0 and for other choices she learns y 1 . We fix the second issue first.

From Elementary OT to Search OT. We define a strengthening of elementary OT, which we call search OT. The syntax and the receiver security remain the same. For sender security, we still keep an unpredictability (search) based security definition. But now we want to ensure that, for any choice of the malicious receiver's message otr, there is a consistent bit w such that y w is hidden. We want to capture this property without requiring the existence of an (even inefficient) extractor that can find such w. We do so as follows. For any choice of the malicious receiver's first message otr (along with all her random coins and the CRS), we define two probabilities ε 0 , ε 1 which denote the probability of the receiver outputting y 0 and y 1 respectively, taken only over the choice of ots. We require that for any polynomial p, with overwhelming probability over the receiver's choices, at least one of ε 0 or ε 1 is smaller than 1/p. In particular, this means that with overwhelming probability over the malicious receiver's choice of otr, there is a fixed and consistent bit w such that the receiver will be unable to recover y w from the sender's message ots. Note that the value w may not be extractable (even inefficiently) from otr alone since the way that w is defined is "adversary-dependent".

To go from elementary OT to search OT, we rely on techniques from "hardness amplification". The difficulty of using a search-OT adversary to break elementary-OT security is that a search-OT adversary can, for example, have ε 0 = ε 1 = 1 2 , but for half the value of ots it outputs the correct y 0 and for half it outputs the correct y 1 , yet it never output both correct values simultaneously. However, if we could ensure that ε 0 , ε 1 are both much larger than 1 2 , then this could not happen. We use hardness amplification to achieve this. In particular, we construct search OT scheme from elementary OT by having the sender generate λ (security parameter) different second-round messages of the elementary OT and set the search OT values to be the concatenations OTS = (ots 1 , . . . , ots λ ) and Y 0 = (y 1 0 , . . . , y λ 0 ), Y 1 = (y 1 1 , . . . , y λ 1 ). By hardness amplification, if for some choice of otr the malicious receiver can separately predict each of Y 0 , Y 1 with probability better than some inverse polynomial 1/p, then that means it can separately predict each of the components y 0 , y 1 with extremely high probability > 3 4 , and by the union bound, can therefore predict both components y 0 , y 1 simultaneously with probability > 1 4 . From Search OT to Indistinguishability OT. Next, we define a notion that we call indistinguishability OT. Here, just like in standard OT, the sender gets to choose his two values m 0 , m 1 himself, rather than having the scheme generate values y 0 , y 1 for him, as was the case in elementary and search OT. The receiver security remains the same as in elementary and search OT: the receiver's choice bit c is hidden by her first-round message otr. The sender security is defined in a similar manner to search OT, except that we now require indistinguishability rather than unpredictability. In particular, the malicious receiver chooses two values m 0 , m 1 and a maliciously generated otr. For any such choice, we define two probabilities ε 0 , ε 1 , where ε b denotes the receiver's advantage, calculated only over the random coins of the sender, in distinguishing between ots generated with the messages (m 0 , m 1 ) versus (m 0 , m 1 ) where m b is uniformly random and m 1−b = m 1−b . We require that for any polynomial p, with overwhelming probability over the receiver's choices, at least one of ε 0 or ε 1 is smaller than 1/p. In particular, this means that, with overwhelming probability, the malicious receiver's choice of otr fixes a consistent bit w such that the receiver does not learn anything about m w .

To go from search OT to indistinguishability OT with 1-bit values m 0 , m 1 , we rely on the Goldreich-Levin hardcore bit [GL89] . In particular, we use search OT to generate ots along with values y 0 , y 1 and then use the Goldreich-Levin hardcore bits of y 0 , y 1 to mask m 0 , m 1 respectively. To then allow for multi-bit values m 0 , m 1 , we simply have the sender send each bit separately, by reusing the same receiver message otr for all bits.

From Indistinguishability OT to Weak SFE. Next, we generalize from OT and define a weak form of (two-round) secure function evaluation (weak-SFE). Here, there is a receiver with an input x and a sender with a circuit f . The receiver learns the output f (x) in the second round. We define a very simple (but weak) game-based notion of malicious security, without relying on a simulator or extractor:

-Receiver Security: The receiver's first-round message hides the input x from the sender. -Sender Security: A malicious receiver cannot distinguish between any two functionally equivalent circuits f 0 , f 1 used by the sender.

We show how to compile indistinguishability OT to weak SFE. Indeed, the construction is the same as the standard construction of (standard) SFE from (standard) OT: the receiver sends first-round OT messages corresponding to the bits of the input x and the sender creates a garbled circuit for f and uses the two input labels as the values for the second-round OT messages. The proof of sender security, however, is very different than that for the standard construction of SFE from OT, which relies on extracting the receiver's OT choice bits. Instead, we rely on technical ideas that are similar to and inspired by those recently used in the context of distinguisher-dependent simulation [JKKR17] and have a sequence of hybrids that depends on the adversary. More concretely, indistinguishability OT guarantees that for each input wire, there is some bit w such that the adversary cannot tell if we replace the label for w by uniform. However, this bit w is defined in an adversary-dependent manner. This effectively allows us to extract the adversary's OT choice bits. Therefore, we have a sequence of adversary-dependent hybrids where we switch the OT values used by the sender and replace the labels for the bits w by random values. We then rely on garbled circuit security to argue that garblings of f 0 and f 1 are indistinguishable, and conclude that the adversary's advantage is negligible. Formalizing the above high-level approach is the most technically involved component of the paper.

From Weak SFE to OT with UC Sender Security. We show how to go from weak SFE to an OT scheme that has UC-security for the sender. In particular, this means we can extract the choice bit c from the receiver's firstround message otr and simulate the sender's second-round message ots given only m c , without knowing the "other" value m 1−c . For the receiver's security, we maintain the same indistinguishability-based requirement as in elementary/search/indistinguishability OT, which guarantees that the choice bit c is hidden by the first-round OT message otr. We refer to this as a "half-UC OT" for short. This is the first step where we introduce a simulation/extraction based notion of security.

Our compiler places a public-key pk of a public-key encryption (PKE) scheme to the CRS. The receiver encrypts her choice bit c under pk using randomness r and sends the resulting ciphertext ct = E pk (c; r) as part of her first-round OT message. At the same time, the receiver and sender run an instance of weak SFE, where the receiver's input is x = (c, r) and the sender's circuit is f pk,ct,m0,m1 (c, r), which output m c if ct = E pk (c; r) and ⊥ otherwise. The indistinguishability-based security of the receiver directly follows from that of the SFE and the PKE, which together guarantees that c is hidden by the first-round message. To argue UC security of the sender, we now extract the receiver's bit c by decrypting the ciphertext ct. If ct is an encryption of c then f pk,ct,m0,m1 is functionally equivalent to f pk,ct,m 0 ,m 1 where m c = m c and m 1−c is replaced by an arbitrary value, say all 0s. Therefore, we can simulate the sender's second-round OT message by using the circuit f pk,ct,m 0 ,m 1 , which only relies on knowledge of m c without knowing m 1−c , and weak SFE security guarantees that this is indistinguishable from the real world.

From UC Sender Security to Full UC OT. Finally, we show how to use an OT scheme with UC-security of the sender and indistinguishability-based security for the receiver ("half-UC OT") to get a full UC-secure OT. In particular, this means that we need to simulate the receiver's first-round message without knowing c and extract two values m 0 , m 1 from a malicious sender such that, if the receiver's bit was c, he would get m c .

Before we give our actual construction, it is useful to examine a naive proposal and why it fails. In the naive proposal, the sender commits to both values m 0 , m 1 using an extractable commitment (e.g., PKE where the public key is in the CRS); the parties use a half-UC OT where the sender puts the two decommitments as his OT values and also sends the commitments as part of the second-round OT message. We can extract two values m 0 , m 1 from the commitment and are guaranteed that the receiver either outputs the value m c or ⊥ (if the decommitment he receives via the underlying OT is incorrect). But we are unable to say which of the two cases will occur. This is insufficient for full security.

We solve the above problem via two steps:

-We first give a solution using a two-round zero-knowledge (ZK) argument and an extractable commitment (both in the CRS model). The sender and receiver run the half-UC OT protocol where the receiver uses her choice bit c and the sender uses his two values m 0 , m 1 . In the first round, the receiver also sends the first-round verifier message of the ZK argument. In the second round, the sender also commits to his two messages m 0 , m 1 using an extractable commitment and uses the ZK argument system to prove that he computed the second-round OT message correctly using the same values m 0 , m 1 as in the commitment. This provides UC security for the receiver since, if the ZK argument verifies, we can extract the values m 0 , m 1 from the commitment and know that the receiver would recover the correct value m c . The transformation also preserves UC security for the sender since the ZK argument can be simulated. -We then show how to construct a two-round ZK argument using half-UC OT.

We rely on a Σ-protocol for NP where the prover sends a value a, receives a 1-bit challenge b ∈ {0, 1}, and sends a response z; the verifier checks that the transcript (a, b, z) is valid for the statement being proved and accepts or rejects accordingly. We can compile a Σ-protocol to a two-round ZK argument using OT. The verifier sends a first-round OT message for a random bit b. The prover chooses a and computes both responses z 0 , z 1 corresponding to both possible values of the challenge b; he then sends a and uses z 0 , z 1 as the values for the second-round OT message. The verifier recovers z b from the OT and checks that (a, b, z b ) is a valid transcript of the Σ-protocol. We repeat this in parallel λ (security parameter) times to get negligible soundness error. It turns out that we can prove ZK security by relying on the UC-security for the sender; we can extract the OT choice bits b in each execution and then simulate the Σ-protocol transcript after knowing the challenge bit b. It would also be easy to prove soundness using UC-security for the receiver, but we want to only rely on a "half-UC" OT where we only have indistinguishability security of the receiver. To solve this, we rely on a special type of "extractable" Σ-protocol [HL18] in the CRS model, where, for every choice of a there is a unique "bad challenge" b such that, if the statement is false, there exists a valid response z that results in a valid transcript (a, b, z). Furthermore, this unique bad challenge b should be efficiently extractable from a using a trapdoor to the CRS. Such "extractable" Σ-protocols can be constructed from only public-key encryption. If the Σ-protocol is extractable and the OT scheme has indistinguishability-based receiver security then the resulting tworound ZK is computationally sound. This is because, the only way that the prover can succeed is if in each of the λ invocations he chooses a first message a such that the receiver's OT choice bit b is the unique bad challenge for a, but this means that the prover can predict the receiver's OT choice bits (the reduction uses the trapdoor for the Σ-protocol to extract the unique bad challenge from a).

Combined together, the above two steps give a general compiler from half-UC OT to fully secure UC OT.

Instantiation from CDH. We now give our simple instantiation of elementary OT under the CDH assumption. The construction is based on a scheme of Bellare and Micali [BM90] , which achieves a weak form of malicious security in the random-oracle model. Our protocol is somewhat simplified and does not require a random oracle. Recall that the CDH assumption states that, given a generator g of some cyclic group G of order p, along with values g a , g b for random a, b ∈ Z p , it is hard to compute g ab . The CRS of the OT scheme consists of A = g a for random a ∈ Z p . The receiver with a choice bit c computes two value h c = g r and h 1−c = A/h c for a random r ∈ Z p and sends otr := h 0 as the first-round OT message. The sender computes h 1 = A/h 0 . It chooses a random b ∈ Z p , sets ots := B = g b as the second-round message, and generates the two values

This ensures correctness sinceŷ c = B r = g br = h b c = y c . Also, h 0 is uniformly random over G no matter what the receiver bit c is, and therefore this provides (statistic) indistinguishability-based receiver security. Lastly, we argue that we get elementary OT security for the sender, meaning that a malicious receiver cannot simultaneously compute both y 0 , y 1 . Note that the only values seen by the malicious receiver during the game are A = g a , B = g b . If the receiver

Instantiation from LPN. We also give a simple instantiation of elementary OT under the LPN assumption. This construction closely mirrors the CDH one. We use a variant of the LPN problem with noise-rate 1/n ε for an arbitrary constant ε > 1 2 . We also rely on a variant of the LPN problem where the secret is chosen from the error distribution, which is known to be equivalent to standard LPN where the secret is uniformly random [ACPS09] . In particular this variant of the LPN problem states that, for a Bernoulli distribution B ρ which outputs 1 with probability ρ = 1/n ε , and for A ← Z n×n 

where λ is the security parameter and sends ots := B = SA + E as the second-round OT message. The sender computes the values y 0 = Sh 0 , y 1 = Sh 1 . The receiver outputsŷ c = Bx.

This ensures correctness with a small inverse-polynomial error probability. In particular,

where Ex + Se = 0 except with a small error probability, which we can make an arbitrarily small inverse polynomial in λ by setting n to be a sufficiently large polynomial in λ. The receiver's (computational) indistinguishability-based security holds under LPN since h 0 is indistinguishable from uniform no matter what c is. We also get elementary OT security for the sender under the LPN assumption. A malicious receiver only sees the values A, v and B = SA + E during the game. If the receiver outputs y 0 = Sh 0 , y 1 = Sh 1 , then we can use it to compute y 0 + y 1 = S(h 0 + h 1 ) = Sv. But, since S is hard to compute given A, B, we can argue that Sv is indistinguishable form uniform under the LPN assumption, by thinking of the i'th of Sv as a Goldreich-Levin hardcore bit for the i'th row of S. Therefore, is should be hard to output Sv except with negligible probability.

The fact that we get a small (inverse polynomial) error probability does not affect the security of the generic transformations going from elementary OT to indistinguishability OT for 1-bit messages. Then, when we go from 1bit messages to multi-bit messages we can also use an error-correcting code to amplify correctness and get a negligible correctness error.

Notation. We use λ for the security parameter. We use c ≡ to denote computational indistinguishability between two distributions and use ≡ to denote two distributions are identical. For a distribution D we use x $ ← − D to mean x is sampled according to D and use y ∈ D to mean y is in the support of D. For a set S we overload the notation to use x $ ← − S to indicate that x is chosen uniformly at random from S.

Lemma 1 (Markov Inequality for Advantages). Let A(Z) and B(Z) be two random variables depending on a random variable Z and potentially addi-

The inequality now follows.

Then it holds that 

s.t. Dec(sk, E(pk, m; r)) = m] = negl(λ), where (pk, sk) $ ← − KeyGen(1 λ ).

C with n-bit inputs consists of (Garble, Eval, Sim) with the following correctness and security properties. 

A two-round oblivious transfer (OT) protocol (we use the definition from [BGI+17] ) is given by algorithms (Setup, OT 1 , OT 2 , OT 3 ), where the setup algorithm Setup generates a CRS value crs

The receiver runs the algorithm OT 1 which takes crs and a choice bit c ∈ {0, 1} as input and outputs (otr, st). The receiver then sends otr to the sender, who obtains ots by evaluating OT 2 (1 λ , otr, m 0 , m 1 ), where m 0 and m 1 (such that m 0 , m 1 ∈ {0, 1}λ) are its inputs. The sender then sends ots to the receiver who obtains m c by evaluating OT 3 (1 λ , st, ots).

We say that a two-round OT scheme is perfectly correct, if with probability 1−negl(λ) over the choice of crs 

We consider two notions of receiver's security-namely, notions that require security against a malicious sender. We describe them next. Receiver's UC-Security. We work in Canetti's UC framework with static corruptions [Can01] . We assume familiarity with this model. We use Z for denoting the underlying environment. For a real protocol Π and an adversary A, we use EXEC Π,A,Z to denote the real-world ensemble. Also, for an ideal functionality F and an adversary S we denote IDEAL F ,S,Z to denote the ideal-world ensemble.

We say that an OT protocol OT is receiver-UC secure if for any adversary A corrupting the sender, there exists a simulator S such that for all environments Z:

where the ideal functionality F OT is defined in Fig. 2 . (We will follow the same style as in [CLOS02, PVW08] .)

OT interacts with an ideal sender S and an ideal receiver R.

1. On input (sid, sender, m 0 , m 1 ) from the sender, store (m 0 , m 1 ). 2. On input (sid, receiver, b), check if a pair of inputs (m 0 , m 1 ) has been already recorded for session sid; if so, send m b to R and send sid to the adversary and halt; else, send nothing. Since our OT protocols are in the CRS model, we also give the F CRS idea functionality below (Fig. 3) . D CRS : parameterized over a distribution D, run by parties P 1 , . . . , P n , and an adversary S:

-Whenever receiving message a message (sid, P i , P j ) from party P i , sample crs $ ← − D and send (sid, crs) to P i and send (sid, crs, P i , P j ) to S. Whenever receiving the message (sid, P i , P j ) from P j , send (sid, crs) to P j and S. 

We consider several different notions of sender's security that we define below.

In the first two notions of security, namely elementary and search notions, we change the syntax of OT 2 a bit. More specifically, instead of taking m 0 and m 1 as input, OT 2 outputs two masks y 0 and y 1 where the receiver only gets y c , where c is the receiver's choice bit.

The elementary sender security corresponds to the weakest security notion against a malicious receiver that is considered in this work. This notion requires that the receiver actually compute both the strings y 0 and y 1 used by the sender. Let A = (A 1 , A 2 ) be an adversary. Consider the following experiment Exp λ eOT (A):

1. Run crs 4. Compute (y * 0 , y * 1 ) $ ← − A 2 (st, ots) and output 1 iff (y * 0 , y * 1 ) = (y 0 , y 1 )

We say that a scheme satisfies eOT security if Pr[Exp λ eOT (A) = 1] = negl(λ). Sender's Search Security. Next, we consider the search security notion. In this stronger security notion, the adversary is expected to still compute both y 0 and y 1 but perhaps not necessarily at the same time. More formally, let A = (A 1 , A 2 ) be an adversary where A 2 outputs a message y * . Consider the following experiment Exp crs,r,w sOT (A), indexed by a crs, random coins r ∈ {0, 1} λ and a bit w ∈ {0, 1}. Sender's UC-Security. We say that an OT protocol OT is sender-UC secure if for any adversary A corrupting the receiver, there exists a simulator S such that for all environments Z:

where the ideal functionality F OT is defined in Fig. 2. Definition 5. For X ∈ {elementary, search, indistinguishability}, we call a two-round OT scheme X -secure if it has sender's X security and receiver's indistinguishability security. Moreover, we call a two-round OT scheme UC-secure if it has sender's UC-security and receiver's UC-security.

In this section, we give a sequence of transformations which leads us to sender's indistinguishability security, starting with sender's elementary security.

We rely on a result of [CHS05] on hardness amplification of weakly verifiable puzzles. In such puzzles, a puzzle generator can efficiently verify solutions but others need not be able to; we rely on a restricted case where the solution is unique and the puzzle generator generates the puzzle with the solution. The result essentially says that solving many puzzles is much harder than solving a single puzzle. For simplicity, we state a simplified version of their result (restatement of Lemma 1 in [CHS05] ) with a restricted range of parameters. It shows that, if there is a "weak solver" that has some inverse polynomial advantage in solving λ puzzles simultaneously, then there is an "amplified solver" that has extremely high advantage (arbitrarily close to 1) in solving an individual puzzle.

Lemma 6 (Hardness Amplification [CHS05] ). For every polynomial p and every constant δ > 0 there exists a PPT algorithm Amp such that the following holds for all sufficiently large λ ∈ N. Let G be some distribution over pairs (puzzle, solution) ← G. Let WS be a "weak solver" such that Theorem 7. If Π is an elementary OT then Π described above is a search OT.

The proof can be found in the full version of the paper.

Let Π = (Setup, OT 1 , OT 2 , OT 3 ) be a search OT with message length n = n(λ). We construct an iOT scheme Π = (Setup, OT 1 , OT 2 , OT 3 ) with 1-bit message as follows:

The proof can be found in the full version of the paper.

Let Π = (Setup, OT 1 , OT 2 , OT 3 ) be an iOT scheme with 1 bit messages. Then, we construct an iOT scheme Π = (Setup, OT 1 , OT 2 , OT 3 ) with message length n = n(λ) as follows: Theorem 9. If Π is iOT with 1-bit messages then Π is an iOT with messages of length n.

The proof can be found in the full version of the paper.

In this section, we will define our notion of weak secure function evaluation and provide instantiations of the new notion.

Definition 10. A weak secure function evaluation scheme wSFE for a function class F consists of four PPT algorithms (Setup, Receiver 1 , Sender, Receiver 2 ) with the following syntax.

Setup(1 λ ): Takes as input a security parameter and outputs a common reference string crs Receiver 1 (crs, x): Takes as input a common reference string crs and an input x and outputs a message z 1 and a state st Sender(crs, f, z 1 ): Takes as input a common reference string crs, a function f ∈ F and a receiver message z 1 and outputs a sender message z 2 Receiver 2 (st, z 2 ): Takes as input a state st and a sender message z 2 and outputs a value y.

We require the following properties. A = (A 1 , A 2 ) be an adversary where A 2 outputs a bit and let the experiment Exp SP (A) be defined as follows: A = (A 1 , A 2 ) which output equivalent functions f 0 ≡ f 1 in the first stage that Adv SP (A) < negl(λ). Likewise, we say that wSFE has statistical sender privacy, if it holds for all unbounded (non-uniform) adversaries A which output equivalent functions f 0 ≡ f 1 in the first stage that Adv SP (A) < negl(λ).

Let iOT = (Setup, OT 1 , OT 2 , OT 3 ) be an iOT protocol and let (Garble, Eval) be a garbling scheme. Overloading notation, assume that if x = (x 1 , . . . , x n ) ∈ {0, 1} n is an input vector, then OT 1 (crs, x) = (OT 1 (crs, x 1 ), . . . , OT 1 (crs, x n ) ). Similarly, if m 0 = (m 0,1 , . . . , m 0,n ) and m 1 = (m 1,1 , . . . , m 1,n ) are two vectors of messages, then denote OT2(crs, otr, m0, m1) = (OT2(crs, otr 1 , m0,1, m1,1) , . . . , OT2(crs, otr n , m0,n, m1,n))

The scheme wSFE is given as follows. and we get that wSFE is correct.

Receiver Privacy. We will first establish receiver privacy of wSFE.

Theorem 11. Assume that iOT has receiver indistinguishability security. The wSFE has receiver privacy.

The proof can be found in the full version of the paper.

Sender Privacy. We will now proceed to show sender privacy of wSFE against malicious receivers.

Theorem 12. Assuming that iOT has indistinguishability sender privacy and that (Garble, Eval) is a simulation secure garbling scheme, it holds that wSFE has sender privacy.

The proof can be found in the full version of the paper.

In this section we will provide a two-round OT protocol with sender's UC security and receiver's indistinguishability security from any CPA-secure PKE and a tworound wSFE for a specific class of functions. Let PKE := (KeyGen, E, Dec) be a PKE scheme and let wSFE be a two-round wSFE, i.e. wSFE := (Setup, Receiver 1 , Sender, Receiver 2 ), for a function class F defined as follows: any function in this class is of the form C[pk, ct, m 0 , m 1 ], parameterized over a public key pk, a ciphertext ct and two messages m 0 and m 1 , and is defined as follows: OT 2 (crs, otr, m 0 , m 1 ): Parse crs = (crs , pk), otr = (ct, z 1 ) and compute z 2 $ ← − wSFE.Sender(crs , C[pk, ct, m 0 , m 1 ], z 1 ). Output ots := z 2 . OT 3 (st, ots): Let z 2 := ots. Compute and output Receiver 2 (st, z 2 ).

Assuming PKE is CPA-secure and perfectly correct (Definition 3), and that wSFE satisfies correctness, receiver privacy and sender privacy (Definition 10), then the OT given in Construction 13 provides receiver's indistinguishability security and sender's UC security.

The proof can be found in the full version of the paper.

Finally, we mention that the OT protocol constructed in Construction 13 satisfies a receiver-extractability property, which was (implicitly) used in the proof of sender's UC security. Since we will use this definition later, we formalize it below.

Definition 15. We say that an OT protocol (Setup, OT 1 , OT 2 , OT 3 ) has receiver extractability if the setup algorithm Setup(1 λ ) in addition to crs also outputs a trapdoor key σ and if there is a PPT algorithm Extract, for which the following holds: for any stateful PPT adversary A := (A 1 , A 2 ) , assuming (m 0 , m 1 , otr) $ ← − A 1 (crs) and b = Extract(σ, otr), then A 2 cannot distinguish between the outputs of OT 2 (crs, otr, (m 0 , m 1 )) and OT 2 (crs, otr, (m b , m b ) ).

In this section we give a two-round (statement-independent) ZK protocol against malicious verifiers in the CRS model based on a special type of Σ-protocols and an OT with sender's UC-security and receiver's indistinguishability security.

We first start by defining the properties we require of our Σ-protocol, and will then define the notion of statement-independent ZK protocols that we would like to achieve. Our notion of Σ-protocols is what Holmgren and Lombardi [HL18] called extractable Σ-protocols, defined as follows.

(Setup, P, V, Extract, Sim) for a language L ∈ NP is a three-round argument system between a prover P := (P 1 , P 2 ) and a verifier V, where the prover is the initiator of the protocol and where the verifier's only message is a random bit b ∈ {0, 1}. The setup algorithm (crs, σ) $ ← − Setup(1 λ ) returns a CRS value crs together with an associated trapdoor key σ. The trapdoor key σ will only play a role in the extractability requirement. We require the following properties:

-Completeness: For all λ, all (x, w) ∈ R (where R is the underlying relation), we have Pr[V(crs, x, a, b, z) = 1] = 1, where the probability is taken over (crs, σ)

-Special soundness and extractability: For any value crs generated as (crs, σ) We will now define out notion of CRS-based two-round statement-independent ZK. Informally, a two-round ZK protocol is statement-independent if the verifier's message in the protocol is independent of the statement being proven.

A two-round zero-knowledge argument system for a language L ∈ NP with a corresponding relation R in the CRS model consists of four PPT algorithms ZK = (Setup, P, V := (V 1 , V 2 ), Sim := (Sim 1 , Sim 2 )), defined as follows. The setup algorithm Setup on input 1 λ outputs a value crs. The verifier algorithm V 1 (crs) on input crs returns a message msgv together with a private state st.

We stress that the verifier does not take as input any statement x, hence the "statement-independent" name. The prover algorithm P(crs, x, w, msgv) on input crs, a statement x with a corresponding witness w and a verifier's message msgv, outputs a message msgp. Finally, the algorithm V 2 (st, x, msgp) outputs a bit b.

We require the following properties. 

Construction 18 (Two-round ZK). Let OT := (Setup, OT 1 , OT 2 , OT 3 ) be an OT protocol and let SIGM := (Setup, P, V, Extract, Sim) be an extractable Σ-protocol for a language L ∈ NP (Definition 16). We give a tworound ZK protocol ZK := (Setup, P, V := (V 1 , V 2 )) for L as follows. The construction is parameterized over a polynomial r := r(λ), which we will instantiate in the soundness proof. (sts i , b) , which is the prover's last message in the Σ-protocol when his first message was a i and when the verifier's challenge bit is b. Return msgp := ( a, OT 2 (crs ot , otr, z 0 , z 1 )), where a : = (a 1 , . . . , a r ) , z 0 := (z 1,0 , . . . , z r,o ) and z 1 := (z 1,1 , . . . , z r,1 ) . The proof can be found in the full version of the paper.

We will now show how to build a UC-secure OT scheme (with both receiver's and sender's UC security) from the combination of a CPA-secure PKE scheme, a CRS-based two-round statement-independent ZK protocol, and a two-round OT scheme with sender's UC-security and receiver's indistinguishability security. Let PKE := (KeyGen, E, Dec) be the PKE scheme, (Setup, OT 1 , OT 2 , OT 3 ) be the base two-round OT scheme and ZK = (Setup, P, V := (V 1 , V 2 ), Sim := (Sim 1 , Sim 2 )) be a two-round statement-independent ZK protocol for the language L pk,crsot,otr ∈ NP, parameterized over a public key pk of the PKE scheme, a CRS value crs ot of the OT scheme and an OT-receiver's message otr, defined as follows:

L pk,crsot,otr = (ct 0 , ct 1 , ots) | ∃(m 0 , m 1 , r 0 , r 1 , r) s.t. The proof can be found in the full version of the paper.

We first give a construction of elementary OT from CDH. In fact, we show that the construction also already directly satisfies the stronger notion of search OT security. The protocol is given in Fig. 4 .

G be a group-generator scheme, which on input 1 λ outputs (G, p, g), where G is the description of a group, p is the order of the group which is always a prime number and g is a generator of the group. We say that G is CDH-hard if for any PPT adversary A: Pr[A(G, p, g, g a1 , g a2 ) = g a1a2 ] = negl(λ), where

Lemma 23. The protocol in Fig. 4 satisfies statistical receiver's indistinguishability security.

Proof. The distribution of the receiver's message h 0 = g r X −c is uniformly random over the group G no matter that the receiver's bit c is. Proof. Let there be a PPT adversary A that breaks the elementary security of the sender. Then we are able to construct a PPT adversary B that breaks the CDH assumption. Recall that A receives a CRS X = g x , sends a group element h 0 , receives S = g s for a uniform s, and succeeds if he outputs y 0 = h s 0 , y 1 = h s 1 = (h 0 X) s . Our adversary against the CDH assumption receives G, p, g, A 1 := g a1 , A 2 := g a2 from his challenger, gives CRS X := A 1 to A, receives h 0 , gives S := A 2 to A, receives y 0 , y 1 and outputs y 1 /y 0 . If A succeeds

0 g a1a2 and therefore y 1 /y 0 = g a1a2 , meaning that B succeeds in solving CDH.

The above two lemmas already show that the scheme in Fig. 4 is a elementary OT scheme and we can then rely on our black-box transformations from the previous sections to then get UC secure OT under CDH assumption. Therefore, the following Theorem follows as a corollary.

Although the above lemmas already suffice to show the above corollary, we note that we can actually show something stronger about the scheme in Fig. 4 . Not only does it satisfy sender's elementary security, it already also satisfies the stronger notion of sender's search security. To show this, we implicitly rely on the random self-reducibility of the CDH problem. Fig. 4 With probability , crs X and random coins r are good, i.e. Pr[Exp crs,r,0 sOTiOT (A) = 1] > and Pr[Exp crs,r,1 sOTiOT (A) = 1] > . We condition on that being the case. Since S 0 and S 1 are independent, it holds with probability 2 that A 2 is successful for input (st, S 0 , 0) and input (st, S 1 , 1). Conditioned on that being the case, y 0 = h s0 0 = h a2+d1 0 and y 1 = h s1 1 = (h 0 · A 1 ) d2+a2 . Therefore it holds that the submitted CDH solution is

Hence, A solves CDH with at least probability 3 .

We now give an instantiation of an elementary OT under the learning parity with noise (LPN) assumption with noise rate ρ = n −ε for ε > 1 2 . This protocol only achieves imperfect correctness, with an inverse-polynomial failure probability, but we argue that this is sufficient to get UC OT with negligible error probability. 

In the following, we will use a variant of LPN, where the secret is sampled from the noise distribution rather than the uniform distribution and the first sample is errorless. This variant is known to be as hard as standard LPN. The two following lemmata give a more precise relation between LPN and its above described variant.

There is an efficient reduction from LPN with dimension n and noise distribution B ρ to LPN where the first sample is errorless with dimension n − 1 and noise distribution B ρ that reduces the advantage by at most probability 2 −n . is invertible. Then, A −1 , A −1 z A = s + A −1 e s will allow mapping LPN samples a, z = as + e to samples with secret s = e s by computing the new sample a = aA −1 , z + aA −1 z A = a s + e. In the case where e = 0, i.e. an errorless LPN sample, the resulting sample will also be errorless. Proof. We use a hybrid version of first is errorless LPN with a secret sampled from the noise distribution which is hard based on standard LPN with the same noise distribution and dimension n − 1, see Lemma 28 and Lemma 29. Hybrid LPN is as hard as standard LPN losing a factor 1 λ in the advantage. Let there be a malicious receiver that outputs y 0 , y 1 with probability > negl then there is a LPN distinguisher A that breaks hybrid first is errorless LPN with advantage . A operates as follows. It receives a LPN challenge v, A, z v , Z and sets CRS to A, v. After receiving h 0 , it sends Z to the malicious receiver and obtains y 0 , y 1 . If y 0 + y 1 = z v it outputs 1 otherwise 0.

Let Z = SA + E, z v = Sv, then A faithfully simulates the actual protocol. With probability , the malicious receiver will output (y 0 , y 1 ) = (Sh 0 , Sh 1 ). In this case y 0 + y 1 = Sv equals z v and A will output 1. In the uniform case, i.e. Z A and z v are uniform, hence the malicious receiver can output y 0 , y 1 such that y 0 + y 1 = z v at most with probability 2 −λ . Hence A breaks LPN with advantage λ − 2 −λ > negl. Fig. 5 with parameter ρ ≤ 1 n , for constant 1 > > 1 2 . Then with overwhelming probability 1 − negl(λ) over the coins of the receiver (i.e., x, e) we have the following probability of correctness over the coins of the sender (i.e., S, E): Pr

where 4λn 1−2 can be an arbitrary 1 poly(λ) for a suitable choice of n = poly(λ). Dealing with Imperfect Correctness. The above gives us an elementary OT scheme with imperfect correctness under LPN: with overwhelming probability over the coins of the receiver, we have a 1/p(λ) error-probability over the coins of the sender, where we can choose p(λ) to be an arbitrary polynomial. For concreteness we set p(λ) = λ 2 , so the error probability is 1/λ 2 . We outline how to leverage the series of generic transformations from the previous sections to get UC OT with a negligible correctness error. This requires only minor modifications throughout.

Elementary OT → Search OT (Theorem 7): This transformation performs a λ-wise parallel repetition on the sender message and therefore, by the union bound, increases the correctness error from 1/λ 2 to 1/λ. Security is unaffected. Search OT → bit-iOT (Theorem 8): This transformation preserves the correctness error of 1/λ. Security is unaffected. bit-iOT → string iOT (Theorem 9): Here, we can modify the transformation slightly and first encode the strings using an error-correcting code and have the receiver apply error correction. Since each bit has an independent error probability of 1/λ, we can set the parameters of the error-correcting code to get an exponentially small error probability, say 2 −2λ . Security is unaffected by this modification. Imperfect → Perfect Correctness: The above gives a scheme where, with overwhelming probability over the receiver's coins, we have a 2 −2λ error probability over the sender's coins. However, our definition of OT correctness in Sect. 4.1 requires a stronger notion of perfect correctness: with overwhelming over the receiver's coins and the CRS, all choices of the sender coins yield the correct output. This is needed in two places: (1) In the construction of 2-round ZK arguments (Theorem 19), we rely on extractable commitments, which in turn require a PKE with perfect correctness (Definition 3). Constructing PKE from OT requires the same perfect correctness for the OT.

(2) In the construction of UC OT from Sender-UC OT and ZK (Theorem 21) we also need the underlying Sender-UC OT to have perfect correctness. This is because we rely on the fact that if a malicious sender computes the secondround OT message correctly with some choice of random coins (which he proves via the ZK argument), then the receiver gets the correct value. We can generically achieve such perfect correctness, using an idea similar to the one behind Naor's commitments [Nao90] . We add an additional random value r * to the CRS. The sender computes his second-round OT message by relying on a pseudorandom generator G and setting the random coins to be G(s) ⊕ r * where s is small seed of length (e.g.,) λ. By a counting argument, with overwhelming probability over r * and the receiver's random coins, there is no choice of the sender's coins s that results in an error. Security is preserved by relying on the security of the PRG.

Combining the above, the following theorem follows as a corollary.

Theorem 33. Under the LPN assumption with noise rate ρ = n −ε for ε > 1 2 there exists a 2-round UC OT.

Fast cryptographic primitives and circular-secure encryption based on hard learning problems

Priced oblivious transfer: how to sell digital goods

More on average case vs approximation complexity

Two-message statistically sender-private OT from LWE

Two-message witness indistinguishability and secure computation in the plain model from new assumptions

k -round multiparty computation from k -round oblivious transfer via garbled interactive circuits

Classical hardness of learning with errors

Anonymous IBE, leakage resilience and circular security from new assumptions

Non-interactive oblivious transfer and applications

Universally composable security: a new paradigm for cryptographic protocols

Oblivious transfer with a memorybounded receiver

Hardness amplification of weakly verifiable puzzles

Universally composable two-party and multi-party secure computation

Universal composition with joint state

Laconic conditional disclosure of secrets and applications

Constant-round oblivious transfer in the bounded storage model

A randomized protocol for signing contracts

A hard-core predicate for all one-way functions

How to play any mental game or a completeness theorem for protocols with honest majority

Two-round multiparty secure computation from minimal assumptions

Smooth projective hashing and two-message oblivious transfer

Cryptographic hashing from strong one-way functions (or: one-way product functions and their applications)

Distinguisher-dependent simulation in two rounds and its applications

How to simulate it -a tutorial on the simulation proof technique

New constructions of reusable designated-verifier NIZKs

Bit commitment using pseudo-randomness

Efficient oblivious transfer protocols

A framework for efficient and composable oblivious transfer

How to exchange secrets with oblivious transfer

Protocols for secure computations (extended abstract)