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

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