International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Statistical Concurrent Non-Malleable Zero-Knowledge from One-Way Functions

Authors:
Susumu Kiyoshima
Download:
DOI: 10.1007/s00145-020-09348-x
Search ePrint
Search Google
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
}