Post-Quantum Security of Fiat-Shamir Protocols
Dive into the world of post-quantum security with the Fiat-Shamir protocols explained by Dominique Unruh. Explore topics like non-interactive proof systems, zero-knowledge proofs, and breaking soundness in a quantum setting. Discover the main results comparing classical Fiat-Shamir with sigma protocols, all through an in-depth exploration by Dominique Unruh.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Post-Quantum Security of Fiat-Shamir Dominique Unruh University of Tartu Dominique Unruh
Fiat-Shamir (overview) Non-interactive proof system: Prover Prover Verifier Verifier ???,? ??? ,???? Quantum Quantum secure? secure? witness statement statement Zero-knowledge proof of knowledge Verifier learns nothing Prover must know witness Signature scheme (Signer proves knowledge of sk) Quantum Fiat-Shamir 2 Dominique Unruh
Understanding FS: Sigma protocols Honest-verifier zero-knowledge Interaction ? efficiently simulated Interactive proof system ? P P V V Special soundness Given: ???? for two ? ??? (same ???) Get: Witness Quantum Fiat-Shamir 3 Dominique Unruh
Understanding FS: The construction Verifier Prover ???,? ???,???? ? ??? ?(???) P P V V Prover sends simulated sigma-proto interaction Soundness of sigma-protocol carries over Quantum Fiat-Shamir 4 Dominique Unruh
Breaking FS soundness (quantum) Artificial sigma-protocol [Ambainis,Rosmanis,U14] (relative to specific oracles) Can give ???? for any? ??? (using | ) Only once (| used up) FS insecure (soundness) But: sigma-protocol has special soundness | P P Quantum Fiat-Shamir 5 Dominique Unruh
Breaking FS soundness (quantum) FS not secure in general For quantum attackers Relative to specific oracles Ways out: Non-relativizing proofs? Doubtful. [U15] [Dagdelen, Fischlin,Gagliardoni13] Other protocols? Yes. Extra conditions on sigma-protocol? This talk. Quantum Fiat-Shamir 6 Dominique Unruh
Main result Sigma protocol than classical Fiat-Shamir than classical Weaker Stronger Statistical Statistical soundness soundness Simulation Simulation soundness soundness Reduction to quantum search Zero Zero Honest Honest verifier ZK verifier ZK Adaptive RO reprogramming knowledge knowledge Unpredictable commitments Complete Complete Quantum Fiat-Shamir 7 Dominique Unruh
Soundness proof Sigma protocol Def:? ???is promising if ???? statistical soundness For any ???, few promising ? ??? P P V V Hard to find: ??? with ?(?,???) promising Fiat-Shamir P P V V Hard to break Fiat-Shamir soundness: Finding valid ???,? ?,??? ,???? ???,? ?,??? ,???? Quantum Fiat-Shamir 8 Dominique Unruh
What about signatures? Quantum Classical approach: Sigma protocol Statistical Fiat-Shamir (as proof) Special Special soundness soundness Simulation sound Simulation sound extractability extractability Fiat-Shamir (as signature) ? Unforgeability Unforgeability Honest Honest verifier ZK verifier ZK Zero knowledge Zero knowledge Dual-mode Hard Hard instances instances Hard to guess ?? from ?? ?? indistinguishable from ?? without ?? Quantum Fiat-Shamir 9 Dominique Unruh
Open problems Suitable sigma protocols [Kiltz,Lyubashevsky,Schaffner]? Stronger guarantees: Extractability? Weaker assms: Computational soundness? Tightness of reductions Quantum Fiat-Shamir 10 Dominique Unruh
I thank you for your attention This research was supported by European Social Fund s Doctoral Studies and Internationalisation Programme DoRa 11 Dominique Unruh
