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

ole_protocol.svg

The ideal functionality \(\mathcal{F}_{\mathsf{OLE}}\) over a finite field \(\mathbb{F}\) operates between a Sender \(S\) and a Receiver \(R\):

  1. Sender inputs \((a, b) \in \mathbb{F} \times \mathbb{F}\).
  2. Receiver inputs \(x \in \mathbb{F}\).
  3. The functionality computes \(y = ax + b\).
  4. 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

ole_ot_relationship.svg

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}\).

ole_hierarchy.svg

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.

References

[1] Moni Naor, and Benny Pinkas. 1999. “Oblivious transfer and polynomial evaluation.” https://dl.acm.org/doi/10.1145/301250.301312.
[2] Satrajit Ghosh, and Tobias Nilges. 2017. “An Algebraic Approach to Maliciously Secure Private Set Intersection.” https://eprint.iacr.org/2017/1064.
[3] Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl. 2019. “Efficient Pseudorandom Correlation Generators: Silent OT Extension and More.” https://link.springer.com/10.1007/978-3-030-26954-8_16.
[4] Chenkai Weng, Kang Yang, Jonathan Katz, and Xiao Wang. 2021. “Wolverine: Fast, Scalable, and Communication-Efficient Zero-Knowledge Proofs for Boolean and Arithmetic Circuits.” https://ieeexplore.ieee.org/document/9519498/.
[5] Carsten Baum, Alex J Malozemoff, Marc B Rosen, and Peter Scholl. “Mac’n’Cheese: Zero-Knowledge Proofs for Boolean and Arithmetic Circuits with Nested Disjunctions.”
[6] Carsten Baum, Lennart Braun, Cyprien Delpech de Saint Guilhem, Michael Klooß, Emmanuela Orsini, Lawrence Roy, and Peter Scholl. 2023. “Publicly Verifiable Zero-Knowledge and Post-Quantum Signatures From VOLE-in-the-Head.” https://eprint.iacr.org/2023/996.