International Association for Cryptologic Research

International Association
for Cryptologic Research


Secure Multi-party Quantum Computation with a Dishonest Majority

Yfke Dulek , QuSoft and University of Amsterdam
Alex B. Grilo , QuSoft and CWI
Stacey Jeffery , QuSoft and CWI
Christian Majenz , QuSoft and CWI
Christian Schaffner , QuSoft and University of Amsterdam
DOI: 10.1007/978-3-030-45727-3_25 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2020
Abstract: The cryptographic task of secure multi-party (classical) computation has received a lot of attention in the last decades. Even in the extreme case where a computation is performed between k mutually distrustful players, and security is required even for the single honest player if all other players are colluding adversaries, secure protocols are known. For quantum computation, on the other hand, protocols allowing arbitrary dishonest majority have only been proven for k=2. In this work, we generalize the approach taken by Dupuis, Nielsen and Salvail (CRYPTO 2012) in the two-party setting to devise a secure, efficient protocol for multi-party quantum computation for any number of players k, and prove security against up to k-1 colluding adversaries. The quantum round complexity of the protocol for computing a quantum circuit of {CNOT, T} depth d is O(k (d + log n)), where n is the security parameter. To achieve efficiency, we develop a novel public verification protocol for the Clifford authentication code, and a testing protocol for magic-state inputs, both using classical multi-party computation.
Video from EUROCRYPT 2020
  title={Secure Multi-party Quantum Computation with a Dishonest Majority},
  booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
  series={Lecture Notes in Computer Science},
  keywords={Quantum cryptography;Multi-party computation;Computational security},
  author={Yfke Dulek and Alex B. Grilo and Stacey Jeffery and Christian Majenz and Christian Schaffner},