Paper 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.

Note: Some typos are fixed.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in CRYPTO 2015
Keywords
concurrent non-malleable zero-knowledgeone-way function
Contact author(s)
kiyoshima susumu @ lab ntt co jp
History
2015-12-18: last of 2 revisions
2015-06-30: received
See all versions
Short URL
https://ia.cr/2015/620
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/620,
      author = {Susumu Kiyoshima},
      title = {Statistical Concurrent Non-malleable Zero-knowledge from One-way Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2015/620},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/620}},
      url = {https://eprint.iacr.org/2015/620}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.