Fiat-Shamir Non-Interactive Proof System Basics
Fiat-Shamir protocol overview, Sigma protocols, breaking soundness in a quantum context, fixing strict soundness, and recap of Sigma protocols in a quantum setting. Explore the transformation of sigma protocol into a non-interactive proof system, classical security features, and zero-knowledge properties.
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
Fiat-Shamir and the Quantum Forking Conjecture 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) Fiat-Shamir 2 Dominique Unruh
Understanding FS: Sigma protocols Interactive proof system Honest-verifier zero-knowledge details omitted P P V V Special soundness Given: ???? for two ? ??? (same ???) Get: Witness 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 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 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. Other protocols? Yes. [U15] Extra conditions on sigma-protocol? This talk. Fiat-Shamir 6 Dominique Unruh
Fixing FS: Strict soundness Special soundness Given: ???? for two ? ??? (same ???) Get: Witness P P V V Strict soundness Given ???, ? ???, exists at most one ???? Honest-verifier zero- knowledge Fiat-Shamir 7 Dominique Unruh
Recap / preview Sigma-protocol: 3-msg proof system Special soundness:???? for two ? ??? witness Strict soundness: For every ???,? ??? at most one ???? Fiat-Shamir: Transforms sigma-protocol into non-interactive proof system Classical security: Sigma-proto is honest verifier ZK FS is zero-knowledge Sigma-proto has special soundness FS has soundness (+ extractability) Quantumly? + strict soudness ( ) Fiat-Shamir 8 Dominique Unruh
Quantum Forking Conjecture Let ?? denote a projective measurement ?? is circuit, makes ? queries to ? ? random function ? ?1 ???? ?? ?? |0 ?1 ?2 Then: Pr ?1= ?2 1/????(?) Fiat-Shamir 9 Dominique Unruh
Proving FS soundness Assume: Adversary ? outputs valid FS proof (for simplicity: Pr = 1) ????? ??? ? valid ? ??? ???? To show: Can efficiently extract witness (with Pr 1/????) Fiat-Shamir 10 Dominique Unruh
Proving FS soundness (ctd.) ????? ????? Compute witness ??? ??? ? ???1 ???? ? ? ? ? ? ??? ? ??? ???? ???? ???1,? ???1,????1 ???2,? ???2,????2 By special soundness ????= ???? To show: ?? ??????? ??????? ?/???? Fiat-Shamir 11 Dominique Unruh
Proving FS soundness (ctd.) ????? ????? ??? ??? ? ???1 ???? ? ? ? ? ? ??? ? ??? ???? ???? ???1,? ???1,????1 ???2,? ???2,????2 By strict soundness To show: ?? ????= ???? ?/???? Fiat-Shamir 12 Dominique Unruh
Proving FS soundness (ctd.) ????? ????? ??? ??? ? ???1 ???? ?? ?? ? ? ? ? ? ??? ? ??? ???? ???? ???1 ???2 Projective measurement Projective measurement To show: ?? ????= ???? ?/???? By QFC Fiat-Shamir 13 Dominique Unruh
Theorem Assume: QFC holds Assume: Sigma-protocol has special soundness strict soundness honest-verifier zero-knowledge Then: Fiat-Shamir is a proof of knowledge (simulation-sound extractable) zero-knowledge Fiat-Shamir 14 Dominique Unruh
Open problems Prove QFC (please help! ) Weaker condition than strict soundness? Sigma-protos with strict soundness Fiat-Shamir 15 Dominique Unruh
I thank you for your attention This research was supported by European Social Fund s Doctoral Studies and Internationalisation Programme DoRa Dominique Unruh
