Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier

on YouTube ↗13m

" summary

Proves that Kilian's original succinct-argument construction becomes post-quantum secure when paired with a post-quantum hash by giving a general quantum-rewinding method that extracts unbounded accepting transcripts from an efficient quantum prover. Technique uses amplitude amplification / Marriott–Watrous style projections to preserve the adversary's success probability rather than its full state, turning prior constant-rewind bounds into an unbounded extractor and enabling post-quantum soundness (plus applications like GMW-86 zero knowledge vs. quantum verifiers).

AI-written summary · about

" chapters (7)

1. 0:00Start
2. 1:00Fundamental formula of cryptography
3. 1:41Why are quantum computers a threat?
4. 2:04Post-quantum cryptography (classical crypto secure against quantum attack)
5. 5:21Rewinding a quantum adversary
6. 5:54Succinct Arguments for NP Kilian92 NP relation R
7. 10:27Recap

" related talks

• 01h 11mQuantum Rewinding Tutorial, Part 2: How to Run a Quantum Attacker Many TimesAlex Lombardi, Fermi Ma · Quantum and Lattices Joint Reunion Workshop
• 01h 12mQuantum Rewinding Tutorial, Part 1: Motivation and Early Rewinding TechniquesAlex Lombardi, Fermi Ma · Quantum and Lattices Joint Reunion Workshop
• 01h 14mQuantum Rewinding Tutorial, Part 3: Zero Knowledge Simulation Beyond WatrousAlex Lombardi, Fermi Ma · Quantum and Lattices Joint Reunion Workshop
• 58mQuantum 2Mark Zhandry · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 24mA Framework for Post-Quantum Succinct ArgumentsAlessandro Chiesa · Zcon1: Zero to Privacy Hero 2019
• 01h 04mQuantum 1Mark Zhandry · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 03mQuantum Proofs of KnowledgeDominique Unruh · Quantum Games and Protocols
• 48mCommitments to Quantum StatesFermi Ma · Minimal Complexity Assumptions for Cryptography 2023