[Resource Topic] 2019/153: Overdrive2k: Efficient Secure MPC over $Z_{2^k}$ from Somewhat Homomorphic Encryption

Welcome to the resource topic for 2019/153

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

Authors: Emmanuela Orsini, Nigel P. Smart, 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.

ePrint: https://eprint.iacr.org/2019/153

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .