Oblivious Transfer (OT)

A protocol that efficiently extends a small number of base OTs (typically 128) into a large number of OTs using only fast symmetric-key cryptography. The base OTs are executed using expensive public-key operations, while the extension phase relies on lightweight primitives like AES hashing. This reduces the computational cost of millions of OTs from prohibitive to practical, making it a critical optimization for MPC-based inference and garbled circuit protocols.

A two-party protocol introduced by Andrew Yao that enables secure function evaluation. The function is represented as a boolean circuit. One party (the garbler) encrypts the circuit, and the other (the evaluator) evaluates it using Oblivious Transfer to obtain the keys corresponding to their private input bits. The evaluator learns the output without learning any intermediate values, and the garbler remains oblivious to the evaluator's input. The Free-XOR optimization eliminates cryptographic costs for XOR gates.

A protocol allowing a client to retrieve an item from a database held by a server without the server learning which item was accessed. PIR is a close relative of OT, but with a critical distinction: in PIR, the client learns only the requested record and nothing about others, while the server's privacy is not a concern. Computational PIR relies on cryptographic hardness assumptions, while Information-Theoretic PIR requires multiple non-colluding servers. Modern PIR schemes leverage homomorphic encryption for single-server efficiency.

A generalization of the standard 1-out-of-2 OT where the sender holds n messages and the receiver selects exactly one without the sender learning the index. This primitive is essential for PIR and secure database lookup. Efficient constructions often reduce 1-out-of-n OT to multiple instances of 1-out-of-2 OT using symmetric-key expansion techniques. The communication complexity can be made sublinear in n using rate-1 OT and batch codes.

A variant where the sender's two messages are not independent but satisfy a specific correlation, such as being a random string and that string XORed with a secret. This structure reduces communication overhead because the sender only needs to transmit a single correction value. Correlated OT is a key building block in OT extension protocols, particularly the IKNP protocol, and is heavily used in secure computation for private equality tests and conditional branching.

An OT variant where the sender's messages are randomly generated during the protocol rather than being chosen in advance. The sender learns both random messages, and the receiver learns only their selected one. Random OT is the workhorse of the OT extension preprocessing phase: the parties generate many random OTs offline, then convert them to standard OTs for specific messages using a simple XOR correction in the online phase. This decoupling dramatically improves online efficiency.