Vector OLE (VOLE)

VOLE is a two-party protocol where a sender inputs a scalar value x and a receiver inputs a scalar value y. The protocol outputs a random vector A and a scalar B to the sender, and a vector C to the receiver, such that the linear correlation C = A * x + B * y holds. Crucially, the sender learns nothing about y, and the receiver learns nothing about x or B, making it a fundamental building block for secure computation.

VOLE can be instantiated in two primary modes:

• Random VOLE: The inputs x and y are randomly generated by the protocol itself. This is the fastest form and is used to generate large batches of correlated randomness in a setup phase.
• Chosen-Input VOLE: The parties provide their own private inputs x and y. This is the form directly consumed by applications like PSI, and it can be efficiently converted from random VOLE using a technique called oblivious transfer extension.

VOLE is the cryptographic engine that powers the world's fastest PSI protocols, such as those based on the KKRT and Ferret frameworks. By using VOLE to generate a massive number of oblivious pseudorandom function (OPRF) instances in bulk, these protocols can evaluate set membership with extremely low communication overhead. This replaces the slower, per-element public-key operations of older Diffie-Hellman-based PSI with fast, batched symmetric-key computations.

VOLE is not a standalone protocol but is itself constructed from more basic primitives. The most efficient constructions use Oblivious Transfer (OT) extension, specifically the IKNP protocol and its modern variants. A small number of base OTs are used as a seed to generate a virtually unlimited number of VOLE correlations using only fast symmetric-key operations, making the amortized cost per correlation negligible.

The Ferret OT protocol is a state-of-the-art method for generating VOLE correlations at blazing speed. It leverages quasi-cyclic low-density parity-check (LDPC) codes to achieve an extremely low communication overhead, approaching the theoretical minimum. This construction is a key reason why modern PSI protocols can process millions of items in seconds, even on consumer-grade hardware.

The security of practical VOLE-based protocols is typically proven in the Random Oracle Model (ROM). Here, a hash function is treated as a truly random function. This allows for highly efficient constructions where the correlation-robustness of the hash function guarantees that the output vectors A and C are indistinguishable from random to the respective parties, preventing any leakage of the secret inputs x and y.