Fact-checked by Grok 2 weeks ago

Oblivious transfer

Oblivious transfer (OT) is a two-party cryptographic protocol in which a sender transmits one of two secret messages to a receiver such that the receiver obtains exactly the chosen message without learning anything about the other, while the sender remains completely unaware of the receiver's choice. The primitive was first introduced in 1981 by Michael Rabin as a probabilistic "all-or-nothing" variant, where a sender transmits a single message that the receiver obtains with probability 1/2, and the sender learns nothing about whether the transfer succeeded. This original formulation addressed challenges in secret exchange without trusted intermediaries or simultaneous message delivery. A more versatile deterministic version, known as 1-out-of-2 OT, was later developed in 1985 by Shimon Even, Oded Goldreich, and Abraham Lempel, enabling the sender to offer two distinct messages from which the receiver selects one obliviously. Their protocol relies on public-key cryptosystems and forms the basis for subsequent extensions, such as 1-out-of-n OT, where the receiver chooses one message from n options without revealing the index. Oblivious transfer has become a cornerstone of modern due to its role in enabling (MPC). In particular, OT is computationally complete for secure two-party computation, meaning that any probabilistic polynomial-time functionality can be securely evaluated using OT as the sole primitive, with efficient constructions demonstrated in the 2000s. This completeness underpins applications in privacy-preserving , secure auctions, and , where parties compute joint functions on private inputs without exposing them. Variants of OT, including quantum and post-quantum secure protocols, continue to be researched to enhance efficiency and resist emerging threats like .

Core Concepts

Definition

Oblivious transfer (OT) is a two-party between a S and a R. In its general form, the sender inputs a set of messages (such as a single message M in the basic case or multiple messages in variants), the receiver inputs a choice bit or index indicating which message to receive, and upon completion, the receiver obtains only the chosen message while the sender remains oblivious to the receiver's choice, and the receiver gains no information about the non-chosen messages. The foundational variant, known as Rabin's oblivious transfer and introduced by in , involves the sender inputting a single message M, with the receiver obtaining M with probability 1/2 or receiving nothing at all, while the sender learns nothing about whether the message was received. This basic protocol achieves perfect obliviousness for the sender and , meaning the receiver cannot gain the message with probability greater than 1/2 even with unbounded computational power. The core security goals of oblivious transfer are sender obliviousness, which ensures the sender acquires no information about the receiver's , and receiver privacy, which guarantees the receiver learns only the selected message and nothing else about the sender's inputs. Informally, oblivious transfer resembles sending a locked via : in Rabin's basic form, the receiver has a 50% chance of holding the key to access the contents, but the sender remains unaware if it was unlocked; generalized variants extend this to allow the receiver selective access to specific items within the without revealing the selection to the sender.

Security Model

Oblivious transfer (OT) protocols are analyzed under two primary adversarial models: the semi-honest model, also known as honest-but-curious, where parties adhere to the specifications but may attempt to extract additional from the communication transcripts, and the malicious model, where parties can arbitrarily deviate from the to compromise or correctness. In the semi-honest setting, ensures that the protocol's execution remains indistinguishable from an ideal execution even if one party passively observes the transcripts. For malicious adversaries, stronger guarantees are required, including robustness against deviations, often achieved via cryptographic compilers that incorporate zero-knowledge proofs to enforce honest behavior. The core security notions for OT are receiver privacy and sender obliviousness. Receiver privacy requires that the sender's view of the protocol execution is computationally or statistically of the receiver's choice of message index, ensuring the sender learns nothing about which message was selected. Sender obliviousness mandates that the receiver's view reveals only the chosen message, with no information about the other messages, formalized as indistinguishability between the real view and an ideal view where the unchosen messages are replaced by random strings. These notions are defined such that an OT is secure if it satisfies both properties simultaneously in the respective adversarial model. OT security can be information-theoretic, providing unconditional protection without computational assumptions, or computational, relying on hardness assumptions such as the Decisional Diffie-Hellman (DDH) problem or Quadratic Residuosity (QR). Information-theoretic security achieves perfect sender obliviousness in the semi-honest model, but full OT against malicious adversaries requires computational assumptions, as unconditional OT is impossible in the plain model. Computational security, as in Bellare-Micali protocols based on DDH, ensures negligible advantage for polynomial-time adversaries in distinguishing the protocol outputs. Modern security analyses employ the ideal/real-world paradigm, where a protocol is secure if no efficient adversary can distinguish executions in the real world (actual protocol run with possibly corrupted parties) from the ideal world (interaction via a trusted party that correctly delivers the chosen message without revealing choices). This paradigm underpins universal composability (UC) security for OT, ensuring the protocol remains secure when composed with arbitrary other protocols. UC-OT implies UC-security for other primitives like secure multiparty computation, with reductions showing that OT can be realized UC-secure from DDH or lossy encryption assumptions. Common attacks in the malicious model include the receiver attempting to learn both messages by deviating in or decryption steps, or the sender forcing the receiver to accept an unintended message by sending correlated inputs. These are countered using zero-knowledge proofs to verify correct key sampling and message encryption, as in compilers transforming semi-honest OT to malicious-secure versions while preserving efficiency.

