Quantum NIZK Proofs Explained with Dominique Unruh

Explore the concept of non-interactive quantum zero-knowledge proofs with Dominique Unruh at the University of Tartu. Discover how these proofs ensure verifier acceptance of true statements while learning nothing, and delve into the various implementations and implications of Quantum NIZK proofs with random oracle.

• Quantum
• NIZK Proofs
• Dominique Unruh
• University of Tartu

samanv Follow

Uploaded on Oct 08, 2024 | 0 Views

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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Non-interactive quantum zero-knowledge proofs Dominique Unruh University of Tartu Dominique Unruh

2. Intro: Proof systems Statement x Witness w Statement x P P V V Soundness: Verifier accepts only true statements Zero-knowledge: Verifier learns nothing Quantum NIZK with random oracle 2 Dominique Unruh

3. Intro: Proof systems Non-interactive ZK Sigma-protocols commitment proof P P V V P P V V challenge response Ease of use Concurrency, offline Need RO or CRS Lack of combiners Specific languages Specific 3-round proofs Versatile combiners Simple to analyze Weak security Quantum NIZK with random oracle 3 Dominique Unruh

4. Intro: Best of two worlds Fiat-Shamir: Convert sigma-proto into NIZK commitment com, H(com), resp P P P P V V V V challenge response Ease of use (concurrent, offline) Versatile combiners Simple analysis Uses random oracle Quantum NIZK with random oracle 4 Dominique Unruh

5. Intro: Best of two world (ctd.) Fiat-Shamir also implies: Sigma-proto signatures (in RO) Fischlin s scheme: Also: sigma-proto NIZK (in RO) No rewinding (online extraction) Less efficient Quantum NIZK with random oracle 5 Dominique Unruh

6. Post-quantum security Quantum computers Potential future threat Not there yet, but we need to be prepared Post-quantum cryptography Classical crypto, secure against quantum attack Is Fiat-Shamir post-quantum secure? Quantum NIZK with random oracle 6 Dominique Unruh

7. Fiat-Shamir soundness com, H(com), resp P P V V Fiat-Shamir: com Can be seen as: H H chal := H(com) P P V V response Rewinding Get two responses Special soundness of sigma-proto Compute witness messed-up state Quantum NIZK with random oracle 7 Dominique Unruh

8. Saving (quantum) Fiat-Shamir? Existing quantum rewinding techniques Watrous / Unruh Do not work with superposition queries Ambainis, Rosmanis, Unruh: No relativizing security proof Consequence: Avoid rewinding! Quantum NIZK with random oracle 8 Dominique Unruh

9. NIZK without rewinding Fischlin s scheme: No rewinding Online extraction: List of queries Witness But again: No relativizing security proof List of queries: Not well-defined: need to measure to get them Disturbs state Quantum NIZK with random oracle 9 Dominique Unruh

10. Quantum online-extraction Prover: ? Idea: H H P P ?(?) Make RO invertible (for extractor) proof Extractor: H H - -1 1 Ensure: all needed outputs contained in proof ? witness Quantum NIZK with random oracle 10 Dominique Unruh

11. Protocol construction ????11 ????12 ????1? hash invertibly ( ) ? ??11 ? ??12 ? ??1? ??? ????12 ???1 ????21 ????22 ????2? ? ??21 ? ??22 ? ??2? all this together is the proof ???2 ????2? W.h.p. at least one ??? has two valid ???? ?????1 ?????2 ?????? ? ???1 ? ???2 ? ???? ?????1 ???? Extractor gets them by inverting hash Hash to get selection what to open (Fiat-Shamir style) Two ???? witness Quantum NIZK with random oracle 11 Dominique Unruh

12. Invertible random oracle Random functions: not invertible Zhandry: RO 2?-wise indep. Function Idea: Use invertible 2?-wise indep. function Problem: None known Solution: Degree 2?polynomials Almost invertible (2? candidates) Good enough Quantum NIZK with random oracle 12 Dominique Unruh

13. Final result Theorem: If the sigma-protocol has: Honest verifier zero-knowledge Special soundness Then our protocol is: Zero-knowledge Simulation-sound online extractable Quantum NIZK with random oracle 13 Dominique Unruh

14. Further results Strongly unforgeable signatures (implied by the NIZK) New results for adaptive programming of quantum random oracle Invertible oracle trick (also used for variant of Fujisaki-Okamoto) Quantum NIZK with random oracle 14 Dominique Unruh

15. Saving Fiat-Shamir? |??? Superposition queries, as many as P wants H H ? ?? |? ??? P P ???? V V Zero-knowledge: yes (same as for our proto) Soundness: no [Ambainis Rosmanis U] Measuring ? ?? disturbs state Hope: Soundness if underlying sigma-protocol has strict soundness / unique responses Quantum NIZK with random oracle 15 Dominique Unruh

16. Strict soundness |??? Superposition queries, as many as P wants H H ? ?? |? ??? P P ???? V V Strict soundness: Given com, chall: at most one possible resp Helped before, for proofs of knowledge Measuring response not disturbing (much) Quantum NIZK with random oracle 16 Dominique Unruh

17. Saving Fiat-Shamir now? With strict soundness: no counterexample Proof still unclear (how to rewinding without disturbing quantum queries) Can be reduced to query-complexity problem Quantum NIZK with random oracle 17 Dominique Unruh

18. The query complexity problem Let ?? be a quantum circuit, using random oracle ?, implementing a projective measurement Game 1: State | , apply ?1 ??. Game 2: State | , apply ?1 ??, apply ?2 ??(?1 ??????). Show: Pr ?1= ?2 Game 2 Pr ?1 Game 1 poly(#???????) Quantum NIZK with random oracle 18 Dominique Unruh

19. I thank for your attention This research was supported by European Social Fund s Doctoral Studies and Internationalisation Programme DoRa Dominique Unruh