Cryptology ePrint Archive: Report 2020/347

Some Low Round Zero Knowledge Protocols

Hongda Li and Peifang Ni and Dongxue Pan

Abstract: The efficiency of zero-knowledge protocols is measured by the round complexity. The construction of low round zero-knowledge protocols for any NP language has been a classical and open question.

In this paper, we focus on zero-knowledge protocols for NP with low round complexity under the augmented black-box simulation technique, in which the simulator has access to the verifier's secret information, and obtain positive results on 3-round zero-knowledge proofs and 2-round zero-knowledge arguments and proofs. More precisely, our contributions are five-fold: (i) we propose the notion of generalized claw-free function and the notion of trapdoor generalized claw-free function, and then we show a construction of trapdoor generalized claw-free function under the discrete logarithm assumption and the knowledge of exponent assumption, (ii) we propose the notion of completely extractable bit-commitment and give a construction of it from trapdoor generalized claw-free functions, (iii) we present a 3-round zero-knowledge proof for NP based on the completely extractable bit-commitment schemes and Yao's garbling circuit technique, (iv) we show a 2-round zero-knowledge argument for NP based on indistinguishable obfuscator, (v) we transform the basic 2-round honest verifier zero-knowledge proof protocol for quadratic non-residue into a 2-round zero-knowledge proof protocol.

Category / Keywords: cryptographic protocols / zero-knowledge, claw-free functions, augmented black-box simulation, parallel repetition, high efficiency

Date: received 23 Mar 2020

Contact author: lihongda at iie ac cn,nipeifang@iie ac cn

Available format(s): PDF | BibTeX Citation

Version: 20200326:074541 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]