Role in Cryptography

Oblivious transfer (OT) serves as a foundational building block in , particularly due to its completeness property for secure two-party computation (2PC). Specifically, OT is computationally complete for 2PC in the presence of public-key encryption, enabling the construction of protocols that securely evaluate any polynomial-time function on private inputs without revealing additional information. This completeness stems from the ability to use OT to simulate the transfer of encrypted inputs and intermediate values in computational tasks, such as Yao's garbled circuits, where OT facilitates the secure revelation of input keys to the evaluator without disclosing the choices. In the context of multiparty computation (MPC), OT enables efficient by leveraging OT extension techniques, which amplify a small number of base OT instances into many correlated OTs using pseudorandom generators and symmetric-key operations, thereby reducing overall communication costs. For instance, the IKNP extension allows generating millions of OT instances from just a handful of base OTs, making OT-based MPC practical for large-scale computations with communication overhead dominated by symmetric rather than expensive public-key operations. This approach has been instrumental in deploying MPC for applications like private database queries and secure aggregation. OT also relates to other , notably in the construction of s where OT is used to generate and transfer wire keys for the evaluator's inputs, contrasting with direct circuit evaluation by ensuring input privacy without additional assumptions. Regarding efficiency in 2PC, the overhead from OT typically involves one OT instance per input bit in basic garbled circuit protocols, though malicious security enhancements like cut-and-choose can increase this to scale with the circuit's input size; OT extensions mitigate this by keeping base OT costs constant while extending to the required volume. In , OT constructions based on lattice assumptions resist quantum attacks, unlike some classical primitives reliant on factoring or discrete logarithms, providing a pathway for quantum-secure 2PC and MPC. For example, OT protocols derived from the Learning With Rounding (LWR) problem or collision-resistant chameleon hashes achieve universal composability in the , ensuring robustness against quantum adversaries while maintaining efficiency comparable to classical counterparts.

Classical Protocols

Rabin's Protocol

Rabin's oblivious transfer protocol, introduced in 1981, provides a probabilistic mechanism for a sender S to transfer a message M (such as a bit string) to a receiver R, where R obtains M with probability exactly 1/2 and receives nothing (denoted ⊥) otherwise, while S remains unaware of the outcome. The original formulation relies on the hardness of computing square roots a composite N (equivalent to factoring N, underlying the assumption). This primitive models a "noisy channel" where information is lost randomly, forming a foundational building block for more complex oblivious transfer variants. The protocol proceeds in the following steps. S selects two large primes p and q such that N = p q is a large composite, chooses a public exponent e with gcd(e, φ(N)) = 1 where φ(N) = (p-1)(q-1), and computes the private exponent d ≡ e^{-1} \pmod{φ(N)}. S encrypts the message as c = M^e \pmod{N} and sends the public information (N, e, c) to R. The receiver R chooses a random x ∈ {0, \dots, N-1} and computes y = x^2 \pmod{N}, sending y to S. Upon receiving y, S uses the of N to compute the four square roots of y modulo N and selects one of them uniformly at random, say z, sending z to R. Finally, R receives z and computes gcd(|x - z|, N). With probability 1/2, z ≡ x \pmod{p} and z ≡ -x \pmod{q} (or vice versa), so the gcd reveals a nontrivial (p or q), allowing R to factor N, compute φ(N) and d, and decrypt c^d \pmod{N} to recover M. Otherwise (if z ≡ ±x \pmod{N}), the gcd is 1 or N, R cannot factor, and obtains ⊥. Security in Rabin's protocol achieves perfect sender obliviousness: S's view consists of a random quadratic residue y and a random square root z, identically distributed regardless of R's success, as R's x is unknown to S and computationally indistinguishable under the factoring assumption. Receiver privacy holds information-theoretically: even an unbounded S cannot learn whether R recovered M, since the success probability is statistically fixed at 1/2 and independent of S's actions. The protocol assumes semi-honest participants and security in the computational model against polynomial-time adversaries. Despite its elegance, the protocol has notable limitations. Its probabilistic nature means R receives nothing with probability 1/2, requiring multiple executions for reliable transfer (though this increases communication). It mandates a public-key setup, including secure generation of large moduli, which is computationally intensive. The protocol operates in O(1) communication rounds but incurs high overhead due to operations and computations N, and early formulations faced potential cheating vulnerabilities (later addressed in extensions). These traits make it unsuitable for direct practical use without or fixes.

