Cryptology ePrint Archive: Report 2009/448

Precise Bounded-Concurrent Zero-Knowledge in Almost Constant Rounds

Ning Ding and Dawu Gu and Bart Preneel

Abstract: Precise concurrent zero-knowledge is a new notion introduced by Pandey et al. \cite{P:P:M:T:V} in Eurocrypt'08 (which generalizes the work on precise zero-knowledge by Micali and Pass \cite{M:P} in STOC'06). This notion captures the idea that the view of any verifier in concurrent interaction can be reconstructed in the almost same time. \cite{P:P:M:T:V} constructed some (private-coin) concurrent zero-knowledge argument systems for $\NP$ which achieve precision in different levels and all these protocols use at least $\omega(\log n)$ rounds. In this paper we investigate the feasibility of reducing the round complexity and still keeping precision simultaneously. Our result is that we construct a public-coin precise bounded-concurrent zero-knowledge argument system for $\NP$ only using almost constant rounds, i.e., $\omega(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. We stress that this result cannot be obtained by \cite{P:P:M:T:V} even in bounded-concurrent setting.

Category / Keywords: foundations / Zero-Knowledge, Precise Zero-Knowledge, Concurrent Zero-Knowledge, Interactive Proofs and Arguments, Proofs of Knowledge

Publication Info: not published

Date: received 12 Sep 2009

Contact author: cs dingning at gmail com

Available formats: PDF | BibTeX Citation

Version: 20090914:012613 (All versions of this report)

Discussion forum: Show discussion | Start new discussion