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

• 作者: 冯登国 徐海霞 李宝 李红达
• 来源期刊: 中国科学（信息科学）
• 关键词: 零知识证明 知识的证明 黑箱模拟 常数轮 密码学
• 年，卷（期）: 2012,（1）
• 所属期刊栏目: 论文
• 页码范围: 20-31
• 页数: 12页
• 语种: 中文

摘要

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