TY - GEN
T1 - Post-Quantum Multi-Party Computation
AU - Agarwal, Amit
AU - Bartusek, James
AU - Goyal, Vipul
AU - Khurana, Dakshita
AU - Malavolta, Giulio
N1 - Funding Information:
A. Agarwal and D. Khurana—This material is based on work supported in part by DARPA under Contract No. HR001120C0024. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Government or DARPA. V. Goyal—Supported in part by the DARPA SIEVE program, NSF award 1916939, a gift from Ripple, a DoE NETL award, a JP Morgan Faculty Fellowship, a PNC center for financial services innovation award, and a Cylab seed funding award.
Publisher Copyright:
© 2021, International Association for Cryptologic Research.
PY - 2021
Y1 - 2021
N2 - 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: 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.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.
AB - 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: 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.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.
UR - http://www.scopus.com/inward/record.url?scp=85111377899&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85111377899&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-77870-5_16
DO - 10.1007/978-3-030-77870-5_16
M3 - Conference contribution
AN - SCOPUS:85111377899
SN - 9783030778699
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 435
EP - 464
BT - Advances in Cryptology – EUROCRYPT 2021 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
A2 - Canteaut, Anne
A2 - Standaert, François-Xavier
PB - Springer
T2 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2021
Y2 - 17 October 2021 through 21 October 2021
ER -