Cryptology ePrint Archive: Report 2018/762

Generalizing the SPDZ Compiler For Other Protocols

Toshinori Araki and Assi Barak and Jun Furukawa and Marcel Keller and Yehuda Lindell and Kazuma Ohara and Hikaru Tsuchida

Abstract: Protocols for secure multiparty computation (MPC) enable a set of mutually distrusting parties to compute an arbitrary function of their inputs while preserving basic security properties like \emph{privacy} and \emph{correctness}. The study of MPC was initiated in the 1980s where it was shown that any function can be securely computed, thus demonstrating the power of this notion. However, these proofs of feasibility were theoretical in nature and it is only recently that MPC protocols started to become efficient enough for use in practice. Today, we have protocols that can carry out large and complex computations in very reasonable time (and can even be very fast, depending on the computation and the setting). Despite this amazing progress, there is still a major obstacle to the adoption and use of MPC due to the huge expertise needed to design a specific MPC execution. In particular, the function to be computed needs to be represented as an appropriate Boolean or arithmetic circuit, and this requires very specific expertise. In order to overcome this, there has been considerable work on compilation of code to (typically) Boolean circuits. One work in this direction takes a different approach, and this is the SPDZ compiler (not to be confused with the SPDZ protocol) that takes high-level Python code and provides an MPC run-time environment for securely executing that code. The SPDZ compiler can deal with arithmetic and non-arithmetic operations and is extremely powerful. However, until now, the SPDZ compiler could only be used for the specific SPDZ family of protocols, making its general applicability and usefulness very limited.

In this paper, we extend the SPDZ compiler so that it can work with general underlying protocols. Our SPDZ extensions were made in mind to enable the use of SPDZ for arbitrary protocols and to make it easy for others to integrate existing and new protocols. We integrated three different types of protocols, an honest-majority protocol for computing arithmetic circuits over a field (for any number of parties), a three-party honest majority protocol for computing arithmetic circuits over the ring of integers $\Z_{2^n}$, and the multiparty BMR protocol for computing Boolean circuits. We show that a single high-level SPDZ-Python program can be executed using all of these underlying protocols (as well as the original SPDZ protocol), thereby making SPDZ a true general run-time MPC environment.

In order to be able to handle both arithmetic and non-arithmetic operations, the SPDZ compiler relies on conversions from field elements to bits and back. However, these conversions do not apply to ring elements (in particular, they require element division), and we therefore introduce new bit decomposition and recomposition protocols for the ring over integers with replicated secret sharing. These conversions are of independent interest and utilize the structure of $\Z_{2^n}$ (which is much more amenable to bit decomposition than prime-order fields), and are thus much more efficient than all previous methods.

We demonstrate our compiler extensions by running a complex SQL query and a decision tree evaluation over all protocols.

Category / Keywords: cryptographic protocols / secure multiparty computation

Original Publication (with minor differences): ACM CCS 2018
DOI:
10.1145/3243734.3243854

Date: received 19 Aug 2018, last revised 1 Oct 2018

Contact author: lindell at biu ac il

Available format(s): PDF | BibTeX Citation

Version: 20181002:054546 (All versions of this report)

Short URL: ia.cr/2018/762


[ Cryptology ePrint archive ]