Vector Oblivious Linear Evaluation (VOLE)

Vector Oblivious Linear Evaluation (VOLE) is a two-party cryptographic protocol where a sender holds a vector a and a receiver holds a scalar x. The protocol allows the receiver to learn a linear combination b = a * x + c, where c is a correction vector known only to the sender, while ensuring the receiver learns nothing else about a and the sender learns nothing about x. This oblivious transfer-like property is fundamental for secure computation.

VOLE serves as a highly efficient building block for Secure Multi-Party Computation (MPC) and Zero-Knowledge Proofs (ZKPs), particularly in the post-quantum era. It is a key component in:

• VOLE-in-the-Head paradigms for efficient ZK proof systems like Libra and Banquet.
• Information-Theoretic MACs for authenticating secret-shared data in MPC.
• Replacing slower oblivious transfer extensions, dramatically improving the prover time and communication overhead in privacy-preserving protocols.

The protocol's power comes from pre-establishing a VOLE correlation between parties. A trusted setup or a slow base Oblivious Transfer (OT) generates correlated randomness: the sender gets (u, v) and the receiver gets (w) such that w = Δ * u + v, where Δ is the receiver's global secret. Later, for an input x, the receiver can compute b = x * u + w, which equals a * x + v, where a = u and c = v. This pre-computation enables fast, constant-round online phases.

VOLE-based protocols offer significant performance benefits over traditional methods:

• Post-Quantum Security: Based on linear correlations over finite fields, resistant to quantum attacks.
• Efficiency: Requires only cheap symmetric-key operations (hash functions, PRGs) after setup, unlike public-key crypto in some ZKPs.
• Low Communication: Minimal data needs to be exchanged during the online computation phase.
• Scalability: Enables practical ZK proofs for large programs (e.g., machine learning inference) with prover times potentially orders of magnitude faster than SNARKs.

VOLE's efficiency makes it suitable for privacy applications requiring high throughput:

• Private Machine Learning: Proving correct inference from a private model on private data.
• Verifiable Decentralized Finance (DeFi): Generating succinct proofs of correct transaction batch processing.
• Secure Audits: Allowing an entity to prove compliance (e.g., solvency, fair voting) without revealing underlying sensitive data.
• Private Set Intersection (PSI): Enabling two parties to find common elements in their datasets without revealing the full sets.

VOLE exists within an ecosystem of related cryptographic primitives:

• Oblivious Transfer (OT): A simpler but less efficient primitive; VOLE is often constructed from a base OT.
• Function Secret Sharing (FSS): Shares similarities in enabling distributed point functions.
• Homomorphic Secret Sharing (HSS): Allows computation on secret-shared data; VOLE can be viewed as a linear HSS.
• STARKs and SNARKs: Alternative ZKP systems with different trust and performance trade-offs.

VOLE provides information-theoretic security for one party, meaning its security is based on information theory rather than computational hardness assumptions. The protocol ensures that a malicious party cannot learn anything about the other party's secret input vector beyond what can be inferred from the output. This is achieved through the use of correlated randomness generated via a silent OT extension.

VOLE protocols typically operate in a two-party, semi-honest (passive) adversarial model, where parties follow the protocol but may try to learn extra information. Some constructions are being adapted for the malicious (active) model. Security often relies on a correlation robustness assumption or a random oracle for the initial seed generation phase, after which the protocol becomes information-theoretically secure.

VOLE's primary security benefit is its efficiency. Compared to standard Oblivious Transfer (OT), VOLE allows for the generation of a large amount of usable correlated randomness with minimal communication after a small setup phase. Key metrics:

• Sublinear communication: After setup, generating millions of correlated pairs requires sending only a few kilobytes.
• Constant rounds: The online evaluation phase often requires only one round of communication. This makes it practical for high-throughput MPC and ZK applications.

VOLE is not used in isolation but as a component within larger protocols. Its security is integral to:

• Zero-Knowledge Proofs: Used in VOLE-in-the-head and Libra-style protocols (e.g., QuickSilver) to achieve post-quantum security and linear prover complexity.
• Secure Multi-Party Computation (MPC): Enables efficient preprocessing for protocols like SPDZ, generating Beaver triples for secure multiplication.
• Function Secret Sharing (FSS): VOLE can be used to efficiently generate the keys for FSS schemes.

Practical security requires careful implementation to avoid side-channel and protocol-specific attacks:

• Seed Generation: The initial Base OT or LPN-based setup must be secure, as a compromise here breaks the entire system.
• Consistency Checks: Protocols for the malicious model add checks to ensure parties use consistent inputs, increasing communication overhead.
• Field Choice: Security and efficiency depend on the underlying finite field (e.g., GF(2) for binary circuits, large prime fields for arithmetic). Using a small field can make linear algebra attacks easier.

VOLE is a powerful generalization of Oblivious Transfer. While a 1-out-of-2 OT gives one party a choice between two secrets, VOLE gives two parties shares of a linear correlation (e.g., w = Δ * a + b). Silent OT extension protocols use VOLE to generate millions of OTs from a few base OTs, making large-scale OT feasible. This relationship is key to understanding VOLE's role in replacing heavy public-key crypto with symmetric operations for bulk data.

VOLE-based protocols enable efficient Private Set Intersection (PSI), where two parties can discover common elements in their datasets without revealing the full sets. This is implemented using correlated OTs derived from VOLE to perform private equality tests. Applications include private contact discovery, fraud detection across institutions, and secure data marketplaces on blockchain.

VOLE can be bootstrapped using a Trusted Execution Environment (TEE) like Intel SGX to establish the initial seed correlation in a trusted setup phase. The TEE generates and distributes the first VOLE correlation to participants, after which the protocol proceeds in a trustless manner. This hybrid model balances strong security assumptions with subsequent decentralized, efficient operation.