文章基本信息

标题：Black-Box Concurrent Zero-Knowledge Requires (logn) Rounds
本地全文：下载
作者：Ran Canetti ; Joe Kilian ; Erez Petrank 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2001
卷号：2001
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We show that any concurrent zero-knowledge protocol for a non-trivial language (i.e., for a language outside \BPP ), whose security is proven via black-box simulation, must use at least ( log n ) rounds of interaction. This result achieves a substantial improvement over previous lower bounds, and is the first bound to rule out the possibility of constant-round concurrent zero-knowledge when proven via black-box simulation. Furthermore, the bound is polynomially related to the number of rounds in the best known concurrent zero-knowledge protocol for languages in \NP .
关键词：concurrent composition , zero-knowledge