Post-Quantum Multi-Party Computation

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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: 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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – EUROCRYPT 2021 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
EditorsAnne Canteaut, François-Xavier Standaert
PublisherSpringer
Pages435-464
Number of pages30
ISBN (Print)9783030778699
DOIs
StatePublished - 2021
Event40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2021 - Zagreb, Croatia
Duration: Oct 17 2021Oct 21 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12696 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2021
Country/TerritoryCroatia
CityZagreb
Period10/17/2110/21/21

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Post-Quantum Multi-Party Computation'. Together they form a unique fingerprint.

Cite this