Paper 2014/296

Quantum Attacks on Classical Proof Systems - The Hardness of Quantum Rewinding

Andris Ambainis, Ansis Rosmanis, and Dominique Unruh

Abstract

Quantum zero-knowledge proofs and quantum proofs of knowledge are inherently difficult to analyze because their security analysis uses rewinding. Certain cases of quantum rewinding are handled by the results by Watrous (SIAM J Comput, 2009) and Unruh (Eurocrypt 2012), yet in general the problem remains elusive. We show that this is not only due to a lack of proof techniques: relative to an oracle, we show that classically secure proofs and proofs of knowledge are insecure in the quantum setting. More specifically, sigma-protocols, the Fiat-Shamir construction, and Fischlin's proof system are quantum insecure under assumptions that are sufficient for classical security. Additionally, we show that for similar reasons, computationally binding commitments provide almost no security guarantees in a quantum setting. To show these results, we develop the "pick-one trick", a general technique that allows an adversary to find one value satisfying a given predicate, but not two.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. MAJOR revision.FOCS 2014
Keywords
Quantum cryptographyproofs of knowledgerewindingrandom oracles
Contact author(s)
unruh @ ut ee
History
2014-10-19: last of 2 revisions
2014-04-30: received
See all versions
Short URL
https://ia.cr/2014/296
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/296,
      author = {Andris Ambainis and Ansis Rosmanis and Dominique Unruh},
      title = {Quantum Attacks on Classical Proof Systems - The Hardness of Quantum Rewinding},
      howpublished = {Cryptology ePrint Archive, Paper 2014/296},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/296}},
      url = {https://eprint.iacr.org/2014/296}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.