We introduce a new approach to actively secure two-party computation based on so-called oblivious linear function evaluation (OLE), a natural generalisation of oblivious transfer (OT) and a special case of the notion of oblivious polynomial evaluation introduced by Naor and Pinkas at STOC 1999. OLE works over a finite field F. In an OLE the sender inputs two field elements a ƒ F and b ƒ F, and the receiver inputs a field element x ∈ F and learns only ƒx) = ax + b. Our protocol can evaluate an arithmetic circuit over a finite field F given black-box access to OLE for F. The protocol is unconditionally secure and consumes only a constant number of OLEs per multiplication gate. An OLE over a field F of size O(2κ) be implemented with communication O(κ). This gives a protocol with communication complexity O(C κ) for large enough fields, where C is an arithmetic circuit computing the desired function.
We introduce a new approach to actively secure two-party computation based on so-called oblivious linear function evaluation (OLE), a natural generalisation of oblivious transfer (OT) and a special case of the notion of oblivious polynomial evaluation introduced by Naor and Pinkas at STOC 1999. OLE works over a finite field F. In an OLE the sender inputs two field elements a ƒ F and b ƒ F, and the receiver inputs a field element x ∈ F and learns only ƒx) = ax + b. Our protocol can evaluate an arithmetic circuit over a finite field F given black-box access to OLE for F. The protocol is unconditionally secure and consumes only a constant number of OLEs per multiplication gate. An OLE over a field F of size O(2κ) be implemented with communication O(κ). This gives a protocol with communication complexity O(C κ) for large enough fields, where C is an arithmetic circuit computing the desired function.
We introduce a new approach to actively secure two-party computation based on so-called oblivious linear function evaluation (OLE), a natural generalisation of oblivious transfer (OT) and a special case of the notion of oblivious polynomial evaluation introduced by Naor and Pinkas at STOC 1999. OLE works over a finite field F. In an OLE the sender inputs two field elements a ƒ F and b ƒ F, and the receiver inputs a field element x ∈ F and learns only ƒx) = ax + b. Our protocol can evaluate an arithmetic circuit over a finite field F given black-box access to OLE for F. The protocol is unconditionally secure and consumes only a constant number of OLEs per multiplication gate. An OLE over a field F of size O(2κ) be implemented with communication O(κ). This gives a protocol with communication complexity O(C κ) for large enough fields, where C is an arithmetic circuit computing the desired function. This asymptotically matches the best previous protocols, but our protocol at the same time obtains significantly smaller constants hidden by the big-O notation, yielding a highly practical protocol. Conceptually our techniques lift the techniques for basing practical actively secure 2PC of Boolean circuits on OT introduced under the name TinyOT by Nielsen, Nordholt, Orlandi and Burra at Crypto 2012 to the arithmetic setting. In doing so we develop several novel techniques for generating various flavours of OLE and combining these. We believe that the efficiency of our protocols, both in asymptotic and practical terms, establishes OLE and its variants as an important foundation for efficient actively secure 2PC.
We study the problem of secure two-party computation of arithmetic circuits in the presence of active ("malicious") parties. This problem is motivated by privacy-preserving numerical computations, such as ones arising in the context of machine learning training and classification, as well as in threshold cryptographic schemes. In this work, we design, optimize, and implement anactively secure protocol for secure two-party arithmetic computation. A distinctive feature of our protocol is that it can make a fully modular black-box use of any passively secure implementation of oblivious linear function evaluation (OLE). OLE is a commonly used primitive for secure arithmetic computation, analogously to the role of oblivious transfer in secure computation for Boolean circuits. For typical (large but not-too-narrow) circuits, our protocol requires roughly 4 invocations of passively secure OLE per multiplication gate. This significantly improves over the recent TinyOLE protocol (Döttling et al., ACM CCS 2017), which requires 22 invocations of actively secure OLE in general, or 44 invocations of a specific code-based passively secure OLE. Our protocol follows the high level approach of the IPS compiler (Ishai et al., CRYPTO 2008, TCC 2009), optimizing it in several ways. In particular, we adapt optimization ideas that were used in the context of the practical zero-knowledge argument system Ligero (Ames et al., ACM CCS 2017) to the more general setting of secure computation, and explore the possibility of boosting efficiency by employing a "leaky" passively secure OLE protocol. The latter is motivated by recent (passively secure) lattice-based OLE implementations in which allowing such leakage enables better efficiency. We showcase the performance of our protocol by applying its implementation to several useful instances of secure arithmetic computation. On "wide" circuits, such as ones computing a fixed function on many different inputs, our protocol is 5x faster and transmits 4x less data than the state-of-the-art Overdrive (Keller et al., Eurocrypt 2018). Our benchmarks include a general passive-to-active OLE compiler, authenticated generation of "Beaver triples", and a system for securely outsourcing neural network classification. The latter is the first actively secure implementation of its kind, strengthening the passive security provided by recent related works (Mohassel and Zhang, IEEE S&P 2017; Juvekar et al., USENIX 2018).
We study the problem of secure two-party computation of arithmetic circuits in the presence of active (malicious) parties. This problem is motivated by privacy-preserving numerical computations, such as ones arising in the context of machine learning training and classification, as well as in threshold cryptographic schemes. In this work, we design, optimize, and implement anactively secure protocol for secure two-party arithmetic computation. A distinctive feature of our protocol is that it can make a fully modular black-box use of any passively secure implementation of oblivious linear function evaluation (OLE). OLE is a commonly used primitive for secure arithmetic computation, analogously to the role of oblivious transfer in secure computation for Boolean circuits. For typical (large but not-too-narrow) circuits, our protocol requires roughly 4 invocations of passively secure OLE per multiplication gate. This significantly improves over the recent TinyOLE protocol (Dottling et al., ACM CCS 2017), which requires 22 invocations of actively secure OLE in general, or 44 invocations of a specific code-based passively secure OLE. Our protocol follows the high level approach of the IPS compiler (Ishai et al., CRYPTO 2008, TCC 2009), optimizing it in several ways. In particular, we adapt optimization ideas that were used in the context of the practical zero-knowledge argument system Ligero (Ames et al., ACM CCS 2017) to the more general setting of secure computation, and explore the possibility of boosting efficiency by employing a leaky passively secure OLE protocol. The latter is motivated by recent (passively secure) lattice-based OLE implementations in which allowing such leakage enables better efficiency. We showcase the performance of our protocol by applying its implementation to several useful instances of secure arithmetic computation. On wide circuits, such as ones computing a fixed function on many different inputs, our protocol is 5x faster and transmits 4x less data than the state-of-the-art Overdrive (Keller et al., Eurocrypt 2018). Our benchmarks include a general passive-to-active OLE compiler, authenticated generation of Beaver triples, and a system for securely outsourcing neural network classification. The latter is the first actively secure implementation of its kind, strengthening the passive security provided by recent related works (Mohassel and Zhang, IEEE SP Juvekar et al., USENIX 2018).
An oblivious linear function evaluation protocol, or OLE, is a two-party protocol for the function f ( x ) = a x + b, where a sender inputs the field elements a, b, and a receiver inputs x and learns f ( x ). OLE can be used to build secret-shared multiplication, and is an essential component of many secure computation applications including general-purpose multi-party computation, private set intersection and more. In this work, we present several efficient OLE protocols from the ring learning with errors (RLWE) assumption. Technically, we build two new passively secure protocols, which build upon recent advances in homomorphic secret sharing from (R)LWE (Boyle et al. in: EUROCRYPT 2019, Part II (2019) 3–33 Springer), with optimizations tailored to the setting of OLE. We upgrade these to active security using efficient amortized zero-knowledge techniques for lattice relations (Baum et al. in: CRYPTO 2018, Part II (2018) 669–699 Springer), and design new variants of zero-knowledge arguments that are necessary for some of our constructions. Our protocols offer several advantages over existing constructions. Firstly, they have the lowest communication complexity amongst previous, practical protocols from RLWE and other assumptions; secondly, they are conceptually very simple, and have just one round of interaction for the case of OLE where b is randomly chosen. We demonstrate this with an implementation of one of our passively secure protocols, which can perform more than 1 million OLEs per second over the ring Z m , for a 120-bit modulus m, on standard hardware.
We study the complexity of securely evaluating arithmetic circuits over finite rings. This question is motivated by natural secure computation tasks. Focusing mainly on the case of two-party protocols with security against malicious parties, our main goals are to: (1) only make black-box calls to the ring operations and standard cryptographic primitives, and (2) minimize the number of such black-box calls as well as the communication overhead. We present several solutions which differ in their efficiency, generality, and underlying intractability assumptions. These include: • An unconditionally secure protocol in the OT-hybrid model which makes a black-box use of an arbitrary ring R, but where the number of ring operations grows linearly with (an upper bound on) log |R|. • Computationally secure protocols in the OT-hybrid model which make a black-box use of an underlying ring, and in which the number of ring operations does not grow with the ring size. The protocols rely on variants of previous intractability assumptions related to linear codes. In the most efficient instance of these protocols, applied to a suitable class of fields, the (amortized) communication cost is a constant number of field elements per multiplication gate and the computational cost is dominated by O(log k) field operations per gate, where k is a security parameter. These results extend a previous approach of Naor and Pinkas for secure polynomial evaluation (SIAM J. Comput., 35(5), 2006). • A protocol for the rings Zm = Z/mZ which only makes a black-box use of a homomorphic encryption scheme. When m is prime, the (amortized) number of calls to the encryption scheme for each gate of the circuit is constant. All of our protocols are in fact UC-secure in the OT-hybrid model and can be generalized to multiparty computation with an arbitrary number of malicious parties.
Oblivious Linear Evaluation (OLE) is an algebraic generalization of oblivious transfer (OT) that forms a critical part of a growing number of applications. An OLE protocol over a modulus q enables the receiver party to securely evaluate a line a⋅ X+b chosen by the sender party on a secret point x∈ ℤq. Motivated by the big efficiency gap between OLE and OT and by fast OT extension techniques, we revisit the question of reducing OLE to OT, aiming to improve the communication cost of known reductions.