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
-
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},
url = {https://eprint.iacr.org/2015/620}
}
