查看原文
其他

零知识证明与多方安全计算之间是什么关系?

Gee Law 隐私计算研习社 2023-04-07



在隐私计算技术中,多方安全计算和零知识证明是两大主流研究内容,二者都能作为保护数据安全的方法,那小伙伴们有没有想过他们之间有什么关系?如果你对本文的解释有不一样的看法,欢迎在推文下方留言一起讨论!
1

问题
零知识证明与多方安全计算之间是什么关系,两者之间是不是可以基本划等号?

2


回答

精神上有类似的地方,但形式化上有很多差别——这些差别既重要,又是某种“小烦恼”。

从安全性角度考虑,零知识证明天然考虑如何抵御主动使坏者(严谨/sound、零知识),而安全计算的安全性里抵御被动和主动的使坏者都算是天然的目标。

从功能角度考虑,证明系统可以看作间隙问题 (gap problem) 的保持完整性 (integrity) 的安全(含间隙)计算。回顾证明系统的完备性、严谨性的定义。

  • 完备性. 若验证者的输入答案是 Yes,证明者的输入是验证者的输入以及该实例的证据,且双方遵守协议,则验证者输出 1。

  • 严谨性. 若验证者的输入答案是 No,则对任意扮演证明者的使坏者(根据定义不同,可能是任意强度的使坏者或者只针对高效使坏者),验证者输出 1 的概率都是可忽略函数。


这两条要求没有说,验证者的输入答案是 Yes,但证明者的输入乱七八糟的时候,验证者的行为。这便是所谓间隙 (gap) 的来源,考虑“含间隙的验证函数”


可以认为证明系统是在“安全计算”,但证明系统只要求:若 ,则正常执行结果是 1(安全计算的完备性刻画了证明系统的完备性);若 则任意(证明者非正常)执行结果必须是 0(即我所谓安全计算的完整性,这刻画了证明系统的严谨性);其他情况无论是证明者是正常还是非正常,执行结果都没有任何要求(即所谓的间隙,是对正常执行下计算正确性的弱化)。此外,没有考虑零知识的时候证明系统不需要让输入保密(所以只需要完整性而不需要隐私)。


考虑安全计算的主动安全性(某种意义上可以认为是同时考虑了完整性和隐私)对该证明系统性质的刻画。


  • 当证明者使坏时,我们要求计算结果必须等同于证明者选择了一个输入或者计算过程中止 (abort),考虑验证者输入的两种情况:如果验证者的输入答案是 No,则输出和证明者选择的输入无关(或者计算过程中止),此时安全计算的主动安全性刻画了严谨性;如果验证者的输入答案是 Yes,那么计算过程中止,或者等同于证明者选择了一个输入,此时 因此安全计算的主动安全性(基本上)没有产生额外的要求(零知识证明也没有提出任何要求)。实际上这比零知识证明的要求严格一些,因为零知识证明只考虑 的情况并且不考虑 的保密。


  • 当验证者使坏时,我们要求计算结果必须等同于验证者选择了一个输入或者计算过程中止,考虑不中止的情况,无论 或  或 ,主动安全性(隐藏输入)对证明者的保护表明 的信息不存在于使坏者的视野中(即刻画了零知识性质),这实际上比零知识证明的条件要严格一些(因为零知识性质里只考虑 的情况;但更严格的部分没有什么用)。


总结:

  • 安全计算的正确性(的含间隙的弱化)基本上对应完备性。

  • 针对使坏证明者的主动安全性里的完整性基本上对应严谨性。

  • 针对使坏验证者的主动安全性里的隐私性基本上对应零知识性质。


大体来说,可以把零知识证明想成是主动安全的、含间隙地计算“含间隙的验证函数”的安全计算。



作者知乎:Gee Law

原文链接:

https://www.zhihu.com/question/566991261/answer/2763264981

如果小伙伴们对于上面的问题有自己的见解或者想要提出一些新的问题,欢迎在下方进行留言,也许对这个问题一头雾水的你和大家一起讨论后就变得清晰通透~



END

往期推荐


1.基于密码的数据安全防护体系研究
2.学术交流 | InForSec 2023年网络空间安全国际学术研究成果分享及青年学者论坛3.首次发现!数据异构影响联邦学习模型,关键在于表征维度坍缩 | ICLR 20234.隐私求交| Simple, Fast Malicious Multiparty Private Set Intersection
欢迎投稿邮箱:pet@openmpc.com参与更多讨论,请添加小编微信加入交流群

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存