### Post-Quantum Multi-Party Computation

Amit Agarwal, James Bartusek, Vipul Goyal, Dakshita Khurana, and Giulio Malavolta

##### Abstract

We initiate the study of multi-party computation for classical functionalities (in the plain model) with security against malicious polynomial-time 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 polynomial quantum 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 an LWE-based circular security assumption. This yields the first quantum multi-key fully-homomorphic encryption scheme with classical keys. - Constant-round zero-knowledge secure against multiple parallel quantum verifiers from spooky encryption for relations computable by quantum circuits. To enable this, we develop a new straight-line non-black-box simulation technique against parallel verifiers that does not clone the adversary's state. This forms the heart of our technical contribution and may also be relevant to the classical setting. - A constant-round post-quantum non-malleable commitment scheme, from the mildly super-polynomial quantum hardness of LWE.

Available format(s)
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
multi-party computationpost-quantum
Contact author(s)
bartusek james @ gmail com
History
Short URL
https://ia.cr/2020/1395

CC BY

BibTeX

@misc{cryptoeprint:2020/1395,
author = {Amit Agarwal and James Bartusek and Vipul Goyal and Dakshita Khurana and Giulio Malavolta},
title = {Post-Quantum Multi-Party Computation},
howpublished = {Cryptology ePrint Archive, Paper 2020/1395},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/1395}},
url = {https://eprint.iacr.org/2020/1395}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.