Paper 2023/270

Actively Secure Arithmetic Computation and VOLE with Constant Computational Overhead

Benny Applebaum, Tel Aviv University
Niv Konstantini, Tel Aviv University
Abstract

We study the complexity of two-party secure arithmetic computation where the goal is to evaluate an arithmetic circuit over a finite field $F$ in the presence of an active (aka malicious) adversary. In the passive setting, Applebaum et al. (Crypto 2017) constructed a protocol that only makes a *constant* (amortized) number of field operations per gate. This protocol uses the underlying field $F$ as a black box, makes black-box use of (standard) oblivious transfer, and its security is based on arithmetic analogs of well-studied cryptographic assumptions. We present an actively-secure variant of this protocol that achieves, for the first time, all the above features. The protocol relies on the same assumptions and adds only a minor overhead in computation and communication. Along the way, we construct a highly-efficient Vector Oblivious Linear Evaluation (VOLE) protocol and present several practical and theoretical optimizations, as well as a prototype implementation. Our most efficient variant can achieve an asymptotic rate of $1/4$ (i.e., for vectors of length $w$ we send roughly $4w$ elements of $F$), which is only slightly worse than the passively-secure protocol whose rate is $1/3$. The protocol seems to be practically competitive over fast networks, even for relatively small fields $F$ and relatively short vectors. Specifically, our VOLE protocol has 3 rounds, and even for 10K-long vectors, it has an amortized cost per entry of less than 4 OT's and less than 300 arithmetic operations. Most of these operations (about 200) can be pre-processed locally in an offline non-interactive phase. (Better constants can be obtained for longer vectors.) Some of our optimizations rely on a novel intractability assumption regarding the non-malleability of noisy linear codes that may be of independent interest. Our technical approach employs two new ingredients. First, we present a new information-theoretic construction of Conditional Disclosure of Secrets (CDS) and show how to use it in order to immunize the VOLE protocol of Applebaum et al. against active adversaries. Second, by using elementary properties of low-degree polynomials, we show that, for some simple arithmetic functionalities, one can easily upgrade Yao's garbled-circuit protocol to the active setting with a minor overhead while preserving the round complexity.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in EUROCRYPT 2023
Keywords
ProtocolsSecure ComputationNoisy Codewords
Contact author(s)
benny applebaum @ gmail com
NivKonst @ gmail com
History
2023-02-23: approved
2023-02-23: received
See all versions
Short URL
https://ia.cr/2023/270
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/270,
      author = {Benny Applebaum and Niv Konstantini},
      title = {Actively Secure Arithmetic Computation and {VOLE} with Constant Computational Overhead},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/270},
      year = {2023},
      url = {https://eprint.iacr.org/2023/270}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.