×

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.

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