http://www.7klian.com

亚瑟王的「随机」挑战:从交互到非交互式零常识证明

· 第二步:Zlice 将 c 与 (m, R’) 写入精灵的表格。

这里为了担保进攻者不能随意伪造签名,正是操作了离散对数困难(DLP)与 Hash 函数满意抗第二原象(Secondary Preimage Resistance )这个假设。
世界,「NIZK」可以作为共鸣协议的一部门。因为一个生意业务需要多个矿工举办校验。设想下,假如生意业务的发送者和每个矿工都要交互一下,让矿工举办挑战,那么共鸣进程将奇慢无比。而非交互式零常识证明则可以直接广播给所有的矿工节点,让他们自行验证。
前文提到,失去了挑战,好像失去了
证明的「信任根本」。而在 Schnorr 签名方案中,Hash 函数担负起了「挑战者」的脚色,这个脚色有一个很是学术的名字:「随机预言机」(Random Oracle)[6]。
· 你如何区分 X 和 Y ,孰真孰假?虽然你无法区分,因为协议是零常识的,你必需不能区分
而『系列三』中,我们阐明白 Schnorr 协议,协议中固然验证者 Bob 只需要挑选一个
随机数 c 来挑战 Alice ,让她计较一个值 z,但 Bob 绝对不能让 Alice 有本领来预测到 c 的任何常识,不然,Alice 也会变身成模仿器。
通过绑架「精灵」,Zlice 同样可以提前预知随机数,这和时间倒流能到达同样的结果。
· Hash 函数计较的功效并不是一个真正具有一致性漫衍的随机数

前面提到,在非交互式证明系统中,需要引入一个第三方来构建信任的「根本」,使得 Bob 可以完全相信由 Alice 所结构的证明。在这里,第三方就是谁人「精灵」,用学术黑话就是「随机预言」(Random Oracle)。这个精灵并不是一个真实存在的第三方,而是一个虚拟的第三方,它同时存在于「现实世界」与「抱负世界」。在「现实世界」中,精灵是一个认真任的宁静玉人子,而在「抱负世界」中,它会被「模仿器」绑架。
NIZK 不只可以超过空间,还能超过时间
· 我可以同样可以把 Y 出示给你看,那岂不是「我」就可以欺骗你了吗?
· 随机预言机每次对付新字符串返回的是一个具有一致性漫衍的「真」随机数
因为这个假设无法被证明,所以我们只能信任这个假设,可能说当做一个正义来用。插一句, Hash 函数的广义抗碰撞性质抉择了它的输出可以模仿随机数,同时在许多环境下(并非所有),对 Hash 函数实施进攻难度很高,于是很多的暗码学家都在斗胆利用。

· 第三步:Zlice 将签名 (c, z) 发送给 Bob。

我们已经证明白模仿器 Zlice 的「存在性」,于是我们上面已经证明白 NIZK。
但是这里为何用 Hash?实际上当 Alice 要发生民众随机数时,需要一个叫做「随机预言机」的玩意儿,这是什么?
话说在1985年,当 GMR 三人的论文历经多次被拒之后终于被 STOC’85 接管,另一篇雷同的事情也同时被 STOC’85 接管,这就是来自于匈牙利罗兰大学的 László Babai,与来自以色列理工的 Shlomo Moran 两人撰写的论文『Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes』[7],引入了 Public-coin
交互式协议(顾名思义,Verifier 只果真抛硬币)。
注:NP 类 是 PSPACE 类的子集,前者各人较量熟悉,后者关联游戏可能下棋中的制胜计策[13]。
我们设想在「现实世界」中,天上有一位「精灵」,他手持一个双栏表格,左边一栏为字符串,右边一栏为数字。任何人,包罗你我,包罗 Alice 和 Bob,都可以发字符串给「精灵」。

大概各人此刻已经猜出来了,模仿器要在「随机预言机」上动手脚。
而在归并 Schnorr 协议进程中,其实我们需要的是一个这样的随机预言精灵,而不是一个 Hash 函数。两者有什么差异的处所?区别就是:

那么为什么前面用的是 Hash 函数呢?这是因为在现实世界中,真正的随机预言机不存在!为什么呢?事实上,一个 Hash 函数不行能发生真的随机数,因为 Hash 函数是一个「确定性」算法,除了参数以外,再没有其它随机量被引入。

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。