We show that the long-standing assumption of "no-communication" between the provers of the two-prover model is not sufficiently precise to guarantee the security of a bit commitment scheme against malicious adversaries. Indeed, we show how a simple correlated random variable, which does not allow to communicate, can be used to cheat a simplified version (sBGKW) of the bit commitment scheme of Ben-Or, Goldwasser, Kilian, and Wigderson [BGKW88]. Instead we propose a stronger notion of separation between the two provers which takes into account correlated computations. To emphasize the risk that entanglement still represents for the security of a commitment scheme despite the stronger notion of separation, we present two variations of the sBGKW scheme that can be cheated by quantum provers with probability (almost) one. A complete proof of security against quantum adversaries is then given for the sBGKW scheme. By reduction we also obtain the security of the original BGKW scheme against quantum provers. For the unfamiliar reader, basic notions of quantum processing are provided to facilitate the understanding of the proofs presented.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.101174 |
| Date | January 2007 |
| Creators | Simard, Jean-Raymond. |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Master of Science (School of Computer Science.) |
| Rights | © Jean-Raymond Simard, 2007 |
| Relation | alephsysno: 002600985, proquestno: AAIMR32783, Theses scanned by UMI/ProQuest. |
Page generated in 0.0016 seconds