Paper 2019/273

Compressing Vector OLE

Elette Boyle, Geoffroy Couteau, Niv Gilboa, and Yuval Ishai


Oblivious linear-function evaluation (OLE) is a secure two-party protocol allowing a receiver to learn a secret linear combination of a pair of field elements held by a sender. OLE serves as a common building block for secure computation of arithmetic circuits, analogously to the role of oblivious transfer (OT) for boolean circuits. A useful extension of OLE is vector OLE (VOLE), allowing the receiver to learn a linear combination of two vectors held by the sender. In several applications of OLE, one can replace a large number of instances of OLE by a smaller number of long instances of VOLE. This motivates the goal of amortizing the cost of generating long instances of VOLE. We suggest a new approach for fast generation of pseudo-random instances of VOLE via a deterministic local expansion of a pair of short correlated seeds and no interaction. This provides the first example of compressing a non-trivial and cryptographically useful correlation with good concrete efficiency. Our VOLE generators can be used to enhance the efficiency of a host of cryptographic applications. These include secure arithmetic computation and non-interactive zero-knowledge proofs with reusable preprocessing. Our VOLE generators are based on a novel combination of function secret sharing (FSS) for multi-point functions and linear codes in which decoding is intractable. Their security can be based on variants of the learning parity with noise (LPN) assumption over large fields that resist known attacks. We provide several constructions that offer tradeoffs between different efficiency measures and the underlying intractability assumptions.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. CCS 2018
Secure computationcorrelation generatorsFSSOLELPNNIZK
Contact author(s)
eboyle @ alum mit edu
geoffroy couteau @ kit edu
gilboan @ bgu ac il
yuvali @ cs technion ac il
2019-03-12: received
Short URL
Creative Commons Attribution


      author = {Elette Boyle and Geoffroy Couteau and Niv Gilboa and Yuval Ishai},
      title = {Compressing Vector {OLE}},
      howpublished = {Cryptology ePrint Archive, Paper 2019/273},
      year = {2019},
      doi = {10.1145/3243734.3243868},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.