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

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

来源：中国科学:信息科学 , 2012, (01): 20-31.

• 零知识证明
• 知识的证明
• 黑箱模拟
• 常数轮
• 密码学 zero-knowledge proofs
• proofs of knowledge
• black-box simulation
• constant-round
• cryptography

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

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