Skip to main navigation Skip to search Skip to main content

Secure multiparty quantum computation with (only) a strict honest majority

  • Michael Ben-Or
  • , Claude Crépeau
  • , Daniel Gottesman
  • , Avinatan Hassidim
  • , Adam Smith
  • Hebrew University of Jerusalem
  • McGill University
  • Perimeter Institute for Theoretical Physics
  • Weizmann Institute of Science

Research output: Contribution to Book/Report types › Contribution to conference proceedings › peer-review

117 Citations (Scopus)

Abstract

Secret sharing and multiparty computation (also called "secure function evaluation") are fundamental primitives in modern cryptography, allowing a group of mutually distrustful players to perform correct, distributed computations under the sole assumption that some number of them will follow the protocol honestly. This paper investigates how much trust is necessary - that is, how many players must remain honest - in order for distributed quantum computations to be possible. We present a verifiable quantum secret sharing (VQSS) protocol, and a general secure multiparty quantum computation (MPQC) protocol, which can tolerate any [n-1/2] cheaters among n players. Previous protocols for these tasks tolerated [n-1/4] and [n-1/6]cheaters, respectively. The threshold we achieve is tight - even in the classical case, "fair" multiparty computation is not possible if any set of n/2 players can cheat. Our protocols rely on approximate quantum error-correcting codes, which can tolerate a larger fraction of errors than traditional, exact codes. We introduce new families of authentication schemes and approximate codes tailored to the needs of our protocols, as well as new state purification techniques along the lines of those used in fault-tolerant quantum circuits.

Original languageEnglish
Title of host publication47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006
Pages249-258
Number of pages10
DOIs
Publication statusPublished - 2006
Externally publishedYes
Event47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006 - Berkeley, CA, United States
Duration: 21 Oct 2006 → 24 Oct 2006

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Conference

Conference47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006
Country/TerritoryUnited States
CityBerkeley, CA
Period21/10/06 → 24/10/06

ASJC Scopus subject areas

  • General Engineering

Fingerprint

Dive into the research topics of 'Secure multiparty quantum computation with (only) a strict honest majority'. These topics are generated from the title and abstract of the publication. Together, they form a unique fingerprint.

Cite this