zbMATH — the first resource for mathematics

Black-box concurrent zero-knowledge requires (almost) logarithmically many rounds. (English) Zbl 1037.94004
Informally, a zero-knowledge proof system is said to be concurrent zero-knowledge if it remains zero-knowledge even when executed in the concurrent setting, i.e. many protocols are executed at the same time. In such a setting standard techniques to demonstrate the zero-knowledge property of a protocol usually cannot be applied in a straightforward way. The difficulty of concurrent zero-knowledge can be illustrated e.g. by results on the lower bound on the round complexity of concurrent zero-knowledge. The best lower bound has been previously shown to be 7 rounds (via the so-called black-box simulation). The considerable gap between the known lower and upper bounds thus naturally leads to the question of whether there exist constant-round concurrent (black-box) zero-knowledge protocols.
In the paper it is shown that in the context of black-box concurrent zero-knowledge any protocol for a nontrivial language must use at least \(\Omega(\log n)\) rounds of interaction. Moreover, the bound is polynomially related to the number of rounds in the best-known concurrent zero-knowledge protocol for languages in NP (established via black-box simulation). Besides the detailed proof of the main result the authors also discuss alternative models and simulation techniques and known results in that direction.

94A60 Cryptography
68Q25 Analysis of algorithms and problem complexity
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
Full Text: DOI