Precise Bounded-Concurrent Zero-Knowledge in Almost Constant Rounds

Abstract

Precise concurrent zero-knowledge is a new notion introduced by Pandey et al. in Eurocrypt'08, which captures the idea that the view of any verifier in concurrent interaction can be reconstructed in almost the same time. They also constructed some (private-coin) concurrent zero-knowledge argument systems for NP which achieve precision in different levels and all these protocols use at least ω (log n) rounds. In this paper we investigate the feasibility of reducing the round complexity and still keeping precision simultaneously. Our main result is that we construct a public-coin precise bounded-concurrent zero-knowledge argument system for NP only using almost constant rounds, i.e., ω (1) rounds. Bounded-concurrency means an a-priori bound on the (polynomial) number of concurrent sessions is specified before the protocol is constructed. Our result doesn't need any setup assumption.