Ferret OT

Ferret OT leverages Vector Oblivious Linear Evaluation (VOLE) as its core primitive, replacing traditional OT extension matrix operations with a more efficient algebraic structure. This shift dramatically reduces communication overhead by generating long vectors of correlated randomness from a small, constant-size seed. The protocol uses quasi-cyclic codes to instantiate the VOLE, enabling linear-time encoding and decoding operations that scale efficiently with batch size.

The protocol employs a specialized correlation-robust hash function to compress the VOLE outputs into standard oblivious transfer messages. This cryptographic construction ensures that the hash outputs remain pseudorandom even when correlated inputs are hashed under the same key, a critical property for maintaining security in the random oracle model. Ferret OT's hashing approach eliminates the need for expensive public-key operations during the extension phase, relying entirely on fast symmetric-key primitives.

Ferret OT instantiates its VOLE using quasi-cyclic low-density parity-check (QC-LDPC) codes, which provide a highly efficient linear encoding structure. These codes are defined by circulant matrices that enable fast polynomial multiplication operations. The quasi-cyclic structure allows the protocol to achieve:

Ferret OT achieves malicious security—protecting against adversaries that arbitrarily deviate from the protocol—with minimal performance penalty compared to semi-honest variants. The protocol incorporates efficient consistency checks that verify the correctness of the VOLE correlations without revealing the underlying values. This is accomplished through batch verification techniques that amortize the cost of checking across millions of OTs, making it practical for real-world deployments where strong adversarial guarantees are required.

Ferret OT supports a silent OT extension mode where the receiver can non-interactively derive its OT outputs after a one-time setup phase. This is particularly valuable for unbalanced PSI and contact discovery applications where a client with a small set queries a server with a massive database. The silent mode eliminates the need for the server to remain online during the extension phase, reducing latency and enabling pre-computation of OT instances before the receiver's inputs are known.

A class of linear error-correcting codes used in Ferret OT to implement correlation-robust hashing with minimal computational overhead. These codes provide structured algebraic properties that enable fast encoding.

• Exploit cyclic shifts to reduce the complexity of matrix-vector multiplication
• Enable the protocol to compress and hash OT outputs efficiently
• Contribute to Ferret's asymptotically optimal communication complexity

The foundational OT extension protocol by Ishai, Kilian, Nissim, and Petrank that established the matrix-transposition paradigm for extending oblivious transfers. Ferret OT builds upon and improves this classical construction.

• Introduced the technique of encoding sender messages into a matrix and transposing it
• Achieves security in the random oracle model
• Serves as the baseline against which Ferret OT's performance gains are measured

A cryptographic assumption and technique used in Ferret OT to securely compress and randomize OT outputs. A hash function is correlation-robust if it remains pseudorandom even when applied to inputs with known linear correlations.

• Essential for preventing information leakage during the OT extension process
• Ferret OT leverages quasi-cyclic codes to implement this hashing with minimal circuit depth
• Allows the protocol to achieve malicious security without expensive consistency checks