专栏首页包罗万想Tutorial of (zero-knowledge) proofs(2)

Tutorial of (zero-knowledge) proofs(2)

课程链接:https://www.bilibili.com/video/av66496040


Day-1 part A: Warmup

Day-1 part B: a concrete example

Day-2 part A: zk-proofs for discrete log

Day-2 part B: more advanced zk-proofs and applications

第一节 零知识证明和相关密码学基础

第二节 Schnorr协议和离散对数的知识证明

第三节 零知识证明:进阶主题

第四节 零知识证明:实际应用


第三节 零知识证明:进阶主题

Day-2 part A: zk-proofs for discrete log

Rewind,坐时光机器回到某个时间点。回到A和c1之间。拿到两个c和两个z,即可以算出w。

只是一种证明方法。实际上,prover不会对一个commitment的两次c返回两次z。

Proof-of-knowledge=knowledge sound

不能构建simulator,所以不能证明是零知识的。除非两种情况。

在这两种情况下,构建simulator,证明是零知识的。

思想,是算A。不需要知道a。

证明第一种情况下的零知识的。

C空间是短的。意味着在多项式时间内可以,如果c'!=c,就rewind回去。重复。这样的simulator就可以构建。

证明第二种情况下的零知识的。

限定verifier,选择challenge C 从伪随机。

看到c马上rewind,随机挑z把A算出来。

所以刚才的原始版本,确实不是零知识的。

有没有办法将Schnorr的协议转换为零知识?

是的,Fiat-Shamir转换可将Schnorr的协议转换为以hash为RO的零知识模型。

介绍hash和ro。跳过

fiat shamir转换。

变化就是第二步c,不是v发送给p。

此处的c不是v随机挑的。理解为V委托P把A扔给RO算出一个c。

v多验证一步A给RO返回的确实是c。

这是非交互式的证明。全是从左往右的,可以理解为一个消息。

先证零知识,构造simulator。

假设我有两个POK

P如何说服V 我既知道w1又知道w2。

显然,跑上面的协议两遍。

P不想让V知道我到底知道w1还是w2。但是证明给V,P知道这两个中的某一个。

构建一个simulator,让整个证明变成只有一个challenger。左边真的P证明P知道的某一个,simulator证明他不知道的那个。两个proof发给V,V无法区分哪个是真的。

具体协议如下,c1无法控制因为c是RO出来的,但c2是可以控制的。

分别check每个证明都是对的。

以上一直用到了commitment。讲一下具体的pedersen commitment。

问题(提示:使用sigma协议)

  • 如果一个人使用Pedersen承诺来提交值1,那么她如何在不透露承诺密钥的情况下证明承诺值是实际的1?
  • 如何证明承诺值是0或1?
  • 一个提交两个值v1和v2,如何证明它们是不同的,而不会泄漏其他任何内容?
  • 一个提交boolean门(或,与,否,异或)的所有输入和输出,如何证明提交的输入和输出满足门的约束而又不泄漏其他任何东西?

第四节 零知识证明:实际应用

Day-2 part B: more advanced zk-proofs and applications

假设一个银行,存在一个数据库,记录所有人的账户余额,所有人都可以看到它。

如何让坏人可以访问这个数据库,但是不能看到具体的账户余额。用commitment。

但是不能防止Alice只有100块却说自己有200块。(双花攻击)

我们需要一些称为机密交易的高级概念来增强使用承诺的天真的想法

每当客户花钱时,她应向银行证明自己不是重复消费:

r就是前面的w。Witness r。r就是我知道的。

显然,基于Schnorr的sigma协议和or-composition由于效率低下根本没有用。

例如,要证明在[0,2^32)中的承诺值。我们需要对or进行组合以计算2^32次Schnorr的协议实例

引入一个新的工具 zk-SNARK ,效率更高。

zero-knowledge Succinct Non-Interactive Argument of Knowledge ( zk-SNARK )零知识的简洁非交互式知识争论

基本知识。GCAC已学,跳过

V知道x0,P知道一个多项式。P要证明给V看,P确实知道这个多项式x0对应的值P(x0)。

第一步,随机挑两个点,s和b。多项式阶次是d。encode那些点。

P不知道s。这个Enc没办法Dec。Enc是加法同态的。

ai是多项式的系数,P知道。

V验证,算两个双线性对e。左右相等,没问题。

这不是零知识的。

