Cryptology ePrint Archive: Report 2017/409

Maliciously Secure Oblivious Linear Function Evaluation with Constant Overhead

Satrajit Ghosh and Jesper Buus Nielsen and Tobias Nilges

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'99). 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.

Category / Keywords: cryptographic protocols / OLE, UC-secure, OT-hybrid model

Date: received 11 May 2017

Contact author: tobias nilges at cs au dk

Available format(s): PDF | BibTeX Citation

Version: 20170513:153207 (All versions of this report)

Short URL: ia.cr/2017/409

Discussion forum: Show discussion | Start new discussion