NP问题的3轮零知识证明系统的存在性

摘要：

研究NP问题的3轮零知识证明的存在性. O. Goldreich与H. Krawczyk在1996年证明BBP以外的语言不存在(欺骗概率可忽略的)3轮黑箱模拟零知识协议, 但是否存在3轮非黑箱模拟零知识证明仍然是一个尚未解决的问题. 采用一种新的交互证明模式, 在标准的DDH假设下, 对图的3着色问题构造了一个3轮零知识证明. 由于对零知识性的证明采用了一种特殊的方法, 文中的协议实际上是非黑箱模拟意义下的零知识证明, 从而证明了在 DDH假设下, 所有的NP语言都有3轮零知识证明系统.

关键词：交互证明、零知识证明、非黑箱模拟、DDH假设

所属期刊栏目：37

分类号：TP3(计算技术、计算机技术)

资助基金：国家自然科学基金60573052;90304013

在线出版日期：2008-04-09（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：1521-1530