Building Non-Interactive Zero-Knowledge Proofs without Interaction
Learn about Non-Interactive Zero-Knowledge (NIZK) proofs based on Computational Diffie-Hellman assumptions, exploring completeness, soundness, and zero-knowledge properties. Discover the main question of how to construct NIZKs and the prior work behind it, including public-key assumptions and cryptographic techniques like Random Oracles, Indistinguishability Obfuscation, Pairings, and more.
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
A Note on Non-Interactive Zero-Knowledge from CDH Geoffroy Couteau Abhishek Jain Zhengzhong Jin Willy Quach Universit Paris-Cit CNRS, IRIF John Hopkins University MIT Northeastern University Weizmann CRYPTO 2023
Non-Interactive Zero-Knowledge (NIZK) NP language ? Witness Statement ? ?,? Prover Verifier ? ?
Non-Interactive Zero-Knowledge (NIZK) NP language ? Witness Statement ? ?,? Prover Verifier ? accept/reject
Non-Interactive Zero-Knowledge (NIZK) NP language ? Witness Statement Completeness: verifier accepts if ? ? ? ?,? Prover Verifier ? accept
Non-Interactive Zero-Knowledge (NIZK) NP language ? Statement Completeness: verifier accepts if ? ? ? ? Computational Soundness: if ? ?, No efficient prover can make verifier accept Prover Verifier ? reject
Non-Interactive Zero-Knowledge (NIZK) NP language ? Witness Statement Completeness: verifier accepts if ? ? ??? ? ?,? Computational Soundness: if ? ?, No efficient prover can make verifier accept Prover Verifier ? Computational Zero-Knowledge: if ? ?, Efficient verifiers don t learn anything else
Non-Interactive Zero-Knowledge (NIZK) NP language ? Witness Statement Completeness: verifier accepts if ? ? ??? ? ?,? Computational Soundness: if ? ?, No efficient prover can make verifier accept Prover Verifier ? Computational Zero-Knowledge: if ? ?, Efficient verifiers don t learn anything else accept/reject Main question: How to build NIZKs, and under what assumptions?
Prior Work on Building NIZKs NP language ? Witness Statement ??? ?,? ? Main question: How to build NIZKs, and under what assumptions? Prover Verifier ? ? Public-Key Assumptions Random Oracles (heuristic) Indistinguishability Obfuscation (+ one-way funct.) Factoring and friends [Blum-Feldman-Micali88 ] Pairings [Canetti-Halevi-Katz03,Groth-Ostrovsky-Sahai06 ] Learning with Errors (LWE) [ Peikert-Shiehian19] Decisional Diffie-Hellman (DDH) [Jain-Jin21] [Fiat-Shamir86] [Sahai-Waters13] Open questions: Generic Public-Key Encryption? Computational Diffie-Hellman (CDH) Learning Parity with Noise (LPN)
Our Main Result Theorem (informal): Assuming the sub-exp. hardness of CDH*, NIZKs for all ?? there exist with weak soundness ZAP arguments ZAP: two-message, public-coin-verifier, witness-indistinguishable argument ) *With restrictions on ? (e.g. ?
Our Main Result Theorem (informal): Assuming the sub-exp. hardness of CDH*, NIZKs for all ?? there exist with weak soundness ZAP arguments infinitely-often( sub-exp. often ) Caveats: soundness only holds against uniform cheating provers More details: Common random string (a.k.a. uniform random string URS) Soundness: computational, adaptive Zero-knowledge: computational, adaptive, multi-theorem ZAP: two-message, public-coin-verifier, witness-indistinguishable argument ) *With restrictions on ? (e.g. ?
Diffie-Hellman Assumptions ? cyclic group of prime order ? generated by ? ? Computational Diffie-Hellman (CDH) Decisional Diffie-Hellman (DDH) Given ??,?? for random ?,? Hard to compute ??? Given ??,?? for random ?,? ??? ?uniform Less structured hardness More structured hardness Lossy trapdoor functions Additively homomorphic encryption 2-round single server PIR Somewhere-stat. binding hash functions ?
Prior Work on NIZKs + DH assumptions ? cyclic group of prime order ? generated by ? ? Computational Diffie-Hellman (CDH) Decisional Diffie-Hellman (DDH) Given ??,?? for random ?,? Hard to compute ??? Given ??,?? for random ?,? ??? ?uniform NIZKs from sub-exp. hardness of DDH* [Jain-Jin21] ) *With restrictions on ? (e.g. ?
Prior Work on NIZKs + DH assumptions ? cyclic group of prime order ? generated by ? ? Computational Diffie-Hellman (CDH) Decisional Diffie-Hellman (DDH) Given ??,?? for random ?,? Hard to compute ??? Given ??,?? for random ?,? ??? ?uniform Designated-Verifier NIZKs from CDH [Couteau-Hofheinz19, Q-Rothblum-Wichs19, Katsumata-Nisimaki-Yamada-Yamakawa19] Reduces to CDH + prove/decide DH tuples (??,??,???)// keyword: hidden-bits model Blueprint: Hash-proof systems [Cramer-Shoup02] DV-NIZK for DH tuples Prover proves to verifier validity of DH tuple using DV-NIZK DV-NIZK from CDH (Symmetric) Pairings: decide DH tuples over source group Verifier verifies himself DH tuple using pairing NIZK from CDH over source group with pairing [Canetti-Halevi-Katz03] DV-NIZK: Verifier is given a reusable but secret verification key from a trusted setup
Prior Work on NIZKs + DH assumptions ? cyclic group of prime order ? generated by ? ? Computational Diffie-Hellman (CDH) Given ??,?? for random ?,? Hard to compute ??? Designated-Verifier NIZKs from CDH [Couteau-Hofheinz19, Q-Rothblum-Wichs19, Katsumata-Nisimaki-Yamada-Yamakawa19] Reduces to CDH + prove/decide DH tuples (??,??,???) Blueprint: // keyword: hidden-bits model Hash-proof systems [Cramer-Shoup02] DV-NIZK for DH tuples Prover proves to verifier validity of DH tuple using DV-NIZK DV-NIZK from CDH Pairings: decide DH tuples over source group Verifier verifies himself DH tuple using pairing NIZK from CDH over source group with pairing [Canetti-Halevi-Katz03] DDH broken NIZK from CDH! DV-NIZK: Verifier is given a reusable but secret verification key from a trusted setup
A Disjunction Argument ? cyclic group* of prime order ? generated by ? ? such that CDH holds over ? OR DDH broken NIZK from CDH! DDH secure* NIZK (from DDH!) Conclusion: NIZK from CDH*? NO: broken not secure ) *With restrictions on ? (e.g. ?
Mismatches Broken Not Secure DDH broken NIZK from CDH! DDH not secure (no NIZK from DDH) Break with sub-exp. small advantage Need break with very high success rate
Mismatches Broken Not Secure DDH broken NIZK from CDH! DDH not secure (no NIZK from DDH) Break with sub-exp. small advantage Need break with very high success rate Need break on arbitrary inputs (??,??,??) Break on random inputs (??,??,??)
Mismatches Broken Not Secure DDH broken NIZK from CDH! DDH not secure (no NIZK from DDH) Break with sub-exp. small advantage Need break with very high success rate Need break on arbitrary inputs (??,??,??) Break on random inputs (??,??,??) Break is non-uniform, non-explicit Honest verifier runs the break
Mismatches Broken Not Secure DDH broken NIZK from CDH! DDH not secure (no NIZK from DDH) Fix: Break with sub-exp. small advantage Need break with very high success rate Amplification (sub-exp.) via Random Self-reducibility Need break on arbitrary inputs (??,??,??) Break on random inputs (??,??,??) Break is non-uniform, non-explicit Honest verifier runs the break Need break to work for (almost) all security parameters Break only works for infinitely-many security parameters
Mismatches Broken Not Secure DDH broken NIZK from CDH! DDH not secure (no NIZK from DDH) Fix: Break with sub-exp. small advantage Need break with very high success rate Amplification (sub-exp.) via Random Self-reducibility Need break on arbitrary inputs (??,??,??) Break on random inputs (??,??,??) Break is non-uniform, non-explicit Honest verifier runs the break Sources of Caveats Need break to work for (almost) all security parameters Break only works for infinitely-many security parameters
A Disjunction Argument ? cyclic group* of prime order ? generated by ? ? such that CDH holds over ? OR DDH broken NIZK from CDH! DDH secure* NIZK (from DDH!) Side Result 1: NIZK from sub-exp. CDH* with non-uniform, non-explicit verifier and infinitely-often sound // soundness against non-uniform provers ) *With restrictions on ? (e.g. ?
Variants of the Disjunction Argument (1) ? cyclic group of prime order ? generated by ? ? such that CDH holds over ? DDH and LPN [Brakerski -Koppula -Mour20] OR secure NIZK DDH broken NIZK from CDH! Side Result 2: NIZK from polynomialCDH + LPN with non-uniform, non-explicit verifier and infinitely-often sound // no restrictions on ?! Curiosity: can show that either CDH implies NIZKs or LPN implies NIZK with caveats
Variants of the Disjunction Argument (2) ? cyclic group* of prime order ? generated by ? ? such that CDH holds over ? OR DDH broken ZAP from CDH! DDH secure* ZAP arguments Stat. sound, URS + [Dwork-Naor00] [Jain-Jin21] Side Result 3: ZAP arguments from sub-exp. CDH* with non-uniform, non-explicit verifier and infinitely-often sound ZAP args: 2-message, public-coin-verifier, witness-ind. args. ) *With restrictions on ? (e.g. ?
A Better Disjunction Argument DDH secure* NIZK (1) Verifier is non-uniform (2) Verifier is non-explicit (3) Soundness only holds inf. often OR Current caveats: DDH broken NIZK from CDH! Standard drawbacks of disjunction arguments Use DDH-secure NIZK Use DDH-broken NIZK Identify secure security parameters Find explicitbreaks on insecure sec. params. Refined approach: New goal: build an explicit universal DDH breaker Specifications (informal): on input a security parameter: 1. Find an efficient break if one exists 2. Ensure that no break exist if it doesn t find any
A Universal Breaker for DDH (1) DDH secure* NIZK New goal: build an explicit universal DDH breaker OR Specifications (informal): on input a security parameter: 1. Find an efficient break if one exists 2. Ensure that no break exist if it doesn t find any DDH broken NIZK from CDH! Fixes: Main issues: 1. Standard DDH is non-uniform breaks are non-uniform Unclear how to ``test non-uniform machines efficiently 2. Security on fixed sec. param. is a non-uniform notion For a fixed security parameter, size of Turing machine advice 3. Poly-time doesn t make sense for fixed sec. param. // Replace by uniform DDH Cost: uniform soundness // Bound size of Turing machine // Use (?,?)-security for sub-exp. ?, inverse sub-exp. ?
A Universal Breaker for DDH (2) DDH secure* NIZK New goal: build an explicit universal DDH breaker OR Specifications (informal): on input a security parameter: 1. Finds an efficient break if one exists 2. Ensures that no break exist if it doesn t find any DDH broken NIZK from CDH! Our notion of security (for DDH): given sec. par. ?, no attacks with: Attack is a (uniform) Turing machine of size log ? Running time ?(?), advantage ?(?) ?: sub-exp. ?: inverse sub-exp.
A Universal Breaker for DDH (2) DDH secure* NIZK (uniform soundness) New goal: build an explicit universal DDH breaker OR Specifications (informal): on input a security parameter: 1. Finds an efficient break if one exists 2. Ensures that no break exist if it doesn t find any DDH broken NIZK from CDH! Our notion of security (for DDH): given sec. par. ?, no attacks with: Attack is a (uniform) Turing machine of size log ? Running time ?(?), advantage ?(?) ?: sub-exp. ?: inverse sub-exp. Our construction: test all TMs of size log ? sufficiently many times (given ?,?) // run-time ?/? = sub-exponential // correctness by Chernoff bounds
NIZKs from Universal Breakers DDH secure* NIZK (uniform soundness) ?????????(1?): on input a security parameter ?: 1. Finds an efficient break if one exists 2. Ensures that no break exist if it doesn t find any stat. ZK OR NP language ? Witness Statement DDH broken NIZK from CDH! ??? ?,? ? Prover Verifier DDH-secure NIZK ? Run ????????? If ?is secure then verify the DDH-secure proof Otherwise verify the DDH-broken proof using ????????? DDH-broken NIZK ? Verifier is uniform and explicit Now always sound, but not arbitrarily sparse: ?????????runs in sub-exp. time ( ?/?2) Need complexity leveraging NIZK is sub-exp. often sound : ?, sound parameter in [?,2??]
Our Main Result Theorem (informal): Assuming the sub-exp. hardness of CDH*, NIZKs for all ?? there exist with weak soundness *With restrictions on ? (e.g. ? ZAP arguments ) ?, sound parameter in [?,2??] sub-exponentially often Caveats: soundness only holds against uniform cheating provers Main Techniques: Open Questions: Standard NIZKs from CDH? NIZKs from public-key encryption? (Hard) Other disjunction arguments? More crypto from CDH over pairings? DDH secure* NIZK (from DDH!) Disjunction argument: DDH broken NIZK from CDH! Universal breaker: uniform, explicit algs, dense params. Thanks Eysa for the drawings! Thanks! General tool for disjunction arguments!
