MHz2k: MPC from HE over Z2k with New Packing, Simpler Reshare, and Better ZKP

Jung Hee Cheon, Dongwoo Kim, Keewoo Lee

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

9 Scopus citations

Abstract

We propose a multi-party computation (MPC) protocol over Z2k secure against actively corrupted majority from somewhat homomorphic encryption. The main technical contributions are: (i) a new efficient packing method for Z2k -messages in lattice-based somewhat homomorphic encryption schemes, (ii) a simpler reshare protocol for level-dependent packings, (iii) a more efficient zero-knowledge proof of plaintext knowledge on cyclotomic rings Z[ X] / ΦM(X) with M being a prime. Integrating them, our protocol shows from 2.2x upto 4.8x improvements in amortized communication costs compared to the previous best results. Our techniques not only improve the efficiency of MPC over Z2k considerably, but also provide a toolkit that can be leveraged when designing other cryptographic primitives over Z2k.

Original languageEnglish
Title of host publicationAdvances in Cryptology – CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Proceedings
EditorsTal Malkin, Chris Peikert
PublisherSpringer Science and Business Media Deutschland GmbH
Pages426-456
Number of pages31
ISBN (Print)9783030842444
DOIs
StatePublished - 2021
Event41st Annual International Cryptology Conference, CRYPTO 2021 - Virtual, Online
Duration: 16 Aug 202120 Aug 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12826 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference41st Annual International Cryptology Conference, CRYPTO 2021
CityVirtual, Online
Period16/08/2120/08/21

Keywords

  • Dishonest majority
  • Homomorphic encryption
  • Multi-party computation
  • Packing method
  • Z
  • Zero-knowledge proof

Fingerprint

Dive into the research topics of 'MHz2k: MPC from HE over Z2k with New Packing, Simpler Reshare, and Better ZKP'. Together they form a unique fingerprint.

Cite this