Quantum Attacks on Classical Proof Systems: The Hardness of Quantum Rewinding
- 1 October 2014
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 474-483
- https://doi.org/10.1109/focs.2014.57
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.Keywords
Other Versions
This publication has 22 references indexed in Scilit:
- The Fiat–Shamir Transformation in a Quantum WorldLecture Notes in Computer Science, 2013
- Quantum-Secure Message Authentication CodesLecture Notes in Computer Science, 2013
- Quantum Proofs of KnowledgeLecture Notes in Computer Science, 2012
- Secure Identity-Based Encryption in the Quantum Random Oracle ModelLecture Notes in Computer Science, 2012
- Zero-Knowledge against Quantum AttacksSIAM Journal on Computing, 2009
- Communication-Efficient Non-interactive Proofs of Knowledge with Online ExtractorsLecture Notes in Computer Science, 2005
- Tight Bounds on Quantum SearchingFortschritte der Physik, 1998
- Quantum cryptanalysis of hash and claw-free functionsACM SIGACT News, 1997
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systemsJournal of the ACM, 1991
- A single quantum cannot be clonedNature, 1982