A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
1-out-of-2 oblivious transfer (OT) is a protocol where a sender has two messages (m0, m1) and a receiver has a choice bit b. After the protocol, the receiver learns m_b but nothing about m_{1-b}, while the sender learns nothing about b. OT is a complete primitive for secure computation: any function can be securely computed using only OT as a building block (Kilian 1988). OT requires computational assumptions — it is impossible information-theoretically. OT extension protocols amortize expensive public-key operations, enabling millions of OTs from a small number of base OTs using only symmetric cryptography.
Oblivious transfer (OT) is deceptively simple to state but extraordinarily powerful. In 1-out-of-2 OT, a sender holds two messages m0 and m1, and a receiver holds a bit b. After the protocol, the receiver learns m_b (the message they chose) and nothing about m_{1-b}, while the sender learns nothing about which message was chosen. Both parties are simultaneously ignorant: the sender doesn't know which message was taken, and the receiver doesn't know the message they didn't take. This dual ignorance is what makes OT non-trivial and impossible to achieve without computational assumptions.
OT can be constructed from various public-key assumptions. In the Naor-Pinkas protocol (based on CDH), the receiver sends a pair of group elements, one of which encodes their choice bit. The sender encrypts each message under the corresponding element. The algebraic structure ensures the receiver can decrypt only one message, while the sender cannot determine which one. More recent constructions use lattice-based assumptions, providing post-quantum security. What cannot be done is build OT from one-way functions alone (Impagliazzo-Rudich) — OT genuinely requires public-key-level assumptions, placing it strictly above symmetric primitives in the cryptographic hierarchy.
The theoretical significance of OT lies in its completeness for secure computation (Kilian, 1988): any efficiently computable function can be securely evaluated using OT as the only cryptographic building block. Combined with Yao's garbled circuits, this means two parties can securely compute any function as follows — the garbler constructs the garbled circuit, and the evaluator obtains their input labels via OT (one OT per input bit), ensuring the garbler doesn't learn which labels were selected. For multi-party computation, OT extensions and related techniques generalize this approach. OT is therefore the minimal cryptographic assumption for general secure computation without honest majority.
In practice, OT's main bottleneck is that each invocation requires public-key operations. OT extension (Ishai, Kilian, Nissim, Orlandi, 2003) is the breakthrough optimization: starting from a small number of "base" OTs (128 or 256, performed with expensive public-key crypto), the protocol generates any number of additional OTs using only symmetric operations (hash evaluations). The technique involves exchanging a matrix of bits and using the base OT keys to correlate rows, enabling the amortized cost per OT to drop to a few hash evaluations. Combined with the preprocessing model (precompute random OTs offline, convert to chosen-message OTs online using XOR), this makes practical MPC with millions of OTs feasible. Modern MPC systems can execute billions of OTs per second, transforming OT from a theoretical primitive into a practical workhorse.