Cryptology ePrint Archive: Report 2019/153

Overdrive2k: Efficient Secure MPC over $Z_{2^k}$ from Somewhat Homomorphic Encryption

Emmanuela Orsini and Nigel P. Smart and Frederik Vercauteren

Abstract: Recently, Cramer et al. (CRYPTO 2018) presented a protocol, SPDZ2k, for actively secure multiparty computation for dishonest majority in the pre-processing model over the ring $Z_{2^k}$, instead of over a prime field $F_p$. Their technique used oblivious transfer for the pre-processing phase, more specifically the MASCOT protocol (Keller et al. CCS 2016). In this paper we describe a more efficient technique for secure multiparty computation over $Z_{2^k}$ based on somewhat homomorphic encryption. In particular we adapt the Overdrive approach (Keller et al. EUROCRYPT 2018) to obtain a protocol which is more like the original SPDZ protocol (Damgård et al. CRYPTO 2012).

To accomplish this we introduce a special packing technique for the BGV encryption scheme operating on the plaintext space defined by the SPDZ2k protocol, extending the ciphertext packing method used in SPDZ to the case of $Z_{2^k}$. We also present a more complete pre-processing phase for secure computation modulo $2^k$ by adding a new technique to produce shared random bits. These are needed in a number of online protocols and are quite expensive to generate using the MASCOT-based method given in the original SPDZ2k paper.

Our approach can be applied to the High-Gear variant of Overdrive, leading to a protocol whose overall efficiency is up to three times better than the OT-based methodology.

Category / Keywords: cryptographic protocols /

Date: received 13 Feb 2019, last revised 13 May 2019

Contact author: emmanuela orsini at kuleuven be,nigel smart@kuleuven be,frederik vercauteren@kuleuven be

Available format(s): PDF | BibTeX Citation

Version: 20190513:095528 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]