Statistical Concurrent Non-malleable Zero-Knowledge from One-Way Functions

Concurrent non-malleable zero-knowledge (CNMZK) protocols are zero-knowledge protocols that are secure even when the adversary interacts with multiple provers and verifiers simultaneously. Recently, the first statistical CNMZK argument for NP was constructed by Orlandi et al. (TCC'14) under 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). Under the existence of collision-resistant hash functions, the round complexity can be reduced to.(log n), which is essentially optimal for black-box concurrent zero-knowledge.