1-2 Oblivious Transfer

In 1-out-of-2 oblivious transfer, also known as 1-2 OT, the sender S holds two input messages M_0 and M_1, while the receiver R holds a choice bit \sigma \in \{0,1\}. Upon completion of the protocol, R obtains M_\sigma with certainty but learns no information about M_{1-\sigma}, and S learns nothing about \sigma. This protocol provides a deterministic extension to Rabin's probabilistic oblivious transfer, enabling R to select a specific message without uncertainty. One standard construction for 1-2 OT builds on Rabin's oblivious transfer through a reduction that ensures determinism. The reduction runs multiple instances of Rabin's OT in parallel to generate shared random bits with high probability, then uses XOR operations to conditionally disclose one of the messages based on R's choice bit \sigma. Specifically, S and R execute Ks instances of Rabin's OT (for security parameter s and constant K) on random bits r_i, where R receives each r_i with probability $1/2. R partitions the indices into two balanced subsets U and V of size s/2, randomly permutes their order to hide the choice, and sends the permuted subsets to S. S computes the XORs m_0 = \oplus_{i \in X} r_i and m_1 = \oplus_{i \in Y} r_i (where \{X, Y\} is the permuted pair), then sends M_0 \oplus m_0 and M_1 \oplus m_1 (or randomized versions thereof). R recovers M_\sigma using knowledge of the bits in the chosen subset, with the binomial distribution ensuring near-certainty of success (probability $1 - 2^{-s}) via the law of large numbers. This achieves statistical security independent of the underlying Rabin's OT implementation, provided it satisfies the basic obliviousness properties. The security of the protocol is computational, relying on the hardness of the underlying Rabin's OT (e.g., factoring). The protocol requires multiple rounds due to the parallel executions and incurs O(s) communication complexity, where s is the security parameter.

1-out-of-n and k-out-of-n Variants

In 1-out-of-n oblivious transfer (1-out-of-n OT), the sender holds n input messages M1, ..., Mn, while the receiver specifies a choice index i ∈ {1, ..., n}; at the end of the protocol, the receiver obtains only Mi, and the sender remains oblivious to i, with the receiver learning nothing about the other messages. A naive construction achieves this by executing n−1 parallel instances of 1-out-of-2 OT, where for each j ≠ i, the sender inputs (Mj, a random string) and the receiver inputs 0 to receive the random string, while for the chosen i, the receiver inputs 1 to obtain Mi; this ensures the sender cannot distinguish the receiver's choices. More efficient protocols reduce the number of base 1-out-of-2 OTs to O(log n) using a binary tree structure: the sender and receiver perform 1-out-of-2 OTs at each level of a balanced binary tree of depth log n, where the receiver's choice bits guide the path to the desired message, and the sender inputs masked versions of messages or random pads along branches. For k-out-of-n OT, the receiver specifies a subset S ⊆ {1, ..., n} of size exactly k and receives only the messages {Mj | j ∈ S}, while learning nothing about the remaining messages and the sender learning nothing about S. Constructions for k-out-of-n OT often employ combinatorial techniques, such as representing the receiver's choice subset via shares in a Shamir secret-sharing scheme of degree k−1, where the sender distributes encrypted shares corresponding to each message, and the receiver reconstructs only the shares for the chosen subset using k 1-out-of-n OTs or equivalent subprotocols; this leverages the access structure to enforce oblivious selection without revealing the full choice. Both variants benefit from OT extension techniques to amortize the cost of base OTs, particularly the IKNP framework, which uses a (PRG) seeded by a small number of base 1-out-of-2 OTs to generate many correlated OTs, enabling efficient 1-out-of-n realizations by encoding choices into PRG outputs and extending to tree-like or vector selections. For k-out-of-n, extensions adapt this by correlating multiple choice vectors, often achieving active security with low overhead via compiler-based transformations on passive-secure bases. Security for these protocols is computational, assuming the underlying 1-out-of-2 OT is secure under standard assumptions like the decisional Diffie-Hellman problem, and obliviousness is preserved under sequential composition theorems for multiparty computation primitives. Naive communication complexity for 1-out-of-n OT is O(n log κ), where κ is the security parameter, due to sending masked messages across n options, but extensions reduce this to O(log n + poly(κ)) for the base phase, with overall costs amortized over many instances. For k-out-of-n OT, complexity is similarly O(n log κ) naively but drops to O(k log n + poly(κ)) using extensions, as only k paths or shares need reconstruction. Recent 2020s developments, such as post-quantum adaptations and hardware-accelerated extensions, further optimize communication for large n and k, achieving sublinear overhead in applications like while maintaining active security.

