Compressing Vector OLE
Open Access
- 15 October 2018
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 896-912
Abstract
Oblivious linear-function evaluation (OLE) is a secure two-party protocol allowing a receiver to learn any 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 any 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 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.Keywords
Funding Information
- AFOSR Award (FA9550-17-1-0069)
- ERC Grant (742754, 724307)
- ISF grant (1861/16, 1709/14, 1638/15)
- grant from the Ministry of Science and Technology Israel and Department of Science and Technology Government of India
- GU Cyber Center grant
This publication has 51 references indexed in Scilit:
- Quadratic Span Programs and Succinct NIZKs without PCPs2013
- Zero-Knowledge Proofs from Secure Multiparty ComputationSIAM Journal on Computing, 2009
- Combinatorial batch codesAdvances in Mathematics of Communications, 2009
- Oblivious Polynomial EvaluationSIAM Journal on Computing, 2006
- Sufficient Conditions for Collision-Resistant Hashing2005
- Share Conversion, Pseudorandom Secret-Sharing and Applications to Secure Computation2005
- Keyword Search and Oblivious Pseudorandom Functions2005
- On interactive proofs with a laconic provercomputational complexity, 2002
- Linear-time encodable and decodable error-correcting codesIEEE Transactions on Information Theory, 1996
- The use of information sets in decoding cyclic codesIEEE Transactions on Information Theory, 1962