Minimal Assumptions and Round Complexity for Concurrent Zero-Knowledge in the Bare Public-Key Model

摘要

Under the (minimal) assumption of the existence of one-way functions, we show that every language in NP has (round-optimal) argument systems in the bare public key (BPK) model of [3], which are sound (i.e., a cheating prover cannot prove that x {not ∈} L) and (black-box) zero-knowledge (i.e., a cheating verifier does not obtain any additional information other than x ∈ L) even in the presence of concurrent attacks (i.e., even if the cheating prover or verifier are allowed to arbitrarily interleave several executions of the same protocol). This improves over the previous best result [12], which obtained such a protocol using a stronger assumption (the existence of one-way permutations) or a higher round complexity (5 messages), and is round-optimal among black-box zero-knowledge protocols. We also discuss various extensions and applications of our techniques with respect to protocols with different security and efficiency requirements.