Proofs of Quantumness from Trapdoor Permutations
summary
Constructs proofs of quantumness from trapdoor permutations by coherently executing interactive hashing and then running a KMCVY22-style challenge, replacing the usual collision-resistance assumption. Uses a full-domain trapdoor permutation, sends f and successive random bits, and forces the prover into a superposition with two preimages y0,y1 so classical PPT adversaries cannot produce both preimages. Protocol achieves standard completeness and soundness; open problems include removing full-domain, using trapdoor functions or one-way functions, and proving quantum security of the NOVY interactive-hashing step.
AI-written summary · about
chapters (7)
- 0:00Introduction to proofs
- 1:21First construction
- 3:29Soundness analysis
- 4:54Improved construction
- 8:35Motivation for new results
- 11:20The proposed construction
- 14:43Conclusion and open problems
related talks
58mQuantum 2
01h 13mQuantum 3
32mQuantum Obfuscation of Classical Circuits
59mQuantum cryptography and quantum complexity
46mObfuscation of Unitary Quantum Programs
16mQuantum Information Meets Cryptography
01h 11mQuantum Rewinding Tutorial, Part 2: How to Run a Quantum Attacker Many Times
59mAn Introduction to Quantum Obfuscation