数学联邦政治世界观
超小超大

零知识证明【非交互知识论证】二 (3-1)

要研究密码学,必须对复杂度类(complexity class)有一定的了解。在后续的内容中,将会多次出现“多项式时间(polynomial time),”对数空间(logarithmic space)”,“常数深度(constant depth)”等概念,这些概念用来定义我们所探讨的计算问题的类型,计算模型,需要约束的计算资源等。另外还有两个主要的基本复杂度类,P与NP,相关材料很多,这里不展开讨论了。

首先我们还是重复一下什么是NP类,NP类包含了所有可以由一个无限制(unbounded)的prover计算出确定性证明(deterministic proofs)的语言。这里生成的proof可以被视为一个多项式长度的字符串。交互证明(interactive proof)在两个方面放松了上述的条件:首先,prover和verifier可以使用随机币(public coins),即可以在交互过程中加入随机性;其次,验证proof的输出只需要以足够合理的概率与statement的实际真相一致;最后,显然各方之间是可以进行交互的。

在1985年,在两篇独立论文中,Babai[1]和Goldwasser, Micali, and Rackoff[2]引入了interactive proofs,也被称为Arthui-Merlin proofs的概念,这两篇论文获得了Gödel奖,这是理论计算机界最高的奖项之一。两篇论文都谈论了复杂度类,其中计算能力无限的prover必须通过多次交互说服多项式计算能力的verifier一个statement的真实性。这两篇论文的主要区别在于对verifier的random coins的使用上,在[1]中,verifier必须想prover展示其在计算过程中使用的所有random coins。这样的interactive proofs被称为public coin interactive proofs。而[2]中正相反,verifier不需要展示其内部的计算状态,这种被称为private coin interactive proofs。和public coin interactive proofs相关的复杂度类被Babai表示为AM[f(n)] ,AM代表Arthur-Merlin, n 代表输入的长度, f(n) 代表允许的交互轮数。和private coin interactive proofs相关的复杂度类被Goldwasser, Micali, and Rackoff表示为 lP[f(n)] 。

数学联邦政治世界观提示您:看后求收藏(同人小说网http://tongren.me),接着再看更方便。

相关小说

羊羊影视厅 连载中
羊羊影视厅
燃宝儿好困
主要是发一些图片,大家尽情期待吧(作者是一位六年级的小学生有可能会,因为学习耽误更新,请你们谅解)
2.0万字4个月前
狼王孤夜之永远的狼王 连载中
狼王孤夜之永远的狼王
狼王遗梦
成为狼王后的他又会经历怎样的难关呢?
6.7万字4个月前
走出来的小故事 连载中
走出来的小故事
莱歌儿
玄幻
15.0万字4个月前
魔法世界林意嘉 连载中
魔法世界林意嘉
姜姜J
新书第一!我的神兽大本营上市了,绝对比这本好看!欢迎大家,谢谢支持~本书介绍:40多集的时候我写得可能有些草率——一定要坚持看下去啊!!!后......
10.5万字4个月前
落雪卿言 连载中
落雪卿言
司慕芸
“我的世界下了一场大雪,连同她的体温,也一起带走了。”
7.5万字4个月前
虐文女主拯救计划 连载中
虐文女主拯救计划
孜颜
【快穿流,女强】万千世界无奇不有,虐文更是层出不穷;而子桑颜的任务就是改变原本虐文女主的悲惨命运,不再受男主的影响。————9527号本以为......
7.0万字4个月前