ZKP11.4 Use CI to instantiate Fiat-Shamir

ZKP学习笔记

ZK-Learning MOOC课程笔记

Lecture 11: From Practice to Theory (Guest Lecturer: Alex Lombardi)

11.4 Use CI to instantiate Fiat-Shamir

• Avoid Bad Challenges
  

  • Def: Given false claim $x$ and a first message $\alpha$, a challenge $\beta$ is “bad” if there exists a prover message $gamma$ making $V$ accept
  • We want to say: if the (3 message) interactive protocol is sound, then (for all $x$, $\alpha$) most $\beta$ are not bad. True for statistically sound IPs.
  • Exactly what CI is good for! Define relation $R_x=\alpha ,\beta :\beta isbad$. Then if $h$ is CI for $R_x$ (when $x\notin L$), ${\Pi }_{FS}$ is sound using $h$!
  • Protocols with more than 3 messages: round-by-round soundness (each round has a type of “bad challenge” to avoid).
  • Main technical challenges:
    • Sometimes our IP doesn’t have statistical soundness.
    • We can only build CI for relations $R$ that can be decided efficiently

• Important example: SNARGs via IOPs (PCPs)

  • SNARGs from PCPs [Kilian, Micali]
    

    • Candidate SNARG: apply Fiat-Shamir to this protocol!
    • Simplified (less efficient) version of modern SNARKs you’ve learned about.
    • Not statistically sound, so it’s not clear how to analyze FS without random oracles.

  • SNARGs for Batch NP
    

  • Interactive Batch Arguments from PCPs [CJJ21]
    

    • SSB Commitments
      

    • Interactive Batch Arguments from PCPs [CJJ21]
      
      

• Summary of Fiat-Shamir without RO

  • Use hash functions that are CI for appropriate functions/relations
    • [CCHLRRW19,PS19,BKM20,JJ21,HLR21]
  • Carefully show that FS-soundness for protocols of interest follows from compatible forms of CI
    • [CCHLRRW19]: (non-succinct) NIZK
    • [JKKZ21]: non-interactive sumcheck protocol
    • [CJJ21]: batch NP arguments
  • Open problems:
    • Characterize which protocols can be FS-compiled (we know it doesn’t work in general [Bar01, GK03])
    • SNARGs for NP from falsifiable assumptions?