1 Introduction

Oblivious transfer (OT) [26, 37] is a fundamental cryptographic primitive that serves as a building block for a number of interesting applications, such as secure two-party and multi-party computation. In this work, we mainly focus on 1-out-of-2 string oblivious transfer, which is a two-party primitive. In this flavor of OT, the sender \(\mathsf {Alice} \) inputs two strings \(m_0\) and \(m_1\), and the receiver \(\mathsf {Bob} \) inputs a choice bit c, obtaining \(m_c\) as the output. Bob must not be able to learn \(m_{1-c}\), while Alice must not learn c. Since oblivious transfer is normally used within other protocols as a primitive, it is desirable to ensure that its security is guaranteed even under arbitrary composition.

The Universal Composability (UC) framework [7] is the most widely used methodology for analyzing protocol security under arbitrary composition. OT protocols UC-secure against static malicious adversaries can be designed under several computational assumptions, such as: Decisional Diffie-Hellman (DDH) [28, 36], strong RSA [28], Quadractic Residuosity (QR) [36], Decisional Linear (DLIN) [16, 32], Decisional Composite Residuosity (DCR) [13, 32], McEliece Assumptions [19], low noise Learning Parity with Noise (LPN) [18] and Learning with Errors (LWE) [36]. Furthermore, there exist constructions based on simple generic primitives such as enhanced trapdoor functions [11] and public-key encryption plus semi-honest stand alone oblivious transfer [31], which mostly do not achieve the same efficiency as the constructions that leverage properties of specific computational assumptions.

It is a well-known fact that UC-secure OT protocols require a setup assumption [9]. Coincidentally, most of the UC-secure OT protocols (including the aforementioned ones) are based in the Common Reference String (CRS) model, where the parties are assumed to have access to a string randomly sampled from a given distribution before execution starts. While this setup assumption allows for the construction of efficient UC-secure OT protocols under a number of assumptions, questions have been raised about its practicality [10, 14], since a local CRS is not readily available for a real world implementation of a protocol. Notice that OT can be UC-realized under a number of alternative setup assumptions, such as the public-key infrastructure model [15], the random oracle model (ROM) [3, 5], noisy channels [24], tamper-proof hardware [23, 25, 33]. However, these models still require each instance of the protocol to access a local instance of the setup assumption. Informally, it means that each instance of the protocol uses an instance of the ideal functionality representing the setup assumption that is independent from all other instances and accessible only to the parties participating in the protocol execution but not to the environment.

Assuming that each protocol instance has local access to an independent setup in order to obtain secure composition is far from optimal and results in several issues that have been pointed out in previous works [4, 8, 10]. In particular, assuming the existence of independent random oracles (RO) for each protocol instance contradicts the common practice of replacing a random oracle by a standardized hash function, which is freely accessible and used by everybody. Such issues were first analyzed and addressed by Canetti et al. [8], who proposed the “Generalized UC model”, where it is assumed that the instance of the trusted setup is globally available (and therefore also accessible by the environment) and used by all protocol instances. This formalism was subsequently extended to the random oracle setting by Canetti et al. [10], who define a global random oracle model, where a single instance of the random oracle \(\mathcal {F}_{\mathrm {gRO}} \) is directly accessible by all parties, the adversary and the environment. Such a model precludes the use of proof techniques that require the simulator to “program” the random oracle’s answers to a given query, which are usually employed in random oracle based constructions. UC protocols based on a local programmable CRS also suffer from issues similar to those of local programmable ROs [10], and formally the security guarantees for protocols based on local setups (e.g. local CRS or programmable RO) only hold if a new fresh setup is available for each individual instance of the protocol, which is unrealistic. It is not known how to generate even a single CRS without heuristics, let alone a fresh one for each execution. Quoting Canetti et al. [10] on the strength of the global random oracle model: “This model provides significantly stronger composable security guarantees than the traditional random oracle model of Bellare and Rogaway [3] or even the common reference string model”. Note that more than one trusted setup instance can be available (in our construction we use 3 instances of global RO), but they should be globally available and not local for a protocol instance. Surprisingly, Canetti et al. [10] showed that using \(\mathcal {F}_{\mathrm {gRO}} \) as a setup assumption it is possible to construct universally composable DLOG based commitments and DDH based two-party computation and non-interactive secure computation secure against static malicious adversaries. Recently, new results in the global ROM were proven assuming certain relaxations of the model [6]. However, no efficient oblivious transfer protocol in the global random oracle model has been proposed so far.

1.1 Our Contributions

We first propose a generic protocol for universally composable oblivious transfer secure against active static adversaries in the global random oracle model of [10]. The central building block of this construction is a One-Way Chosen Plaintext Attack (OW-CPA) secure public-key encryption (PKE) scheme with a number of properties. We show that such a scheme can be efficiently instantiated under the Computational Diffie Hellman (CDH) assumption. Our results can be summarized as follows:

  • The first UC-secure OT protocol based on the CDH assumption.Footnote 1

  • The first UC-secure OT protocol in the Global Random Oracle model [10] that achieves efficiency for single executions (without OT extension) comparable to the most efficient previous work [36], which requires a programmable CRS.Footnote 2

In order to obtain a protocol based on an assumption as weak as CDH, we introduce novel simulation techniques for extracting choice bits and messages in the simulation without resorting to programming the random oracle, which is not possible in the global random oracle model of Canetti et al. [10]. Notice that previous works required stronger computational assumptions (e.g. DDH [5, 36]) even though they relied on stronger local setup assumptions (e.g. CRS [36] and programmable random oracles [5]). Hence, in comparison to such previous works, our results improve on both the computational and setup assumptions required for UC-secure OT.

In terms of efficiency, our protocols compare favorably to previous works based on stronger assumptions. In the setting where one wishes to execute a large number of OTs through OT extension, the costs of each seed OT with our CDH based protocol are only the computation of 6 modular exponentiations and the communication of 5 group elements, 5 binary strings of security parameter length, and 2 binary strings of message length. In the setting where few OTs are needed, our CDH based protocol requires 15 modular exponentiations and the communication of 9 group elements, 9 binary strings of security parameter length, and 4 binary strings of message length. We remark that, in contrast to previous works based on local setup assumptions, our protocols can be readily implemented while retaining their security properties by substituting the global random oracle by an extensively tested cryptographic hash function (e.g. SHA3).

