Maliciously Secure Oblivious Linear Function Evaluation with Constant Overhead

BUG REPORT: In early 2021 we were made aware of a bug in Lemma 9.1 by Carmit Hazay, Muthu Venkitasubramaniam, Laasya Bangalore, and Rishabh Bhadauria. The bug does not have an easy fix and we are currently exploring whether a different proof can be found. Until then the results of this paper should not be considered proven and in particular the protocols should not be considered secure. We will later either update the e-print version with a new proof or withdraw the paper. ORIGINAL ABSTRACT: In this work we consider the problem of oblivious linear function evaluation (OLE). OLE is a special case of oblivious polynomial evaluation (OPE) and deals with the oblivious evaluation of a linear function $f(x)=ax+b$. This problem is non-trivial in the sense that the sender chooses $a,b$ and the receiver $x$, but the receiver may only learn $f(x)$. We present a highly efficient and UC-secure construction of OLE in the OT-hybrid model that requires only $O(1)$ OTs per OLE. The construction is based on noisy encodings introduced by Naor and Pinkas (STOC\u2799). Our main technical contribution solves a problem left open in their work, namely we show in a generic way how to achieve full simulation-based security from noisy encodings. All previous constructions using noisy encodings achieve only passive security. Our result requires novel techniques that might be of independent interest. Using our highly efficient OLE as a black box, we obtain a direct construction of an OPE protocol that simultaneously achieves UC-security and requires only $O(d)$ OTs, where $d$ is the degree of the polynomial that shall be evaluated