| NP问题的最优轮复杂性知识的零知识证明 |
| |
| 引用本文： | 李红达,冯登国,李宝,徐海霞.NP问题的最优轮复杂性知识的零知识证明[J].中国科学：信息科学,2012(1):20-31. |
| |
| 作者姓名： | 李红达 冯登国 李宝 徐海霞 |
| |
| 作者单位： | 信息安全国家重点实验室;中国科学院研究生院;中国科学院软件研究所 |
| |
| 基金项目： | 国家重点基础研究发展计划(批准号:2007CB311202,2007CB311201);国家自然科学基金(批准号:60970139)资助项目 |
| |
| 摘 要： | NP问题已有的知识的(黑箱)零知识证明都是非常数轮的,因此,在标准的复杂性假设下,NP问题是否存在常数轮的(黑箱)知识的零知识证明是一个有意义的问题.本文对该问题进行了研究,在一定的假设下给出了HC问题的两个常数轮知识的零知识证明系统.根据Katz最近的研究结果,在多项式分层不坍塌的条件下,本文基于claw-free陷门置换给出的HC问题的5轮知识的零知识证明系统具有最优的轮复杂性.
|
| 关 键 词： | 零知识证明 知识的证明 黑箱模拟 常数轮 密码学 |
Round-optimal zero-knowledge proofs of knowledge for NP |
| |
| Affiliation: | LI HongDa1,2,FENG DengGuo1,3,LI Bao1,2 & XUE HaiXia1,2 1 State Key Lab of Information Security,Beijing 100049,China;2 Graduate University of Chinese Academy of Sciences,Beijing 100049,China;3 Institute of software of Chinese Academy of Sciences,Beijing 100080,China |
| |
| Abstract: | It is well known that all the known black-box zero-knowledge proofs of knowledge for NP are nonconstant-round.Whether there exit constant-round black-box zero-knowledge proofs of knowledge for all NP languages under certain standard assumptions is an open problem.This paper focuses on the problem and gives a positive answer by presenting two constructions of constant-round(black-box) zero-knowledge proofs of knowledge for the HC(Hamiltonian cycle) problem.By the recent result of Katz,our second construction which relies on the existence of claw-free functions has optimal round complexity(5-round) assuming the polynomial hierarchy does not collapse. |
| |
| Keywords: | zero-knowledge proofs proofs of knowledge black-box simulation constant-round cryptography |
| 本文献已被 CNKI 等数据库收录！ |
|
