Cryptology ePrint Archive: Report 2019/977

Non-malleable Zero-Knowledge Arguments with Lower Round Complexity

Zhenbin Yan and Yi Deng

Abstract: Round complexity is one of the fundamental problems in zero-knowledge proof systems. Non-malleable zero-knowledge (NMZK) protocols are zero-knowledge protocols that provide security even when man-in-the-middle adversaries interact with a prover and a verifier simultaneously. It is known that the first constant-round public-coin NMZK Arguments for NP can be constructed by assuming the existence of collision-resistant hash functions (Pass and Rosen STOC'05) and has relatively high round complexity; the first four-round private-coin NMZK Arguments for NP can be constructed in the plain model by assuming the existence of one-way functions (Goyal, Richelson, Rosen and Vald FOCS'14 and Ciampi, Ostrovsky, Siniscalchi and Visconti TCC'17).

In this paper, we present a six-round public-coin NMZK argument of knowledge system assuming the existence of collision-resistant hash functions and a three-round private-coin NMZK argument system from multi-collision resistance of hash functions assumption in the keyless setting.

Category / Keywords: cryptographic protocols / Zero-Knowledge, Non-Malleable, Multi-Collision Resistance, Computational Complexity

Original Publication (with minor differences): The Computer Journal
DOI: 10.1093/comjnl/bxaa076

Date: received 27 Aug 2019, last revised 12 Jul 2020

Contact author: yanzhenbin at iie ac cn

Available format(s): PDF | BibTeX Citation

Version: 20200712:105656 (All versions of this report)

Short URL: ia.cr/2019/977