以上主要是为了引出多项式的整除性。

第一个可以整除,第二个不可整除,余2。

整除性:n是分子,d是分母。做除法。只有商q没有余数。

p向v证明,n是可以由d整除的

不需要证明整个式子,只需要带入一个点可以整除就行。检查一个点左右相等了,就是可以整除。

左边是可以整除的例子,右边不可整除。

回到协议,如何证明整除。

第三步有两个check。

第一个check保证你真的evaluate 了一个多项式。

第二个保证了确实在s点处多项式左右相等。

QAP可以把任意的NP-language变成检查多项式整除问题。

SNARK很有用,一些应用:

匿名认证: 用户应证明自己具有有效的登录证书

可验证的计算: 云应证明其忠实地计算了定制程序

关于匿名登录的一个使用SNARK的例子。

左右两个任务1和2.

每个面具都是一个匿名身份,连接着一个真人。

有一个人又参加了1 又参加了2.

通过找交集可以找到这个人。更强的匿名性,无法找到这个人。

用户只能参加一个任务一次。匿名,不知道你登录了几次。

在一次任务里面登录第二次的时候,拒绝服务。

两个性质:

(Anonymity) The un-linkability cross tasks, for anyone (including the RA); (Accountability) The subtle linkability within the same task.

合法的,所有的verify都应该通过。

第一步注册。

第二步产生零知识证明,证明我确实注册过。

比较t是一样的就可以把登录两次的人找到。

Reference list

  • Eli Ben Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. 2014. Zerocash: Decentralized Anonymous Payments from Bitcoin. In Proceedings of the 2014 IEEE Symposium on Security and Privacy (SP ’14). IEEE Computer Society, Washington, DC, USA, 459-474.
  • Rosario Gennaro Craig Gentry Bryan Parno Mariana Raykova Quadratic span programs and succinct NIZKs without PCPs. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer Berlin Heidelberg, 2013.
  • Parno, B., Howell, J., Gentry, C., Raykova, M. (2013, May). Pinocchio: Nearly practical verifiable computation. In Security and Privacy (SP), 2013 IEEE Symposium on (pp. 238-252). IEEE.

本文分享自微信公众号 - 包罗万想(An-mind),作者:安包

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-01-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • GCAC79 19.1 Schnorr’s identification protocol

    Chapter 19 Identification and signatures from sigma protocols

    安包
  • GCAC48 用TDF构建SS的公钥加密方案(作业8答案)

    GCAC43 11.4 Encryption based on a trapdoor function scheme

    安包
  • Tutorial of (zero-knowledge) proofs(1)

    课程链接:https://www.bilibili.com/video/av66496040

    安包
  • Git 项目推荐 | javascript ajax 代理调用工具

    javascript ajax 代理调用工具 。 AjaxProxy url: /template/default/script/AjaxProxy.js; 接...

    码云Gitee
  • JUnit:别再用 main 方法测试了,好吗?

    你好呀,我是 JUnit,一个开源的 Java 单元测试框架。在了解我之前,先来了解一下什么是单元测试。单元测试,就是针对最小的功能单元编写测试代码。在 Jav...

    沉默王二
  • 元宵节专门为程序员设计的灯谜

    元宵节刚过,不过专家说:今年是15的月亮16圆,猿们,考研智商和技术知识面的时刻来了,看看下面的灯谜你能搞出几个来。

    后端技术探索
  • RS 纠删码为什么可以提高分布式存储可靠性?| 原力计划

    Erasure Code(EC),即纠删码,是一种前向错误纠正技术(Forward Error Correction,FEC,说明见后附录)。目前很多用在分布式...

    区块链大本营
  • Myexclipse创建Junit测试

    . 下载JUnit的jar文件,下载地址在这里 2. 在MyEclipse中新建一个要测试的项目HelloJUnit 3. 添加一个要测试的类HelloJ...

    xiangzhihong
  • WPF 给应用程序添加水印

    例如我有一个应用,我在主页面添加了功能页面,在功能页面的最上层需要一个水印,这个水印不能被用户点击到,例如我的功能页面是一个用户控件放在页面

    林德熙
  • 如何打造一个高效的研发团队

    互联网公司的成功很大一部分归结为人才储备,如何打造有活力、持续创新的研发团队,相信很多管理者都比较关心。

    用户7676729

扫码关注云+社区

领取腾讯云代金券