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 are secure even against adversaries that interact with multiple provers and verifiers simultaneously. Recently, the first statistical CNMZK argument for NP was constructed under the DDH assumption (Orlandi el al., TCC'14).

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). Under the existence of collision-resistant hash functions, the round complexity can be reduced to w(log n), which is known to be 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 29 Jun 2015

Contact author: kiyoshima susumu at lab ntt co jp

Available format(s): PDF | BibTeX Citation

Version: 20150630:183221 (All versions of this report)

Short URL: ia.cr/2015/620

Discussion forum: Show discussion | Start new discussion