CryptoDB
Statistical Concurrent Non-Malleable Zero-Knowledge from One-Way Functions
| Authors: | |
|---|---|
| Download: | |
| Abstract: | Concurrent non-malleable zero-knowledge ( $$\mathrm {CNMZK}$$ CNMZK ) protocols are zero-knowledge protocols that provides security even when adversaries interact with multiple provers and verifiers simultaneously. It is known that $$\mathrm {CNMZK}$$ CNMZK arguments for $$\mathcal {NP}$$ NP can be constructed in the plain model. Furthermore, it was recently shown that statistical $$\mathrm {CNMZK}$$ CNMZK arguments for $$\mathcal {NP}$$ 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 $$\mathrm {CNMZK}$$ CNMZK argument for $$\mathcal {NP}$$ NP assuming only the existence of one-way functions. The security is proven via black-box simulation, and the round complexity is $$\mathsf {poly}(n)$$ poly ( n ) . Under the existence of collision-resistant hash functions, the round complexity is reduced to $$\omega (\log n)$$ ω ( log n ) , which is essentially optimal for black-box concurrent zero-knowledge protocols. |
BibTeX
@article{jofc-2020-30755,
title={Statistical Concurrent Non-Malleable Zero-Knowledge from One-Way Functions},
journal={Journal of Cryptology},
publisher={Springer},
volume={33},
pages={1318-1361},
doi={10.1007/s00145-020-09348-x},
author={Susumu Kiyoshima},
year=2020
}