NP问题的最优轮复杂性知识的零知识证明

摘要：

NP问题已有的知识的(黑箱)零知识证明都是非常数轮的,因此,在标准的复杂性假设下,NP问题是否存在常数轮的(黑箱)知识的零知识证明是一个有意义的问题.本文对该问题进行了研究,在一定的假设下给出了HC问题的两个常数轮知识的零知识证明系统.根据Katz最近的研究结果,在多项式分层不坍塌的条件下,本文基于claw-free陷门置换给出的HC问题的5轮知识的零知识证明系统具有最优的轮复杂性.

关键词：零知识证明、知识的证明、黑箱模拟、常数轮、密码学

所属期刊栏目：42

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

资助基金：国家重点基础研究发展计划（973计划）;国家自然科学基金

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

页码：20-31