Post-Quantum Multi-Party Computation in Constant Rounds

James Bartusek (UC Berkeley)
Lattices: Algorithms, Complexity, and Cryptography
Seminar, Apr. 21, 2020

This talk will describe the first constant-round classical MPC protocol in the plain model secure against quantum polynomial-time adversaries. Security follows from the mildy superpolynomial hardness of LWE and an LWE-based circular security assumption. At a technical level, the protocol relies on a novel parallel no-cloning non-black-box simulation technique that uses the recently introduced no-cloning technique of Bitansky and Shmueli (STOC 2020) as a starting point. Parallel simulation is enabled by the first construction of spooky encryption for relations computable by quantum circuits. In addition, the protocol makes crucial use of post-quantum non-malleable commitments in the plain model, which are constructed by porting the techniques of Khurana and Sahai (FOCS 2017) to the post-quantum setting.


Based on joint work with Amit Agarwal, Vipul Goyal, Dakshita Khurana, and Giulio Malavolta.