Oblivious Linear Evaluation
Summary
Oblivious Linear Evaluation (OLE) is a two-party cryptographic primitive that computes a linear function over a finite field \(\mathbb{F}\) while keeping each party's inputs private. It is the natural arithmetic generalization of oblivious transfer (OT) from \(\mathbb{F}_2\) to arbitrary fields.
Formal Definition
The ideal functionality \(\mathcal{F}_{\mathsf{OLE}}\) over a finite field \(\mathbb{F}\) operates between a Sender \(S\) and a Receiver \(R\):
- Sender inputs \((a, b) \in \mathbb{F} \times \mathbb{F}\).
- Receiver inputs \(x \in \mathbb{F}\).
- The functionality computes \(y = ax + b\).
- Output \(y\) to the Receiver. Output nothing to the Sender.
Security requires that the Sender learns nothing about \(x\), and the Receiver learns nothing about \(a\) or \(b\) individually beyond what is revealed by \(y\).
Relationship to Oblivious Transfer
OT is OLE over \(\mathbb{F}_2\). A 1-out-of-2 OT with sender messages \(m_0, m_1 \in \mathbb{F}_2\) and receiver choice bit \(c\) can be expressed as OLE by setting \(a = m_0 \oplus m_1\), \(b = m_0\), and \(x = c\). Note that over \(\mathbb{F}_2\), addition and XOR are the same operation (\(\oplus = +\)), so \(a = m_0 + m_1\) and \(y = ax + b\) is computed mod 2. Then:
- If \(c = 0\): \(y = a \cdot 0 + b = m_0\).
- If \(c = 1\): \(y = (m_0 + m_1) + m_0 = m_1\).
Just as OT is complete for secure computation of boolean circuits, OLE is complete for secure computation of arithmetic circuits over \(\mathbb{F}\).
Vector OLE (VOLE)
Vector OLE generalizes OLE to vectors. The sender holds \((a, \mathbf{b})\) where \(a \in \mathbb{F}\) and \(\mathbf{b} \in \mathbb{F}^n\), and the receiver holds \(\mathbf{x} \in \mathbb{F}^n\). The receiver obtains \(\mathbf{y} = a \cdot \mathbf{x} + \mathbf{b}\) (component-wise). VOLE correlations are cheaper to generate and have become the practical workhorse for OLE-based protocols.
Random/Correlated OLE
In many modern protocols, the variant used is a random OLE where the functionality samples \((a, b, x)\) at random and distributes the correlation: the sender gets \((a, b)\), the receiver gets \((x, y = ax + b)\). This is the "OLE correlation" used in pseudorandom correlation generator (PCG) constructions.
Notes
- The "oblivious X evaluation" naming pattern refers to two-party protocols where one party holds a function \(f\) of type X (e.g., linear, polynomial, PRF) and the other party holds an input \(x\). The second party learns \(f(x)\) without learning \(f\), and the first party learns nothing about \(x\).
- OLE is the degree-1 special case of Oblivious Polynomial Evaluation (OPE), studied by Naor and Pinkas [1].
- The explicit treatment of OLE as a standalone primitive over arbitrary fields was formalized by Ghosh, Nielsen, and Nilges [2].
- The Boyle-Couteau-Gilboa-Ishai-Kohl-Scholl line of work on pseudorandom correlation generators (PCGs) [3] was transformative for practical VOLE: it enables "silent" generation of VOLE correlations from short correlated seeds with sublinear communication, based on variants of the Learning Parity with Noise (LPN) assumption.
- VOLE-based zero-knowledge proof systems (e.g., Wolverine [4], Mac'n'Cheese [5]) have emerged as a major application area.
- The "VOLE-in-the-head" paradigm [6] extends VOLE to post-quantum signature schemes, showing the reach of OLE/VOLE beyond MPC.