Oblivious Transfer (OT)

The core security guarantee for the sender. After the protocol executes, the sender learns absolutely nothing about which message the receiver selected. This is not merely computational hiding; it is information-theoretic in many constructions. The sender's view is statistically independent of the receiver's choice index, meaning even an adversary with unbounded computational power cannot determine which secret was accessed. This property is critical for protocols like Private Set Intersection (PSI) where the sender's database contents must remain private beyond the single intersection element.

The core security guarantee for the receiver. The receiver's choice input must remain computationally hidden from the sender. Specifically, the sender cannot distinguish between a receiver selecting message m0 versus message m1 with any probability significantly greater than random chance. This is typically achieved through public-key cryptography where the receiver crafts two public keys—one real and one fake—but the sender cannot tell which is which. This property relies on hard problems like the Decisional Diffie-Hellman assumption.

The most fundamental and widely implemented variant. The sender inputs two messages (m0, m1), and the receiver inputs a single choice bit b (0 or 1). The receiver learns mb but learns nothing about m1-b, while the sender learns nothing about b. This primitive is the atomic unit of secure computation; any multi-party computation (MPC) circuit can be theoretically constructed from a sufficient number of 1-out-of-2 OT executions combined with garbled circuits.

A generalization where the sender holds a database of n messages, and the receiver retrieves a single record at index i without revealing i to the sender. A naive approach using repeated 1-out-of-2 OT would require O(n) complexity, but optimized protocols using OT Extension can reduce the computational overhead dramatically. This variant is the direct cryptographic backbone of Private Information Retrieval (PIR) systems, allowing users to query databases without exposing their search terms.

A critical performance optimization that allows a small number of 'base' OTs (typically 128) to be extended into millions of effective OTs using only fast symmetric-key operations (like AES hashes). This technique, introduced by Ishai et al., breaks the reliance on expensive public-key crypto for every single transfer. By generating a matrix of correlated randomness, OT Extension makes OT practical for high-volume secure computation tasks, such as evaluating deep neural networks in MPC frameworks.

A variant where the sender does not input specific messages; instead, the protocol generates random messages and the receiver randomly learns one of them. This produces a pool of correlated randomness that can be stored offline. Later, in an online phase, the sender can simply XOR their actual messages with the pre-computed random values to convert the Random OT into a Standard OT with minimal latency. This separation of phases is vital for low-latency encrypted inference.

The fundamental variant where a sender holds two messages (m₀, m₁) and the receiver chooses one bit. The receiver learns only their chosen message, and the sender remains oblivious to the choice.

• Mechanism: Relies on trapdoor permutations or Diffie-Hellman assumptions
• Use case: Core subroutine in Yao's Garbled Circuits for secure two-party computation
• Efficiency: Can be extended from a small number of base OTs using OT extension protocols

A generalized protocol where the receiver selects k messages from a set of n held by the sender. The sender learns nothing about which subset was chosen.

• Privacy: Receiver's selection remains computationally hidden
• Application: Private information retrieval (PIR) and privacy-preserving database queries
• Trade-off: Higher communication overhead than 1-out-of-2, but more expressive selection

A cryptographic technique that amplifies a small number of expensive public-key base OTs into a large number of OTs using only fast symmetric-key operations.

• IKNP Protocol: The foundational OT extension construction by Ishai, Kilian, Nissim, and Petrank
• Performance: Reduces computational cost from O(n) public-key ops to O(n) hash evaluations
• Impact: Makes OT practical for large-scale secure computation with millions of gates

A specialized variant where the sender's messages are not independent but satisfy a specific correlation, typically m₁ = m₀ ⊕ Δ for a fixed global secret Δ.

• Efficiency: Reduces communication since only one message needs to be sent explicitly
• Application: Critical for efficient Garbled Circuit evaluation and silent OT generation
• Silent OT: A recent advancement enabling OT with near-zero communication using learning parity with noise (LPN) assumptions

A non-interactive variant where both sender's messages are uniformly random strings generated during the protocol, rather than chosen by the sender in advance.

• Preprocessing: Can be executed offline before inputs are known
• Conversion: Random OTs are converted to standard OTs at online time with minimal communication
• Advantage: Decouples expensive OT generation from the input-dependent phase of secure computation

A secure two-party computation protocol that relies on OT as its sole cryptographic primitive for input transfer. The circuit evaluator uses OT to obliviously receive wire labels corresponding to their private input bits.

• Yao's Construction: The foundational protocol enabling any polynomial-time function to be computed securely
• OT Role: Prevents the evaluator from learning both wire labels, which would break security
• Optimizations: Point-and-permute, free-XOR, and half-gates techniques reduce circuit size