Cryptology ePrint Archive: Report 2019/164

Use your Brain! Arithmetic 3PC For Any Modulus with Active Security

Hendrik Eerikson and Marcel Keller and Claudio Orlandi and Pille Pullonen and Joonas Puura and Mark Simkin

Abstract: Secure multiparty computation (MPC) allows a set of mutually distrustful parties to compute a public function on their private inputs without revealing anything beyond the output of the computation. In recent years, a large effort has undergone into designing and implementing MPC protocols that can be used in practice. This paper focuses on the specific case of actively secure three-party computation with an honest majority, which is among the most popular models for real-world applications of MPC. In particular, we are interested in solutions which allow to evaluate arithmetic circuits over real-world CPU word sizes, like 32- and 64-bit words, that are secure against active adversaries that may arbitrarily deviate from the protocol description.

This paper presents better protocols for this important setting. Our starting point is the novel compiler of Damgård et al. from CRYPTO 2018, and we improve it in several ways: First, we present an improved version of their compiler which reduces the online communication complexity by a factor of 2. Next, we replace their preprocessing protocol (which performs arithmetic modulo a large prime) with a more efficient preprocessing which only performs arithmetic modulo powers of two (and is therefore more efficient). And finally, we present a novel protocol which replaces the preprocessing phase with a "postprocessing" check. The protocols we construct offer different efficiency tradeoffs and can therefore outperform each other in different deployment settings.

We also provide a fully-fledged implementation of our protocols, and extensive benchmarks of our framework in a LAN and in different WAN settings. Concretely, we achieve a throughput of 3 million 64-bit multiplications per second with each of the three parties located on a different continent and 10 million in the same location, thus achieving the most effcient implementation of a three-party computation protocol for arithmetic circuits modulo $2^{64}$ with active security.

Category / Keywords: implementation / Three-Party Computation, Blackbox Compiler, Honest Majority

Date: received 15 Feb 2019, last revised 31 Jul 2019

Contact author: simkin at cs au dk,orlandi@cs au dk

Available format(s): PDF | BibTeX Citation

Version: 20190731:164525 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]