NP问题的常数轮知识的零知识证明系统

作者：李红达; 徐海霞; 李宝; 冯登国

来源：中国科学:信息科学 , 2010, (09): 1197-1210.

• 零知识证明
• 知识的证明
• 常数轮
• NP关系

文中研究在标准复杂性假设下NP问题的常数轮知识的零知识证明系统的存在性问题.利用一种特殊的交互证明模式,在因子分解的困难性假设下,给出了NP问题的一个3轮的知识的零知识证明系统.文中给出的证明系统不仅肯定了NP问题的常数轮知识的零知识证明系统的存在性,同时也是对(NP问题的)3轮零知识证明系统的存在性这一公开问题的一个肯定性答复.

• 单位
  中国科学院研究生院; 信息安全国家重点实验室; 中国科学院软件研究所