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 DOI: 10.1007/978-3-030-77870-5_16 (login may be required) Search ePrint Search Google EUROCRYPT 2021 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},
doi={10.1007/978-3-030-77870-5_16},
author={Amit Agarwal and James Bartusek and Vipul Goyal and Dakshita Khurana and Giulio Malavolta},
year=2021
}