×

The knowledge tightness of parallel zero-knowledge. (English) Zbl 1296.94102

Cramer, Ronald (ed.), Theory of cryptography. 9th theory of cryptography conference, TCC 2012, Taormina, Sicily, Italy, March 19–21, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-28913-2/pbk). Lecture Notes in Computer Science 7194, 512-529 (2012).
Summary: We investigate the concrete security of black-box zero-knowledge protocols when composed in parallel. As our main result, we give essentially tight upper and lower bounds (up to logarithmic factors in the security parameter) on the following measure of security (closely related to knowledge tightness): the number of queries made by black-box simulators when zero-knowledge protocols are composed in parallel. As a function of the number of parallel sessions, \(k\), and the round complexity of the protocol, \(m\), the bound is roughly \(k ^{1/m }\).
We also construct a modular procedure to amplify simulator-query lower bounds (as above), to generic lower bounds in the black-box concurrent zero-knowledge setting. As a demonstration of our techniques, we give a self-contained proof of the \(o(\log n /\log \log n)\) lower bound for the round complexity of black-box concurrent zero-knowledge protocols, first shown by Canetti, Kilian, Petrank and Rosen (STOC 2002). Additionally, we give a new lower bound regarding constant-round black-box concurrent zero-knowledge protocols: the running time of the black-box simulator must be at least \(n ^{\Omega (\log n)}\).
For the entire collection see [Zbl 1238.94002].

MSC:

94A60 Cryptography
68M12 Network protocols
68P25 Data encryption (aspects in computer science)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI