Paper 2024/1879

Practical Zero-Knowledge PIOP for Maliciously Secure Multiparty Homomorphic Encryption

Abstract

Homomorphic encryption (HE) is a foundational technology in privacy-enhancing cryptography, enabling computation over encrypted data. Recently, generalized HE primitives designed for multi-party applications, such as multi-party HE (MPHE), have garnered significant research interest. While constructing secure multi-party protocols from MPHE in the semi-honest model is straightforward, achieving malicious security remains challenging as it requires zero-knowledge arguments of knowledge (ZKAoKs) for MPHE ciphertexts and public keys. In this work, we design practical ZKAoKs for MPHE that validate the well-formedness of public keys and ciphertexts. Specifically, we develop our ZKAoKs within the polynomial interactive oracle proof (PIOP) framework. To achieve this, we introduce novel optimization techniques that seamlessly integrate constraints for MPHE into the PIOP framework, enabling the design of PIOPs for validating all types of MPHE public keys, including relinearization and automorphism keys. To the best of our knowledge, our construction is the first ZKAoK for MPHE that validates automorphism keys. We instantiate our PIOP using a lattice-based polynomial commitment scheme (PCS). When compared with the previous state-of-the-art construction, PELTA (CCS' 2023), our implementation achieves a 5.4x reduction in proof size, a 111x speed-up in proof generation, and a 768x improvement in verification time for validating the encryption key. In addition to the encryption key, we provide benchmark results for all types of ZKAoKs required for MPHE, presenting the first concrete performance results in compiling passively secure MPHE-based protocols into maliciously secure ones.