Advanced and Generalized Forms

Generalized Oblivious Transfer

Generalized oblivious transfer (GOT) extends the basic oblivious transfer to support arbitrary access structures beyond simple selections, allowing the receiver's retrieval to be governed by a P. In a GOT , the sender provides a database of items, while the submits a private query; the then obtains exactly the items satisfying P (e.g., any monotone access structure) without revealing the query, and the sender learns nothing about which items were accessed. Constructions for GOT typically leverage advanced primitives such as functional encryption or attribute-based encryption (ABE) to enforce the predicate. For instance, predicate oblivious transfer (Pred-OT), where P belongs to a function class like inner-product predicates, can be realized using predicate encryption schemes that match attributes to policies without decryption of unauthorized data. Representative examples include string oblivious transfer, in which the receiver retrieves database strings matching a private pattern without exposing the pattern to the sender. Functional oblivious transfer () provides another extension, enabling the receiver to compute a (e.g., or ) on selected items rather than receiving the items directly, which supports applications like privacy-preserving k-nearest neighbors classification in . These protocols achieve security in the universal composability (UC) framework under assumptions such as bilinear pairings or the learning-with-errors (LWE) problem, distinguishing them from standard OT by handling expressive predicates while preserving obliviousness. Post-2010 developments have focused on malicious security and post-quantum resilience, including UC-secure adaptive oblivious transfer with access control based on lattice assumptions, supporting policies expressed as branching programs of polynomial length.

Quantum Oblivious Transfer

Quantum oblivious transfer (QOT) adapts the classical to the by employing quantum states, typically qubits, to and transmit messages between distrustful parties. In a standard 1-out-of-2 QOT , the sender prepares two quantum states corresponding to distinct messages and sends them to the receiver, who selects one bit to determine the basis for decoding the chosen message while obtaining no about the other; simultaneously, the sender learns nothing about the receiver's choice. This leverages and to potentially achieve stronger guarantees than classical methods, such as resistance to certain attacks. Despite these advantages, secure QOT—providing perfect without computational assumptions—is impossible, as proven by no-go theorems linked to the unattainability of secure quantum bit (QBC). The seminal BBCS protocol (Bennett, , Crépeau, and Skubiszewska, 1992) demonstrated a of QOT to QBC using BB84 quantum states, where the sender encodes bits in polarized photons and the receiver measures accordingly; however, subsequent results by Mayers (1997) and Lo and Chau (1997) established that perfect QBC is impossible due to the quantum , allowing the committer to cheat by deferring measurement choices post-, thereby rendering perfect QOT unattainable from quantum resources alone. These impossibility results hold even under general attacks using classical or , as extended by D'Ariano et al. (2007). Practical QOT constructions thus rely on hybrid approaches or relaxed security models. One common method combines quantum key distribution (QKD), such as , with classical OT protocols: parties first generate a key via QKD, which is then used to securely perform classical OT, providing computational security against quantum adversaries while ensuring post-quantum key exchange. Alternatively, weak QOT variants achieve for honest parties but allow bounded cheating probabilities (e.g., 0.75 for the ), as in the by Chailloux et al. (2011), which uses quantum states to correlate random bits without perfect obliviousness. The original BB84-based QOT by BBCS (1992) employed faint laser pulses for photon transmission but was flawed due to the underlying QBC vulnerability, though it inspired hybrid fixes like adding classical commitments (Damgård et al., 2009). More advanced protocols pursue device-independent QOT, secure against arbitrary device imperfections under no-signaling constraints. The first such , by Kaniewski and Wehner (2016), operates in the noisy-storage model, where adversaries have limited , using self-testing of entangled states to certify security without trusting hardware. Recent developments include measurement-device-independent constructions leveraging MDI-QKD for enhanced practicality; for instance, a 2023 device-independent OT under bounded quantum storage combines self-testing with computational assumptions to achieve security even against receiver quantum storage limitations. These approaches exploit the quantum to prevent message duplication and offer potential post-quantum security, making QOT viable for applications like in quantum networks.