As an intermediate step towards our CDH based construction, we first design a generic protocol based on a public-key encryption scheme with certain properties. We start by constructing a generic protocol that realizes an OT functionality that captures a selective failure issue, which is nevertheless sufficient for instantiating efficient OT extension protocols as shown in [21]. Interestingly, our protocol achieves high efficiency, requiring only one key generation operation, two encryption operations and one decryption operation, apart from a few calls to the random oracle. In terms of communication, our protocol only requires the transfer of one public-key, two ciphertexts, five binary strings of security parameter length, and two binary strings of message length. Later on, we obtain a generic protocol that realizes the standard OT functionality (without any selective failure) by augmenting our original protocol with four encryptions, one decryption, two ciphertexts, two binary strings of security parameter length and two binary strings of message length. If hundreds of OTs are needed, our OT with selective failures represents a new option of base OT for use with OT extension schemes. If only tens of OTs are needed, our OT without selective failures is a good option for usage. Besides yielding a CDH based instantiation, these generic protocols can be potentially instantiated under other assumptions, paving the way to post-quantum secure constructions of UC-secure OT under lattice and coding based assumptions.

1.2 Related Works

The global random oracle model has been established by Canetti et al. in [10], where they also build UC-secure commitments, two-party computation and non-interactive secure computation (NISC) secure against static malicious adversaries. In their construction of NISC in the global ROM, they state that a natural way to construct such a protocol would be to instantiate existing approaches based on 2-round OT with a global ROM version of the originally CRS based UC-secure OT protocol by Peikert et al. [36]. However, they observe that there are significant challenges in obtaining such a global ROM version of the protocol by Peikert et al., and instead construct a one-side simulatable OT protocol that is only UC-secure against a malicious receiver. Their solution is not generic but intrinsically based on DDH via non-black-box use of the OT protocol of [36], only implying 2-round UC OT based on DDH, and with communication/computation costs several orders of magnitude higher than ours. On the other hand, ours is the first UC OT in the GRO built in a black-box way from a generic primitive (a PKE that we define), yielding the first UC OT based on CDH (a weaker assumption) while achieving much lower computation/communication costs. Even though the global ROM was recently revisited in [6], allowing for relaxations such as programming the random oracle in specific situations, no new results related to oblivious transfer were proposed in this relaxed model.

The idea of constructing OT using two public-keys—the “pre-computed” one and the “randomized” one dates back to early days of OT development [2, 26]. Naor and Pinkas [35] presented an improved stand alone CDH-based protocol in the (local) random oracle model under the same approach that is proven secure in the half-simulation paradigm. A recent result by Friolo et al. [27] shows how to construct 4 round fully simulatable OT from key agreement protocols with certain properties without requiring setup assumptions, which yields a protocol based on CDH. However, their results fundamentally fall short of UC security (since UC-secure OT protocols necessarily require a setup assumption [9]) and cannot be easily adapted to this setting.

We remark that the “Simplest OT” protocol [14] and the protocol by Hauck and Loss [30] have been found to suffer from a number of issues [5, 29] and are not UC secure. The CDH based protocol of [21] only realizes an OT functionality with a selective failure (as our first simple construction) and it is unclear how to use it to realize the standard OT functionality (without selective failure). The UC OT protocol of [1] can also be instantiated from a similar generic public key encryption scheme, for which a CDH instantiation is presented (among other assumptions). However, in order to prove the security of the construction of [1], it is also necessary to assume that the public key encryption scheme has circular security, which is an ad-hoc assumption not proven under CDH.

Independent and Concurrent Works: Döttling et al. [22] proposed a generic round optimal UC-secure OT protocol in the CRS model that can be instantiated from CDH. However, even though their protocol solves the important problem of achieving round optimality, it has computational and communication complexities orders of magnitude higher than our protocol, making it impractical. These overheads are intrinsic to the use of generic zero-knowledge proofs and garbled circuits in their construction. Canetti et al. [12] introduced a CDH based OT protocol that is UC-secure in the Global Random Oracle model. Similarly to our initial result, they focus on obtaining OT with selective failures in order to achieve better efficiency when using their protocol as basis for OT extension. However, differently from our final result, they do not show how to eliminate selective failures in their protocol without using OT extension.

1.3 Our Techniques

At a high level, we start by building a simple generic protocol that realizes a weak version of the OT functionality, which allows for a selective failure attack. Starting from this weak flavor of OT is useful because it allows us to showcase our techniques more clearly while still being useful for performing OT extension, which results in an unlimited number of standard OTs (without selective failures) at very high efficiency. We then lift our protocol with selective failures to a generic protocol that realizes the standard OT functionality by leveraging subtleties of the first, simpler, construction. The central building block for both protocols is a public-key encryption (PKE) scheme satisfying a number of properties, which we construct based on the CDH assumption departing from the ElGamal cryptosystem. In order to provide some intuition on the design of our schemes, we informally describe properties we require from our PKE scheme and discuss how they are used to build our protocols:

  • Property 1 (informal): Let the public-key space \(\mathcal {PK} \) form a group with operation denoted by “\(\star \)”. Then, for the public-keys \((\mathsf {pk} _0,\mathsf {pk} _1)\), such that \(\mathsf {pk} _0 \star \mathsf {pk} _1 =q\), where q is chosen uniformly at random from \(\mathcal {PK} \), one cannot decrypt both ciphertexts encrypted using \(\mathsf {pk} _0\) and \(\mathsf {pk} _1\), respectively. In particular, when a public/secret-key pair \((\mathsf {pk} _c,\mathsf {sk} _c)\) is generated, the above relationship guarantees that \(\mathsf {pk} _{1-c}\) that is chosen to satisfy the constraint \(\mathsf {pk} _0 \,\star \, \mathsf {pk} _1 =q\) is “substantially random”, so that learning the messages encrypted with \(\mathsf {pk} _{1-c}\) is hard.

  • Property 2 (informal): \(\mathsf {pk} \) obtained using the key generation algorithm is indistinguishable from a random element of \(\mathcal {PK} \). Note that we assume in this work that not all the elements of \(\mathcal {PK} \) may represent valid public-keys.

  • Property 3 (informal): The PKE scheme must be “committing”, meaning that it must be impossible to generate two pairs of randomness and plaintext messages \((\mathsf {r} _0,\mathsf {m} _0)\) and \((\mathsf {r} _1, \mathsf {m} _1)\) with \(\mathsf {m} _0 \ne \mathsf {m} _1\) such that encrypting \(\mathsf {m} _0\) with randomness \(\mathsf {r} _0\) under a uniformly random public-key \(\mathsf {pk} \) yields the same ciphertext as encrypting \(\mathsf {m} _1\) with randomness \(\mathsf {r} _1\) under the same public-key.

  • Property 4 (informal): Property 3 only holds for key pairs generated according to the key generation algorithm or picked at random, but not for arbitrary key pairs, which could be crafted to be “non-committing”. Intuitively, this property says that encrypting a message under such an arbitrary “non-committing” public key will also cause some message bits to be lost, which will come in handy in the security proof.

  • Property 5 (informal): The PKE scheme has a witness-recovering decryption algorithm that outputs the randomness used to generate the decrypted ciphertext along with the plaintext message.

