Oblivious Transfer (OT)

The sender remains oblivious to the receiver's choice. After the protocol concludes, the sender has no information about which of the transmitted messages was accessed. This is achieved through cryptographic blinding, where the receiver's selection is hidden within a set of indistinguishable protocol messages. The formal guarantee is that the sender's view when the receiver chooses message i is computationally indistinguishable from its view when the receiver chooses message j, for any i and j. This property is essential for applications like private information retrieval and privacy-preserving advertising, where the querier's intent must remain hidden.

The receiver learns only the content of the single message they selected and gains zero knowledge about the other messages. This is enforced by the protocol's cryptographic construction, typically using public-key techniques where the receiver can only decrypt one of several ciphertexts. For example, in a 1-out-of-2 OT, the receiver generates keys that allow decryption of only one of two encrypted messages. Any attempt to extract information about the unselected message would require solving a computationally hard problem, such as the Computational Diffie-Hellman problem. This property is critical for secure database lookup and contract signing.

While the classic formulation is 1-out-of-2 OT, the primitive generalizes to 1-out-of-n OT, where the sender holds n messages and the receiver selects one index. This is not merely a theoretical extension; it is a practical building block. A 1-out-of-n OT can be constructed from log(n) instances of 1-out-of-2 OT, preserving efficiency. This generalization allows a client to privately query a single record from a database of arbitrary size without revealing which record was accessed, forming the basis for Private Information Retrieval (PIR) and secure table lookups in garbled circuit evaluations.

A naive implementation of OT requires expensive public-key cryptography for every single transfer, making it impractical for large-scale secure computation. OT Extension protocols, such as the IKNP protocol, solve this bottleneck. They enable the execution of a small number of 'base' OTs (e.g., 128) using public-key crypto, and then bootstrap these into millions of OTs using only fast symmetric-key operations like hash functions. This reduces the amortized cost per OT by orders of magnitude, transforming OT from a theoretical curiosity into a practical, high-throughput primitive for protocols like Private Set Intersection (PSI) and secure multi-party computation.

OT comes in two functional variants. In Random OT (ROT), the sender's messages are randomly generated by the protocol itself, and both parties learn their respective outputs. This is extremely efficient and serves as a setup phase. In Chosen-Message OT, the sender provides specific, pre-determined input messages. A standard optimization is to perform a batch of cheap ROTs first, and then use the random outputs as one-time pads to encrypt and transmit the actual chosen messages in a second, minimal communication round. This decoupling of the setup from the input-dependent phase is a key technique in high-performance PSI protocols like KKRT.

Oblivious Transfer is complete for secure two-party computation. This means that any arbitrary function that can be jointly computed by two parties on their private inputs can be realized using an OT protocol as the sole cryptographic building block, combined with other non-cryptographic operations. In practice, this is achieved by using OT to evaluate Garbled Circuits, where each AND gate in the circuit requires a 1-out-of-2 OT. This theoretical result establishes OT as the most fundamental asymmetric primitive in cryptography, from which all other secure computation protocols can be derived.