Paper 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.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint. MINOR revision.
- Keywords
- OLEUC-secureOT-hybrid model
- Contact author(s)
- tobias nilges @ cs au dk
- History
- 2021-07-19: revised
- 2017-05-13: received
- See all versions
- Short URL
- https://ia.cr/2017/409
- License
-
CC BY