Paper 2017/617

Secure Arithmetic Computation with Constant Computational Overhead

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


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.

Available format(s)
Cryptographic protocols
Publication info
Published by the IACR in CRYPTO 2017
foundationsconstant computational overhead
Contact author(s)
benny applebaum @ gmail com
2017-08-12: revised
2017-06-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benny Applebaum and Ivan Damgård and Yuval Ishai and Michael Nielsen and Lior Zichron},
      title = {Secure Arithmetic Computation with Constant Computational Overhead},
      howpublished = {Cryptology ePrint Archive, Paper 2017/617},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.