Yuval Ishai, Technion and UCLA

Abstract

Oblivious linear-function evaluation (OLE) is a secure two-party protocol allowing a receiver to learn a linear combination of two field elements held by a sender. Vector OLE (VOLE) extends OLE by allowing the receiver to learn a linear combination of two vectors held by the sender. OLE and VOLE serve as useful building blocks in secure computation of arithmetic circuits, analogous to the roles of oblivious transfer (OT) and string OT for Boolean circuits.

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 are based on a combination of function secret sharing (FSS) for multi-point functions and linear codes in which decoding is intractable.

We present several applications of VOLE generators, including efficient secure computation protocols with "silent" preprocessing that only requires a low-communication setup phase and no further interaction.

Joint work with Elette Boyle, Geoffroy Couteau, and Niv Gilboa.  

Video