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 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 the 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

Date: received 27 Aug 2019, last revised 3 Sep 2019

Contact author: zhenbiny at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20190903:153247 (All versions of this report)

Short URL: ia.cr/2019/977