Quantum attacks on classical proof systems: the hardness of quantum rewinding

DOI10.1109/FOCS.2014.57MaRDI QIDQ6947214zbMATH OpenFDO

Authors Andris Ambainis, Ansis Rosmanis, Dominique Unruh

Publication date 5 August 2025

Full work available at URL https://doi.org/10.1109/FOCS.2014.57

Mathematics Subject Classification ID

Combinatorics (05-XX) Computer science (68-XX) Information and communication theory, circuits (94-XX)

Cited in

(11)

• Straight-line knowledge extraction for multi-round protocols
• On one-shot signatures, quantum vs. classical binding, and obfuscating permutations
• Privacy-preserving certificate-less authenticated key exchange with key registration privacy
• A computational separation between quantum no-cloning and no-telegraphing
• Generalized hybrid search with applications to blockchains and hash function security
• Rewindable quantum computation and its equivalence to cloning and adaptive postselection
• QCCA security of Fujisaki-Okamoto transformation in the quantum random oracle model
• Verifiable quantum advantage without structure
• The quantum supremacy Tsirelson inequality
• On quantum query complexities of collision-finding in non-uniform random functions
• A note on the minimality of one-way functions in post-quantum cryptography

This page was built for publication: Quantum attacks on classical proof systems: the hardness of quantum rewinding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6947214)