A Toy Example: Consider a very simple protocol where the receiver generates a key pair \((\mathsf {pk} _c,\mathsf {sk} _c)\), queries a global RO with a random seed value s to obtain q, computes \(\mathsf {pk} _{1-c}\) such that \(\mathsf {pk} _0 \star \mathsf {pk} _1 =q\), and sends \(\mathsf {pk} _0\) and s to the sender. The latter recomputes \(\mathsf {pk} _1\) from \(\mathsf {pk} _0\) and s with the help of the RO and uses the public-keys to encrypt random seeds. The sender then uses these seeds to generate one-time pads (using the global RO) that she uses to encrypt her messages, sending both the PKE ciphertexts containing the seeds and the one-time pad encryptions of the actual messages to the receiver. The receiver can retrieve the seed encrypted under \(\mathsf {pk} _c\) (since he has \(\mathsf {sk} _c\)), compute the one-time pad with the help of the global RO and retrieve the message associated with his choice bit c. Intuitively, Property 2 now prevents the sender from learning the choice bit, while Property 1 ensures that the receiver learns at most one of the inputs.

While this simple protocol intuitively implements a stand alone oblivious transfer, it is hard to construct a simulator to prove it UC-secure in the global RO model. If programming the RO was allowed, the simulator could program the answer of the RO to a query s in such a way that it knows the secret keys corresponding to both \(\mathsf {pk} _0\) and \(\mathsf {pk} _1\), allowing it to extract the messages from a corrupted sender. In the case of a corrupted receiver, the simulator could wait for the RO to be queried on one of the one-time pad seed (extracting the choice bit), retrieve the message associated to that choice bit and program the answer of this RO query in such a way that the one-time pad encryption related to that seed decrypts to the message obtained from the OT functionality. However, the global RO model precludes us from using any of these techniques. Instead, we develop novel techniques for extracting both a corrupted receiver’s choice bit and a corrupted sender’s messages solely by observing global RO queries.

OT with Selective Failures: As a starting point, we design a protocol that UC-realizes a weaker version of the OT functionality, which captures a selective failure attack. This attack allows a malicious sender to try and “guess” the receiver’s choice bit, only being caught if her guess is wrong. Allowing this selective failure makes it easier to implement mechanisms used by the simulator to extract the choice bit from a malicious receiver without the need to program the random oracle. Even though this protocol has a selective failure issue, it has been shown in [21] that it is sufficient to instantiate efficient OT extension protocols such as the one of [34]. Many applications require such a high number of oblivious transfers that it makes sense to use an actual OT protocol only to seed an OT extension, which can then be used for an unlimited number of OTs at very low cost. In order to simulate an execution with a corrupted receiver, we augment our simple protocol with a challenge-response mechanism inspired by [21] that forces the receiver to query the global RO in such a way that it reveals its choice bit to the simulator. In the real world protocol, the adversary can mount a selective failure attack where it can “guess” the receiver’s choice bit, being caught if it guesses the wrong bit. However, a simulator who can observe the queries made to the global RO can easily determine the receiver’s choice bit without resorting to a selective failure attack. This mechanism works by having the sender pick two random values \(\mathsf {p}_0,\mathsf {p}_1\), compute a challenge \(\mathsf {ch}= \mathsf {H}(\mathsf {H}(\mathsf {p}_0)) + \mathsf {H}(\mathsf {H}(\mathsf {p}_1))\) where \(\mathsf {H}(\cdot )\) is the random oracle and send this challenge to the receiver along with encryptions of \(\mathsf {p}_0,\mathsf {p}_1\). The receiver decrypts \(\mathsf {p}_c\) corresponding to its choice bit and answers with \(\mathsf {chr}=\mathsf {H}(\mathsf {H}(\mathsf {p}_c)) + c \cdot \mathsf {ch}\), which will always be \( \mathsf {H}(\mathsf {H}(\mathsf {p}_0))\) when \(\mathsf {ch}\) is computed correctly. After receiving \(\mathsf {chr}\), the sender provides the receiver with \(\mathsf {H}(\mathsf {p}_0)\) and \(\mathsf {H}(\mathsf {p}_1)\), so that it can check that \(\mathsf {ch}\) was correctly computed and that \(\mathsf {H}(\mathsf {p}_c)\) is consistent with the value it decrypted. However, a malicious sender can always guess the receiver’s choice bit and compute \(\mathsf {ch}\) in such a way that it will learn the actual choice bit but only be caught if it guesses wrong. Due to Properties 1 and 3, the simulator can be assured that the query \(\mathsf {p}_c\) done by the receiver corresponds to its choice bit. The case of a corrupted sender is handled by a novel technique where the sender is forced to query the global RO in a way that reveals both of its messages to a simulator who can observe RO queries. The basic idea is to modify the challenge-response mechanism by having the sender query the global RO not only with the challenge seed \(\mathsf {p}_i\) but also adding the public-key \(\mathsf {pk} _i\), and randomness \(\mathsf {r} _i\) used to encrypt \(\mathsf {p}_i\) to the query. Using Property 5, the receiver can complete the challenge-response mechanism since it can recover \(\mathsf {r} _i\) used in the encryption of \(\mathsf {p}_i\). Using Property 3, the simulator is assured that a malicious sender could only have generated one such query for each pair of value \(\mathsf {p}_i\) and randomness \(\mathsf {r} _i\). Hence, the simulator can check which pairs \(\mathsf {r} _i,\mathsf {p}_i\) in the list of queries to the global RO results in the ciphertexts sent by the sender when used as input to an encryption under \(\mathsf {pk} _i\). After extracting both \(\mathsf {p}_0,\mathsf {p}_1\), the simulator detects whether the adversary is trying to guess the choice bit (as well as the bit being guessed), which it forwards to the functionality. Later on, the sender uses the same \(\mathsf {p}_i\) and corresponding randomness \(\mathsf {r} _i\) to query a different instance of the global RO and obtain a one-time pad used to encrypt the actual messages it wants to transfer. Hence, the simulator can also use \(\mathsf {p}_0,\mathsf {p}_1\) to extract both messages transferred by a malicious sender.

