Cryptology ePrint Archive: Report 2015/620

Statistical Concurrent Non-malleable Zero-knowledge from One-way Functions

Susumu Kiyoshima

Abstract: Concurrent non-malleable zero-knowledge (CNMZK) protocols are zero-knowledge protocols that provides security even when adversaries interacts with multiple provers and verifiers simultaneously. It is known that CNMZK arguments for NP can be constructed in the plain model. Furthermore, it was recently shown that statistical CNMZK arguments for NP can also be constructed in the plain model. However, although the former requires only the existence of one-way functions, the latter requires the DDH assumption.

In this paper, we construct a statistical CNMZK argument for NP assuming only the existence of one-way functions. The security is proven via black-box simulation, and the round complexity is poly(n). Furthermore, under the existence of collision-resistant hash functions, the round complexity is reduced to w(log n), which is essentially optimal for black-box concurrent zero-knowledge protocols.

Category / Keywords: foundations / concurrent non-malleable zero-knowledge, one-way function

Original Publication (with major differences): IACR-CRYPTO-2015

Date: received 22 Jun 2015, last revised 17 Dec 2015

Contact author: kiyoshima susumu at lab ntt co jp

Available format(s): PDF | BibTeX Citation

Note: Some typos are fixed.

Version: 20151218:011437 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]