### Fast Vector Oblivious Linear Evaluation from Ring Learning with Errors

Leo de Castro, Chiraag Juvekar, and Vinod Vaikuntanathan

##### Abstract

Oblivious linear evaluation (OLE) is a fundamental building block in multi-party computation protocols. In OLE, a sender holds a description of an affine function $f_{\alpha,\beta}(z)=\alpha z+\beta$, the receiver holds an input $x$, and gets $\alpha x+\beta$ (where all computations are done over some field, or more generally, a ring). Vector OLE (VOLE) is a generalization where the sender has many affine functions and the receiver learns the evaluation of all of these functions on a single point $x$. The state-of-the-art semi-honest VOLE protocols generally fall into two groups. The first group relies on standard assumptions to achieve security but lacks in concrete efficiency. These constructions are mostly based on additively homomorphic encryption (AHE) and are classified as folklore". The second group relies on less standard assumptions, usually properties of sparse, random linear codes, but they manage to achieve concrete practical efficiency. In this work, we present a conceptually simple VOLE protocol that derives its security from a standard assumption, namely Ring Learning with Errors (RLWE), while still achieving concrete efficiency comparable to the fastest VOLE protocols from non-standard coding assumptions. Furthermore, our protocol admits a natural extension to batch OLE (BOLE), which is yet another variant of OLE that computes many OLEs in parallel.

Available format(s)
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
implementationoblivious linear evaluation
Contact author(s)
ldec @ mit edu
History
Short URL
https://ia.cr/2020/685

CC BY

BibTeX

@misc{cryptoeprint:2020/685,
author = {Leo de Castro and Chiraag Juvekar and Vinod Vaikuntanathan},
title = {Fast Vector Oblivious Linear Evaluation from Ring Learning with Errors},
howpublished = {Cryptology ePrint Archive, Paper 2020/685},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/685}},
url = {https://eprint.iacr.org/2020/685}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.