Paper 2019/153

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

Emmanuela Orsini, Nigel P. Smart, and Frederik Vercauteren


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.CT-RSA 2020
Contact author(s)
emmanuela orsini @ kuleuven be
nigel smart @ kuleuven be
frederik vercauteren @ kuleuven be
2019-11-23: last of 3 revisions
2019-02-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Emmanuela Orsini and Nigel P.  Smart and Frederik Vercauteren},
      title = {Overdrive2k: Efficient Secure MPC over $Z_{2^k}$ from Somewhat Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2019/153},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.