**Secure Arithmetic Computation with Constant Computational Overhead**

*Benny Applebaum and Ivan Damgård and Yuval Ishai and Michael Nielsen and Lior Zichron*

**Abstract: **We study the complexity of securely evaluating an arithmetic circuit over a finite field $F$ in the setting of secure two-party computation with semi-honest adversaries. In all existing protocols, the number of arithmetic operations per
multiplication gate grows either linearly with $\log |F|$ or polylogarithmically with the security parameter. We present the first protocol that only makes a *constant* (amortized) number of field operations per gate. The protocol uses the underlying field $F$ as a black box, and its security is based on arithmetic analogues of well-studied cryptographic assumptions.

Our protocol is particularly appealing in the special case of securely evaluating a ``vector-OLE'' function of the form $\vec{a}x+\vec{b}$, where $x\in F$ is the input of one party and $\vec{a},\vec{b}\in F^w$ are the inputs of the other party. In this case, which is motivated by natural applications, our protocol can achieve an asymptotic rate of $1/3$ (i.e., the communication is dominated by sending roughly $3w$ elements of $F$). Our implementation of this protocol suggests that it outperforms competing approaches even for relatively small fields $F$ and over fast networks.

Our technical approach employs two new ingredients that may be of independent interest. First, we present a general way to combine any linear code that has a fast encoder and a cryptographic (``LPN-style'') pseudorandomness property with another linear code that supports fast encoding and *erasure-decoding*, obtaining a code that inherits both the pseudorandomness feature of the former code and the efficiency features of the latter code. Second, we employ local *arithmetic* pseudo-random generators, proposing arithmetic generalizations of boolean candidates that resist all known attacks.

**Category / Keywords: **cryptographic protocols / foundations, constant computational overhead

**Original Publication**** (in the same form): **IACR-CRYPTO-2017

**Date: **received 22 Jun 2017, last revised 27 Jun 2017

**Contact author: **benny applebaum at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20170627:191617 (All versions of this report)

**Short URL: **ia.cr/2017/617

[ Cryptology ePrint archive ]