Oblivious Transfer (OT)

The defining property of OT. After the protocol executes, the sender has zero information about which secret the receiver chose. This is not merely a promise; it is a mathematically provable guarantee based on computational hardness assumptions.

• Mechanism: Achieved by masking all sender messages with cryptographic keys, only one of which the receiver can decrypt.
• Contrast: Unlike a simple encrypted download where a server logs access, OT leaves no digital trace of the selection.
• Requirement: The sender must hold multiple inputs (typically 2 in the base case, denoted as 1-out-of-2 OT) for the choice to be meaningful.

The receiver learns exactly one piece of information and nothing about the other messages. This is enforced by the protocol's cryptographic construction, not by trust.

• 1-out-of-2 OT: The receiver chooses bit b and learns message M_b, but gains no information about M_{1-b}.
• 1-out-of-n OT: Extends the concept to n messages, where the receiver selects a single index i and learns only M_i.
• Security Guarantee: Even a malicious sender with unbounded computational power cannot force the receiver to learn more than one message (information-theoretic security for the receiver in some constructions).

OT is cryptographically complete for secure multi-party computation (SMPC). Any arbitrary function that can be computed jointly by multiple parties with private inputs can be constructed solely from OT protocols.

• Garbled Circuits: OT is the essential mechanism for the evaluator to obliviously receive the wire labels corresponding to their private input without the garbler learning that input.
• AND Gate Evaluation: A 1-out-of-2 OT directly implements a secure AND gate, which is a universal gate for boolean circuits.
• Efficiency Driver: Because OT is the primary bottleneck in many SMPC protocols, massive engineering effort focuses on OT extension techniques to generate millions of OT instances from a small number of base OTs.

A performance breakthrough that allows a small number of computationally expensive base OTs (using public-key cryptography) to be extended into a virtually unlimited number of OTs using only fast symmetric-key operations.

• IKNP Protocol: The foundational OT extension protocol by Ishai, Kilian, Nissim, and Petrank (2003) that dramatically reduced the computational cost.
• Impact: Reduces the public-key overhead from linear in the number of OTs to a constant, making OT practical for large-scale SMPC applications like private set intersection on million-element datasets.
• Correlated OT: A variant where the sender's messages are not independent but satisfy a linear correlation, further optimizing specific SMPC sub-protocols.

OT enables competing financial institutions to collaboratively detect fraud without exposing their proprietary transaction data or customer lists to one another.

• Private Set Intersection (PSI): Banks can use OT-based PSI to discover accounts appearing on multiple institutions' fraud watchlists without revealing any non-intersecting accounts.
• Private Database Query: An investigator can query a consortium's shared fraud database for a specific entity's risk score without the database learning which entity was queried.
• Regulatory Compliance: Satisfies data localization and privacy regulations (like GDPR) by ensuring raw data never leaves the originating institution's control during collaborative analytics.

A highly efficient variant where the sender's messages are not chosen by the sender but are generated as random strings by the protocol itself. The sender learns the random pair, and the receiver learns one of them based on their choice bit.

• Pre-computation Phase: Random OTs can be generated in bulk during an offline phase, independent of the actual data to be computed on.
• Online Phase: When the actual inputs are known, the random strings are used as one-time pads to mask the real messages, requiring only trivial XOR operations.
• Benefit: Shifts heavy cryptographic work to an offline, non-latency-critical phase, enabling extremely fast online secure computation.