本文介绍: ZK-Learning MOOC 课程笔记Lecture 11: From Practice to Theory (Guest Lecturer: Alex Lombardi)

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

      x

      x and a first message

      α

      alpha

      α, a challenge

      β

      beta

      β is “bad” if there exists a prover message

      g

      a

      m

      m

      a

      gamma

      gamma making

      V

      V

      V accept

    • We want to say: if the (3 message) interactive protocol is sound, then (for all

      x

      x

      x,

      α

      alpha

      α) most

      β

      beta

      β are not bad. True for statistically sound IPs.

    • Exactly what CI is good for! Define relation

      R

      x

      =

      α

      ,

      β

      :

      β

      i

      s

      b

      a

      d

      R_x = {alpha, beta: beta is bad}

      Rx=α,β:βisbad. Then if

      h

      h

      h is CI for

      R

      x

      R_x

      Rx (when

      x

      L

      x notin L

      x/L),

      Π

      F

      S

      Pi_{FS}

      ΠFS is sound using

      h

      h

      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

        R

        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]: noninteractive 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?

原文地址:https://blog.csdn.net/weixin_45347752/article/details/134617886

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。

如若转载,请注明出处:http://www.7code.cn/show_918.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注