TinyOLE: Efficient Actively Secure Two-Party Computation from Oblivious Linear Function Evaluation

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 \in \F$ and $b \in \F$, and the receiver inputs a field element $x \in \F$ and learns only $f(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^\kappa)$ can be implemented with communication $O(\kappa)$. This gives a protocol with communication complexity $O(\vert C \vert \kappa)$ 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