Eliminating Selective Failures: We are also interested in solving the problem of directly UC-realizing a standard OT functionality in the observable global random oracle model. In order to do so, we must eliminate the selective failure issue of our first protocol. We observe that we can do so by basically running two instances of our first protocol in parallel with the same public-keys \(\mathsf {pk} _0\) and \(\mathsf {pk} _1\). Notice that these public-keys encode the choice bit, meaning that the same choice bit is used in both instances. The first instance will be used to extract the receiver’s choice bit while ensuring a malicious sender cannot learn it through a selective failure attack. The other instance will be used to execute an oblivious transfer with the previously extracted choice bit and random messages, which can be later derandomized through standard techniques. We will run both protocol instances with a random choice bit, so that the receiver’s actual choice bit does not leak in case the sender mounts a selective failure attack, which will be detected causing the execution to abort. In one of these instances, we will execute the challenge-response mechanism with the additional requirement that the sender must reveal both \(\mathsf {p}_0,\mathsf {r} _0\) and \(\mathsf {p}_1,\mathsf {r} _1\), allowing the receiver to be sure no selective failure attack occurred. With this instance we are able to extract the receiver’s random choice bit while ensuring that in the second instance the same bit will be used (because it is encoded in the keys \(\mathsf {pk} _0\) and \(\mathsf {pk} _1\), also used in the second instance). In the second instance, we do not execute the challenge-response mechanism but use \(\mathsf {pk} _0\) and \(\mathsf {pk} _1\) to encrypt a second pair of seeds \(\hat{\mathsf {p}}_0,\hat{\mathsf {p}}_1\) with randomness \(\mathsf {r} _0',\mathsf {r} _1'\), which the sender queries to another instance of the global RO to obtain one-time pads for random messages being transferred. Due to Property 3, the simulator can extract \(\hat{\mathsf {p}}_0,\hat{\mathsf {p}}_1\) from the queries to the global RO and retrieve these random messages. At this point we have executed a random oblivious transfer, which is then derandomized to the receiver’s actual choice bit and the sender’s actual messages using standard information theoretical techniques.

2 Preliminaries

