Paper 2019/273

Compressing Vector OLE

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

Abstract

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.CCS 2018
DOI
10.1145/3243734.3243868
Keywords
Secure computationcorrelation generatorsFSSOLELPNNIZK
Contact author(s)
eboyle @ alum mit edu
geoffroy couteau @ kit edu
gilboan @ bgu ac il
yuvali @ cs technion ac il
History
2019-03-12: received
Short URL
https://ia.cr/2019/273
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/273,
      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{https://eprint.iacr.org/2019/273}},
      url = {https://eprint.iacr.org/2019/273}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.