Round-optimal zero-knowledge proofs of knowledge for NP |
| |
Affiliation: | LI HongDa1,FENG DengGuo2,LI Bao1 & XUE HaiXia1 1State Key Lab of Information Security,Graduate University of Chinese Academy of Sciences,Beijing 100049,China;2State Key Lab of Information Security,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 |
本文献已被 CNKI 等数据库收录! |
|