International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Post-Quantum Multi-Party Computation

Authors:
Amit Agarwal , University of Illinois Urbana Champaign
James Bartusek , UC Berkeley
Vipul Goyal , NTT Research and CMU
Dakshita Khurana , University of Illinois Urbana Champaign
Giulio Malavolta , Max Planck Institute for Security and Privacy
Download:
Search ePrint
Search Google
Conference: EUROCRYPT 2021
Abstract: We initiate the study of multi-party computation for classical functionalities in the plain model, with security against malicious quantum adversaries. We observe that existing techniques readily give a polynomial-round protocol, but our main result is a construction of *constant-round* post-quantum multi-party computation. We assume mildly super-polynomial quantum hardness of learning with errors (LWE), and quantum polynomial hardness of an LWE-based circular security assumption. Along the way, we develop the following cryptographic primitives that may be of independent interest: 1.) A spooky encryption scheme for relations computable by quantum circuits, from the quantum hardness of (a circular variant of) the LWE problem. This immediately yields the first quantum multi-key fully-homomorphic encryption scheme with classical keys. 2.) A constant-round post-quantum non-malleable commitment scheme, from the mildly super-polynomial quantum hardness of LWE. To prove the security of our protocol, we develop a new straight-line non-black-box simulation technique against parallel sessions that does not clone the adversary's state. This technique may also be relevant to the classical setting.
BibTeX
@inproceedings{eurocrypt-2021-30877,
  title={Post-Quantum Multi-Party Computation},
  publisher={Springer-Verlag},
  author={Amit Agarwal and James Bartusek and Vipul Goyal and Dakshita Khurana and Giulio Malavolta},
  year=2021
}