History and Applications

Origins

Oblivious transfer was first introduced by in his 1981 technical report, motivated by the need for secure protocols enabling parties to exchange secrets fairly without revealing unnecessary information, such as in scenarios where one party accesses a database without disclosing the query. Rabin's protocol, often called Rabin's oblivious transfer or 1/2-OT, allows a sender to transmit a secret to a receiver with probability 1/2, providing a foundation for probabilistic security in cryptographic exchanges. This invention relied on assumptions, specifically the security of one-way functions like those underlying , and emphasized an efficient protocol design to minimize communication rounds. In the early 1980s, the concept saw initial extensions that built upon Rabin's work to address more deterministic forms. A key development came in 1985 from Shimon Even, , and Abraham Lempel, who constructed a 1-out-of-2 oblivious transfer protocol from Rabin's basic version, enabling the receiver to choose exactly one of two secrets while keeping the choice hidden from the sender. Concurrently, David Chaum's 1981 introduction of mix-nets for untraceable electronic mail provided an indirect foundation by exploring anonymity-preserving protocols that later intersected with oblivious transfer in privacy applications. By the mid-1980s, oblivious transfer's role in broader cryptographic constructions began to solidify. In 1989, Mihir Bellare and Silvio Micali demonstrated non-interactive oblivious transfer. In 1988, Joe Kilian showed that oblivious transfer is complete for secure two-party computation, meaning that any probabilistic polynomial-time functionality can be securely evaluated using OT as the sole primitive under computational assumptions. The 1990s marked a shift toward computational security models, with protocols increasingly based on the Diffie-Hellman assumption to enable efficient implementations without relying solely on factoring-based primitives like . This evolution highlighted OT's foundational status in modern while addressing practical limitations in early designs.

Modern Applications

Oblivious transfer () serves as a foundational in practical (MPC) frameworks, enabling privacy-preserving computations across distributed parties. Libraries such as MP-SPDZ incorporate OT extensions to support efficient and garbled circuits, facilitating applications like privacy-preserving where parties jointly train models without revealing individual data inputs. Similarly, the EMP-toolkit implements OT protocols for two-party computations, including maliciously secure variants that underpin scenarios by allowing selective data sharing without exposing full datasets. In , OT underpins (PIR) systems, where users query databases without revealing their interests to the . For instance, single-database PIR protocols can be constructed from OT, ensuring that the remains oblivious to the retrieved item while the user obtains only the desired data. OT also enables anonymous credentials and related mechanisms, allowing users to prove attributes without disclosing underlying information, as seen in credential systems that leverage OT for selective disclosure. Efficiency advancements have made OT viable for large-scale deployments through extension protocols that amplify a small number of base OTs into many instances using symmetric-key operations. The 2015 IKNP-based actively secure OT extension reduces overhead to near-optimal levels, requiring only O(1) base OTs for millions of extensions while maintaining security in the model. Hardware accelerations further optimize performance; for example, FPGA-based architectures like POTA pipeline silent OT computations, achieving up to 10x speedup in communication-intensive MPC tasks on cloud platforms. Despite these gains, OT protocols face challenges from bandwidth overhead in large-scale settings, where extensions can still consume significant network resources for high-volume correlations. Mitigations include silent OT variants, such as the 2021 Silver protocol, which generate OT instances non-interactively after an initial setup, reducing rounds and communication by leveraging vector oblivious linear evaluation (VOLE) from decisional Diffie-Hellman assumptions. Post-2020 benchmarks demonstrate that silent OT extensions achieve throughputs exceeding 1 million OTs per second on modern hardware, enabling scalable privacy-preserving AI in resource-constrained environments. In blockchain contexts, supports zero- succinct non-interactive arguments of (zk-SNARKs) by providing correlated for proof generation in privacy-focused transactions, as integrated in MPC-based proof systems for verifiable computations.