Passer à la navigation principale Passer à la recherche Passer au contenu principal

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

Résultats de recherche: Chapitre dans un livre, rapport, actes de conférence › Participation à un ouvrage collectif lié à un colloque ou une conférence › Revue par des pairs

116 Citations (Scopus)

Résumé

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.

langue originaleAnglais
titre47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006
Pages249-258
Nombre de pages10
Les DOIs
étatPublié - 2006
Modification externeOui
Evénement47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006 - Berkeley, CA, Etats-Unis
Durée: 21 oct. 2006 → 24 oct. 2006

Série de publications

NomProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (imprimé)0272-5428

Conférence

Conférence47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006
Pays/TerritoireEtats-Unis
La villeBerkeley, CA
Période21/10/06 → 24/10/06

Empreinte digitale

Voici les principaux termes ou expressions associés à « Secure multiparty quantum computation with (only) a strict honest majority ». Ces libellés thématiques sont générés à partir du titre et du résumé de la publication. Ensemble, ils forment une empreinte digitale unique.

Citer cette ressource