We denote by \(\kappa \) the security parameter. Let \(y {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}F(x)\) denote running the randomized algorithm F with input x and random coins, and obtaining the output y. When the coins r are specified we use \(y \leftarrow F(x;r)\). Similarly, \(y \leftarrow F(x)\) is used for a deterministic algorithm. For a set \(\mathcal{X}\), let \(x {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathcal{X}\) denote x chosen uniformly at random from \(\mathcal{X}\); and for a distribution \(\mathcal{Y}\), let \(y {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathcal{Y}\) denote y sampled according to the distribution \(\mathcal{Y}\). We will denote by \(\mathsf {negl}(\kappa )\) the set of negligible functions of \(\kappa \). We abbreviate probabilistic polynomial time as PPT.

Encryption Schemes: The main building block used in our OT protocol is a public-key encryption scheme \(\mathsf {PKE} \). It has public-key \(\mathcal {PK} \), secret-key \(\mathcal {SK} \), message \(\mathcal {M} \), randomness \(\mathcal {R} \) and ciphertext \(\mathcal {C} \) spaces that are functions of the security parameter \(\kappa \), and consists of a PPT key generation algorithm \(\mathsf {KG} \), a PPT encryption algorithm \(\mathsf {Enc} \) and a deterministic decryption algorithm \(\mathsf {Dec} \). For \((\mathsf {pk},\mathsf {sk}){\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathsf {KG} (1^\kappa )\), any \(\mathsf {m} \in \mathcal {M} \), and \(c {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathsf {Enc} (\mathsf {pk},\mathsf {m})\), it should hold that \(\mathsf {Dec} (\mathsf {sk},\mathsf {ct})=\mathsf {m} \) with overwhelming probability over the used randomness.

We should emphasize that for some encryption schemes not all \(\widetilde{\mathsf {pk}} \in \mathcal {PK} \) are “valid” in the sense of being a possible output of \(\mathsf {KG} \). The same holds for \(\widetilde{\mathsf {ct}} \in \mathcal {C} \) in relation to \(\mathsf {Enc} \) and all possible coins and messages. Our OT protocol uses as a building block a \(\mathsf {PKE} \) that satisfies a variant of the OW-CPA security notion: informally, two random messages are encrypted under two different public-keys, one of which can be chosen by the adversary (but he does not have total control over both public-keys). His goal is then to recover both messages and this should be difficult. Formally, this property is captured by the following definition.

Property 1

(Double OW-CPA Security). Consider the public-key encryption scheme \(\mathsf {PKE} \) and the security parameter \(\kappa \). It is assumed that \(\mathcal {PK} \) forms a group with operation denoted by “\(\star \)”. For every PPT two-stage adversary \(\mathcal {A} =(\mathcal {A} _1,\mathcal {A} _2)\) running the following experiment:

figure a

it holds that

$$ \Pr [(\widetilde{\mathsf {m} _0},\widetilde{\mathsf {m} _1}) = (\mathsf {m} _0,\mathsf {m} _1) ] \in \mathsf {negl}(\kappa ). $$

We also need a property about the indistinguishability of a public-key generated using \(\mathsf {KG} \) and an element sampled uniformly at random from \(\mathcal {PK} \).

Property 2

(Pseudorandomness of Public-Keys). Consider the public-key encryption scheme \(\mathsf {PKE} \) and the security parameter \(\kappa \). Let \((\mathsf {pk},\mathsf {sk}) {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathsf {KG} (1^\kappa )\) and \(\mathsf {pk} ' {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathcal {PK} \). For every PPT distinguisher \(\mathcal {A} \), it holds that

$$ | \Pr [\mathcal {A} (\mathsf {pk}) = 1 ] - \Pr [\mathcal {A} (\mathsf {pk} ') = 1 ] | \in \mathsf {negl}(\kappa ). $$

Moreover, we need the \(\mathsf {PKE} \) scheme to be committing, meaning that an adversary can only generate two different pairs of randomness and plaintext message that result in the same ciphertexts when encrypted under a uniformly random public-key with negligible probability.

Property 3

(Committing Encryption). Consider the public-key encryption scheme \(\mathsf {PKE} \) and the security parameter \(\kappa \). For every PPT adversary \(\mathcal {A} \), it holds that:

figure b

Note that if Properties 2 and 3 hold for some \(\mathsf {PKE} \), then the modified version of Property 3 in which \(\mathsf {pk} \) is chosen using \(\mathsf {KG} \) also trivially holds. Moreover, we will need a variation of the committing property stating that even if an adversary is allowed to provide an arbitrary secret and public-key pair, it cannot both decrypt a ciphertext generated under that public-key and break the standard committing property. The rationale behind this property is that, for some committing encryption schemes, an adversary can generate an arbitrary public-key that breaks the standard committing property. However, in most cases, such a public-key will also cause plaintext information to be lost, making it impossible for the adversary to recover the original message from a ciphertext encrypted under this key with probability 1. This property is formalized in Property 4.

Property 4

(Committing Encryption with Arbitrary Keys). Consider the public-key encryption scheme \(\mathsf {PKE} \) and the security parameter \(\kappa \). For every PPT two-stage adversary \(\mathcal {A} =(\mathcal {A} _1,\mathcal {A} _2)\) running the following experiment:

figure c

it holds that

$$ \Pr [\mathsf {m} '=\mathsf {m} \wedge \mathsf {r} ' = \mathsf {r} \wedge (\mathsf {m} _i,\mathsf {r} _i) \ne (\mathsf {m},\mathsf {r}) \wedge \mathsf {ct} \leftarrow \mathsf {Enc} (\mathsf {pk},\mathsf {m} _i,\mathsf {r} _i) \; \forall \; i=1,\ldots ,{n-1} ] \le \frac{1}{n} + \mathsf {negl}(\kappa ). $$

We require \(\mathsf {PKE} \) to have a witness-recovering decryption algorithm. Informally, this property means that the decryption algorithm also recovers the randomness used to generate the ciphertext it takes as input. Witness-recovering decryption is formally defined in Property 5.

Property 5

(Witness-Recovering Decryption). A public-key encryption scheme \(\mathsf {PKE} =(\mathsf {KG},\mathsf {Enc}, \mathsf {Dec})\) has a witness-recovering decryption algorithm \(\mathsf {Dec} \) if it takes as input the secret-key \(\mathsf {sk} \in \mathcal {SK} \) and a ciphertext \(\mathsf {ct} \in \mathcal {C} \) and outputs either a pair \((\mathsf {m},\mathsf {r})\) for \(\mathsf {m} \in \mathcal {M} \) and \(\mathsf {r} \in \mathcal {R} \) or an error symbol \(\perp \). For any \((\mathsf {pk},\mathsf {sk}){\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathsf {KG} (1^\kappa )\), any \(\mathsf {m} \in \mathcal {M} \), any \(\mathsf {r} {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathcal {R} \) and \(c \leftarrow \mathsf {Enc} (\mathsf {pk},\mathsf {m}; \mathsf {r})\), it should hold that \(\mathsf {Dec} (\mathsf {sk},\mathsf {ct})=(\mathsf {m},\mathsf {r})\) with overwhelming probability over the randomness used by the algorithms.

In the full version [17], we prove that Properties 1, 2, 3 and 4 hold for the ElGamal cryptosystems based on the CDH assumption, yielding an efficient instantiation of our generic protocol. Even though the ElGamal cryptosystem does not have a straightforward witness-recovery decryption algorithm, we show how any OW-CPA secure public-key encryption scheme used on random messages can be augmented with such a decryption algorithm to achieve Property 5. This can be done through the encrypt-with-hash paradigm, where the randomness used for encryption is obtained by hashing the message being encrypted, which can be proven secure in the non-programmable random oracle model.

Fig. 1.
figure 1

Functionality \(\mathcal {F}_{\mathrm {gRO}}\).

Full size image

Universal Composability in the Global Random Oracle Model: We analyze our protocol in the UC model with global random oracles as presented in [10]. We refer interested readers to the original work for more details on the UC framework [7]. In the UC model with global random oracles, the parties are assumed to have access to a global random oracle functionality \(\mathcal {F}_{\mathrm {gRO}} \) (see Fig. 1 for details) and interfaces that leak the list of illegitimate queries \(\mathcal{Q}_{\mid s}\) to the adversary. Differently from the basic UC model, the global random oracle model allows all parties (including the environment) to access a single instance of \(\mathcal {F}_{\mathrm {gRO}} \). The \(\mathcal {F}_{\mathrm {gRO}} \) functionality functions as a regular random oracle but is augmented with a mechanism for leaking queries performed by parties that are not part of a given execution. In the UC model parties are identified by a unique pair of program id (PID) and session id (SID). Queries that are no prepended with the same SID as the one identifying the party \(P=(\mathsf {pid},\mathsf {sid})\) making the query are added to a list of illegitimate queries that can be requested by instances of functionalities whose session id match the one in the query. This mechanism allows the simulator to learn queries made by the environment or adversary but keeps the queries made by honest parties secret (as honest parties will follow the protocol and prepend their queries with the correct SID). Moreover, the functionalities in the global random oracle model take into consideration the existence of this list of illegitimate queries, requesting it from \(\mathcal {F}_{\mathrm {gRO}} \) and handing it to the adversary, if requested by the adversary. Our construction will actually use three instances of \(\mathcal {F}_{\mathrm {gRO}} \): \(\mathcal {F}_{\mathrm {gRO}1} \) with range \(\mathcal {PK} \), \(\mathcal {F}_{\mathrm {gRO}2} \) with range \(\{0,1\}^{\lambda }\) and \(\mathcal {F}_{\mathrm {gRO}3} \) with range \(\{0,1\}^{\kappa }\).

We consider a static malicious adversary. I.e., it can deviate from the prescribed protocol in an arbitrary way, but has to corrupt the parties before the execution starts.

Fig. 2.
figure 2

Functionality \(\mathcal {F}_{\mathrm {SFOT}}^\lambda \) in the global random oracle model.

Full size image

Oblivious Transfer: The functionality \(\mathcal {F}_{\mathrm {OT}}^{\lambda ,\ell } \) that provides \(\ell \) instances of the 1-out-of-2 string (of length \(\lambda \)) oblivious transfer in the \(\mathcal {F}_{\mathrm {gRO}} \)-hybrid model is presented in the full version [17]. This work focus on obtaining a weaker form of oblivious transfer that allows selective failure attacks, aiming for the same type of weaker OT as in Doerner et al. [21]. The ideal functionality \(\mathcal {F}_{\mathrm {SFOT}}^\lambda \) for 1-out-of-2 string oblivious transfer with selective failure in the \(\mathcal {F}_{\mathrm {gRO}} \)-hybrid model is described in Fig. 2. Essentially, the sender is given the option of trying to guess the choice bit of the receiver. If she makes a wrong guess, the cheating is detected and the execution aborts. If she makes a right guess, she learns the choice bit and nothing is detected by the receiver. As proved by Doerner et al. in the full version of their work [20], \(\mathcal {F}_{\mathrm {SFOT}}^\lambda \) can be used as the base OTs in the OT extension protocol of Keller et al. [34] to UC-realize \(\mathcal {F}_{\mathrm {OT}}^{\lambda ,\ell } \).

Lemma 1

The OT extension protocol of Keller et al. [34] UC-realizes \(\mathcal {F}_{\mathrm {OT}}^{\lambda ,\ell } \) in the \(\mathcal {F}_{\mathrm {SFOT}}^\lambda ,\mathcal {F}_{\mathrm {gRO}} \)-hybrid model.

Proof

This follows directly from Lemma D.3 of [20], which proves that the first part of the OT extension protocol UC-realizes the correlated OT with errors functionality \(\mathcal {F}_{\mathrm {COTe}}\) in the \(\mathcal {F}_{\mathrm {SFOT}}^\lambda ,\mathcal {F}_{\mathrm {gRO}} \)-hybrid model, and the reduction from \(\mathcal {F}_{\mathrm {OT}}^{\lambda ,\ell } \) to \(\mathcal {F}_{\mathrm {COTe}}\) using the remaining steps of the OT extension protocol [34].

Fig. 3.
figure 3

Protocol \(\pi _{\textsf {SFOT}}\)

Full size image

3 The Generic Protocol

Our protocol uses as a building block a public-key encryption scheme that satisfies Properties 1, 2, 3, 4 and 5 (defined in Sect. 2). The basic high-level idea is that \(\mathsf {Bob} \) picks two public-keys \(\mathsf {pk} _0,\mathsf {pk} _1\) such that he only knows the secret-key corresponding to \(\mathsf {pk} _c\) (where c is his choice bit) and hands them to \(\mathsf {Alice} \). She then uses the two public-keys to transmit two messages in an encrypted way, so that \(\mathsf {Bob} \) can only recover the message for which he knows the secret-key \(\mathsf {sk} _c\).

A crucial point in such schemes is making sure that \(\mathsf {Bob} \) is only able to decrypt one of the messages. In order to enforce this property, our protocol relies on Property 1 and uses the random oracle to force the element q to be chosen uniformly at random from \(\mathcal {PK} \). After generating the pair of public and secret-key \((\mathsf {pk} _c,\mathsf {sk} _c)\), \(\mathsf {Bob} \) samples a seed \(s\), queries the random oracle \(\mathcal {F}_{\mathrm {gRO}1} \) with \(s\) to obtain q, and computes \(\mathsf {pk} _{1-c}\) such that \(\mathsf {pk} _0 \star \mathsf {pk} _{1} =q\). \(\mathsf {Bob} \) then hands the public-key \(\mathsf {pk} _0\) and the seed \(s\) to \(\mathsf {Alice} \), enabling her to also compute \(\mathsf {pk} _1\). Since the public-keys are indistinguishable according to Property 2, \(\mathsf {Alice} \) learns nothing about \(\mathsf {Bob} \)’s choice bit. Next, \(\mathsf {Alice} \) picks two uniformly random strings \(\mathsf {p}_0,\mathsf {p}_1\), queries them to the random oracle \(\mathcal {F}_{\mathrm {gRO}2} \) obtaining \(\widetilde{\mathsf {p}_0},\widetilde{\mathsf {p}_1}\) as response, and then she computes one-time pad encryptions of her messages \(\mathsf {m}_0,\mathsf {m}_1\) as \(\widetilde{\mathsf {m}_0} = \mathsf {m}_0 \oplus \widetilde{\mathsf {p}_0}\) and \(\widetilde{\mathsf {m}_1} = \mathsf {m}_1 \oplus \widetilde{\mathsf {p}_1}\). \(\mathsf {Alice} \) also computes \(\mathsf {ct} _0 \leftarrow \mathsf {Enc} (\mathsf {pk} _0,\mathsf {p}_0;\mathsf {r} _0)\), \(\mathsf {ct} _1 \leftarrow \mathsf {Enc} (\mathsf {pk} _1,\mathsf {p}_1;\mathsf {r} _1)\) and sends \((\widetilde{\mathsf {m}_0},\widetilde{\mathsf {m}_1},\mathsf {ct} _0,\mathsf {ct} _1)\) to \(\mathsf {Bob} \). \(\mathsf {Bob} \) can use \(\mathsf {sk} _c\) to decrypt \(\mathsf {ct} _c\) obtaining \(\mathsf {p}_c\). He then queries \(\mathsf {p}_c\) to the random oracle \(\mathcal {F}_{\mathrm {gRO}2} \) obtaining \(\widetilde{\mathsf {p}_c}\) as response, and retrieves \(\mathsf {m}_c=\widetilde{\mathsf {m}_c} \oplus \widetilde{\mathsf {p}_c}\). Due to Property 1, \(\mathsf {Bob} \) will not be able to recover \(\mathsf {p}_{1-c}\) in order to query it to the random oracle and to decrypt \(\widetilde{\mathsf {m}_{1-c}}\). Therefore, the security for \(\mathsf {Alice} \) is also guaranteed.

Even though this simple protocol seemingly performs an oblivious transfer, it poses significant challenges for a proof in the Global Random Oracle model of Canetti et al. [10], where the simulator cannot program the answers to random oracle queries. In the case of a malicious sender, the simulator would need to generate a seed \(s\) and public key \(\mathsf {pk} _0\) such that it knows both secret keys associated to the resulting public keys \(\mathsf {pk} _0\) and \(\mathsf {pk} _1\), which it needs to know in order to extract the messages \(\mathsf {m}_0\) and \(\mathsf {m}_1\). However, while this is easy if the simulator could program an arbitrary random oracle answer given the seed \(s\), it cannot be done in this model. In the case of a malicious receiver, Property 2 ensures that the simulator cannot learn any information about the choice bit c before the adversary queries the random oracle on \(\mathsf {p}_c\), which only happens after the simulator has sent its last message. The simulator could possibly program the random oracle answer given \(\mathsf {p}_c\) so that the result is \(\mathsf {m}_c\) (received from the OT functionality), but this is not possible in this setting. In order to circumvent these challenges, we augment the simple protocol described before with mechanisms that allow the simulator to extract the choice bit c and messages \(\mathsf {m}_0\) and \(\mathsf {m}_1\) without resorting to programming the random oracle.

In order to obtain security against a malicious receiver, we use a challenge-response mechanism that follows the approach of Doerner et al. [21]. Basically, before carrying out the actual transfer, \(\mathsf {Alice} \) queries \((\mathsf {pk} _0,\mathsf {p}_0,\mathsf {r} _0)\) and \((\mathsf {pk} _1,\mathsf {p}_1,\mathsf {r} _1)\) to the random oracle \(\mathcal {F}_{\mathrm {gRO}3} \) (note that this oracle is different from \(\mathcal {F}_{\mathrm {gRO}2} \)) obtaining \(\mathsf {p}_0',\mathsf {p}_1'\), and then queries \(\mathsf {p}_0',\mathsf {p}_1'\) to the random oracle \(\mathcal {F}_{\mathrm {gRO}3} \) obtaining \(\mathsf {p}_0'',\mathsf {p}_1''\). \(\mathsf {Alice} \) fixes the challenge as \(\mathsf {ch}\leftarrow \mathsf {p}_0'' \oplus \mathsf {p}_1''\) and sends \(\mathsf {ch}\) to \(\mathsf {Bob} \). \(\mathsf {Bob} \) queries \(\mathcal {F}_{\mathrm {gRO}3} \) with \((\mathsf {pk} _c,\mathsf {p}_c,\mathsf {r} _c)\), which is possible because \(\mathsf {PKE} \) has witness-recovering decryption according to Property 5, obtaining \(\mathsf {p}_c'\) and then with \(\mathsf {p}_c'\) obtaining \(\mathsf {p}_c''\). \(\mathsf {Bob} \) returns \(\mathsf {p}_c'' \oplus (c \cdot \mathsf {ch})\) to \(\mathsf {Alice} \), who checks if the returned value is equal to \(\mathsf {p}_0''\). \(\mathsf {Alice} \) then sends \(\mathsf {p}_0',\mathsf {p}_1'\) to \(\mathsf {Bob} \), who checks if these values are compatible with the values he previously computed and \(\mathsf {ch}\). After receiving a valid response from \(\mathsf {Bob} \), \(\mathsf {Alice} \) proceeds with the transfer. A crucial aspect of this mechanism is that in order to obtain \(\mathsf {p}_c''\), \(\mathsf {Bob} \) is forced to first issue a query associated to its choice bit c to the random oracle, allowing for extraction. In the proof, the simulator can extract c solely by observing the adversary’s queries after it receives the challenge, allowing it to obtain \(\mathsf {m}_c\) from the OT functionality and prepare the last message to the adversary accordingly. This mechanism allows selective failure attacks, but the resulting scheme fulfills the requirements to be used as base OTs in the OT extension scheme of Keller et al. [34] (see Sect. 2).

Instead of querying \(\mathcal {F}_{\mathrm {gRO}2} \) with \(\mathsf {p}_0,\mathsf {p}_1\), we query it with \((\mathsf {pk} _0,\mathsf {p}_0,\mathsf {r} _0)\) and \((\mathsf {pk} _1,\mathsf {p}_1,\mathsf {r} _1)\) to obtain \(\widetilde{\mathsf {p}_0},\widetilde{\mathsf {p}_1}\). These queries of the form \((\mathsf {pk} _i,\mathsf {p}_i,\mathsf {r} _i)\) to \(\mathcal {F}_{\mathrm {gRO}2} \) and \(\mathcal {F}_{\mathrm {gRO}3} \) allow the simulator to extract both of the corrupt sender’s messages solely by observing the queries to the random oracle. In the simulation, the simulator reconstructs ciphertexts \(\hat{\mathsf {ct}}_j=\mathsf {Enc} (\mathsf {pk} _i,\hat{\mathsf {p}}_j,\hat{\mathsf {r}}_j)\) from all random oracle queries of the form \((\mathsf {pk} _i,\hat{\mathsf {p}}_j,\hat{\mathsf {r}}_j)\), looking for a ciphertext \(\hat{\mathsf {ct}}_{j}\) that matches ciphertext \(\mathsf {ct} _i\) (for \(i \in \{0,1\}\)) in the adversary’s message. Having found these ciphertexts the simulator can proceed to recover each message \(\mathsf {m}_i\). An adversary could try to confuse the simulator by making two different queries to the random oracle that pass the tests above. However, this is not possible due to Properties 3 and 4.

Protocol \(\pi _{\textsf {SFOT}} \) is described in Fig. 3 and its security if formally stated in Theorem 1, which we prove in the full version [17]. A CDH based instantiation is described in the full version [17].

Theorem 1

Let \(\mathsf {PKE} \) be a public-key encryption scheme that satisfies Properties 1, 2, 3, 4 and 5. When instantiated with \(\mathsf {PKE} \), Protocol \(\pi _{\textsf {SFOT}} \) UC-realizes functionality \(\mathcal {F}_{\mathrm {SFOT}}^\lambda \) with security against static malicious adversaries in the global random oracle model.

4 Realizing \(\mathcal {F}_{\mathrm {OT}}^{\lambda ,1}\) Directly

Our previous generic protocol can be modified to directly realize the standard 1-out-of-2 OT functionality \(\mathcal {F}_{\mathrm {OT}}^{\lambda ,1} \) without any selective failure issues, instead of first realizing \(\mathcal {F}_{\mathrm {SFOT}}^\lambda \) and then employing the OT extension of Keller et al. to realize \(\mathcal {F}_{\mathrm {OT}}^{\lambda ,\ell } \). However, we will rely directly on the specific CDH based PKE constructed in the full version [17] instead of a generic PKE with Properties 1, 2, 3, 4 and 5. This is necessary since the simulator will now need to extract messages encrypted under this PKE that it cannot extract by simply observing queries to the random oracle instances used in the protocol but that can be extracted by observing queries to the random oracle instance used by this specific PKE construction.

In order to eliminate the potential selective failure from our first protocol, we need to provide \(\mathsf {Bob} \) with a proof that \(\mathsf {Alice} \) has used exactly the values \(\mathsf {p}_0, \mathsf {p}_1\) contained in ciphertexts \(\mathsf {ct} _0,\mathsf {ct} _1\) to generate challenge \(\mathsf {ch}\). The main idea is to use two instances of our original protocol that are run using the same public keys \(\mathsf {pk} _0,\mathsf {pk} _1\) (encoding the same choice bit). One of them is used to execute the challenge-response mechanism and the other is used to execute a random OT, which can be later derandomized. In our previous protocol, \(\mathsf {Alice} \) only reveals the outputs of \(\mathcal {F}_{\mathrm {gRO}3} \) upon being queried with \((\mathsf {sid},\mathsf {pk} _i,\mathsf {p}_i,\mathsf {r} _i)\), which only allows \(\mathsf {Bob} \) to check that these were the values used in the challenge with probability \(\frac{1}{2}\). In order to prove that those values were indeed used, we will leverage the committing property (Property  3) of the underlying cryptosystem and have \(\mathsf {Alice} \) reveal \(\mathsf {p}_0,\mathsf {p}_1,\mathsf {r} _0,\mathsf {r} _1\) to \(\mathsf {Bob} \) upon getting a valid response to the challenge. Using these values, \(\mathsf {Bob} \) can recompute the challenge (checking that it matches \(\mathsf {ch}\) received from \(\mathsf {Alice} \)) and check that \(\mathsf {ct} _{i} {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathsf {Enc} (\mathsf {pk} _i,\mathsf {p}_i;\mathsf {r} _i)\), for \(i=\{0,1\}\). If those checks fail, the receiver aborts but, if they succeed, it is assured by the committing property that those values were used in computing \(\mathsf {ct} _0\), \(\mathsf {ct} _1\) and \(\mathsf {ch}\) (meaning the choice bit was not leaked). Having both \(\mathsf {p}_0, \mathsf {p}_1\) revealed to \(\mathsf {Bob} \), we will need to have \(\mathsf {Alice} \) generate new \(\hat{\mathsf {p}}_0, \hat{\mathsf {p}}_1\) and corresponding \(\hat{\mathsf {ct}}_0,\hat{\mathsf {ct}}_1\) to complete the OT as in our first protocol. However, notice that this protocol still leaks \(\mathsf {Bob} \)’s choice bit to an adversary who mounts a successful selective failure attack, even though the attack is detected and the protocol is aborted. In order to deal with this, \(\mathsf {Bob} \) uses a random choice bit to execute a random OT that is derandomized after \(\mathsf {Bob} \) is certain no selective failure attack occurred.

Fig. 4.
figure 4

Protocol \(\pi _{\textsf {OT}} \)

Full size image

The simulator for a corrupt \(\mathsf {Alice} \) does not have to extract the “guess” bit of the adversary, just acting as an honest \(\mathsf {Bob} \) and extracting the messages \(\mathsf {m}_0,\mathsf {m}_1\) using the same techniques as the simulator in \(\pi _{\textsf {SFOT}} \). However, it will need to extract messages \(\hat{\mathsf {p}}_0, \hat{\mathsf {p}}_1\) from the ciphertexts \(\hat{\mathsf {ct}}_0,\hat{\mathsf {ct}}_1\) by observing queries to the random oracle used in the CDH based PKE described in the full version [17]. The simulator for a corrupt \(\mathsf {Bob} \) uses the same techniques as the simulator in \(\pi _{\textsf {SFOT}} \) to extract the choice bit. The difference is that the ciphertexts \(\mathsf {ct} _0',\mathsf {ct} _1'\) obtained from the challenger in the game of Property 1 are given to the adversary as \(\mathsf {ct} _{c},\hat{\mathsf {ct}}_{1-c}\) in the reduction showing that an adversary that obtains \(\mathsf {m}_{1-c}\) when interacting with this simulator breaks Property 1.

Protocol \(\pi _{\textsf {OT}} \) is described in Fig. 4 and its security if formally stated in Theorem 2, which we prove in the full version [17]. The CDH based PKE instantiation is described in the full version [17].

Theorem 2

Under the CDH assumption, Protocol \(\pi _{\textsf {OT}} \) UC-realizes functionality \(\mathcal {F}_{\mathrm {OT}}^{\lambda ,1} \) with security against static malicious adversaries in the global random oracle model.