Round-optimal zero-knowledge proofs of knowledge for NP  

作　　者：LI HongDa FENG DengGuo LI Bao XUE HaiXia 

机构地区：[1]State Key Lab of Information Security,Graduate University of Chinese Academy of Sciences,Beijing 100049,China [2]State Key Lab of Information Security,Institute of software of Chinese Academy of Sciences,Beijing 100080,China

出　　处：《Science China(Information Sciences)》2012年第11期2473-2484,共12页中国科学（信息科学）（英文版）

基　　金：supported by National Basic Research Program of China (Grants Nos. 2007CB311202,2007CB311201);National Natural Science Foundation of China (Grant No. 60970139);National High-Tech Research & Development Plan of China (Grant No. 2006AA01Z427);Strategic Priority Program of Chinese Academy of Sciences (Grant No. XDA06010702)

摘　　要：It is well known that all the known black-box zero-knowledge proofs of knowledge for NP are non- constant-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.It is well known that all the known black-box zero-knowledge proofs of knowledge for NP are non- constant-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.

关 键 词：zero-knowledge proofs proofs of knowledge black-box simulation constant-round 

分 类 号：TP309[自动化与计算机技术—计算机系统结构] TP393.08[自动化与计算机技术—计算机科学与技术]