OT Extension

The protocol begins with a small number (e.g., 128 or 256) of Base OTs. These initial transfers use slow, computationally intensive public-key cryptography (like Diffie-Hellman). Their sole purpose is to seed the extension process. Once executed, these base OTs are never used again for the bulk transfer, isolating the heavy computation to a one-time setup cost.

The foundational IKNP protocol (Ishai, Kilian, Nissim, Petrank) transforms the base OTs into an arbitrary number of extended OTs. It leverages a Random Oracle Model and a matrix transposition trick. The sender creates two large matrices, and the receiver uses the base OTs to selectively learn one of two strings for each column, enabling the efficient generation of millions of correlated, random OT instances using only fast hash function evaluations.

Modern extensions like Ferret OT push performance further by using Vector Oblivious Linear Evaluation (VOLE) and quasi-cyclic codes. This approach generates extremely long, correlated OT strings at blazing speeds. The security relies on a Correlation-Robust Hash function, a weaker and more efficient assumption than a full random oracle, allowing for concrete, high-speed implementations that form the backbone of state-of-the-art PSI protocols like KKRT.

A primary goal of OT Extension is to minimize data transfer. By shifting the workload to local symmetric computations, the protocol drastically reduces communication complexity. The bulk of the extended OTs are generated non-interactively from a shared, short seed. This makes the technique ideal for bandwidth-constrained environments and is a key reason why modern PSI protocols can process sets of millions of items in seconds over a standard network.

OT Extension protocols can be instantiated with different security guarantees. The base OTs and the extension logic can be adapted for semi-honest security (parties follow the protocol but are curious) or hardened for malicious security (parties may arbitrarily deviate). Achieving malicious security requires additional checks, like consistency verification of the matrix, but the core extension paradigm remains the same, offering a tunable trade-off between performance and adversarial robustness.

OT Extension is not a standalone application; it is the universal engine powering modern secure computation. Protocols like KKRT for semi-honest PSI and its maliciously secure variants are built directly on top of extended OTs. It enables efficient Oblivious Pseudorandom Functions (OPRFs) and Garbled Circuits, making it the single most important optimization for converting theoretical cryptographic privacy into practical, real-world collaborative analytics.