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

Abstract

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