Adaptive zero knowledge and computational equivocation (extended abstract)
Adaptive zero knowledge and computational equivocation (extended abstract)
复制标题
DOI：
10.1145/237814.238014
复制
发表时间：
1996-07
期刊：
影响因子：
--
通讯作者：
Donald Beaver
中科院分区：
文献类型：
--
作者：
Donald Beaver
[GMW86] 的开创性工作提出使用零知识证明系统（ZKPS）作为证明遵守指定网络协议的手段，从而保护交互式网络计算免受恶意子版本的侵害。每个参与者都会在不透露任何额外信息的情况下证明自己确实遵守了规则。我们提供的证据表明，经典的零知识分析 [GMR89] 和 [GM W86] 中的特定 ZKPS 都不足以提供可证明的安全性，以抵御自适应恶意对手的攻击，如下所示。如果 [GMW86] 中提出的图 3 着色性的 ZKPS 被证明是安全的，可以防止对手随着协议的进展而选择破坏谁，并且如果分解是棘手的，那么多项式层次结构就会崩溃。特别是，NP 中的任何语言都可以通过访问 Oracle 进行因式分解来解决。我们还考虑了经典 ZKPS 未解决的微妙要求，例如验证者的隐私，并表明某些 ZKPS 可能允许微妙的攻击，其中有用的知识被泄漏而无法检测。为了解决这些问题，我们提出了一种用于自适应零知识证明系统的稳健模型，该模型体现了传输对声明有效性的信心的更广泛的安全方面。在这个模型中，我们通过证明“证明良好行为”范式可以用于针对适应性对手的可证明安全性，从而解决了[GMW86]背后的非正式猜想。允许免费制作全部或部分 WIS 材料的数字硬拷贝以供个人或课堂使用，前提是这些拷贝不是为了盈利或商业利益而制作或分发的，版权声明、出版物的标题及其日期出现，并且声明是摘要）Beaver *
The seminal work of [GMW86] proposed the use of zero knowledge proof systems (ZKPS 's) as a means to demonstrate adherence to a specified network protocol, thereby protecting an interactive network computation against malicious sub-version. Each participant would prove – without revealing anything additional – that it indeed followed the rules. We give evidence that both the classical zero knowledge analysis [GMR89] and the particular ZKPS in [GM W86] are not sufficient to provide provable security against attacks by an adaptive malicious adversary, as follows. If the ZKPS for graph 3-colorability proposed in [GMW86] is provably secure against adversaries who can choose whom to corrupt as a protocol progresses, and if factoring is intractable, then the polynomial hierarchy collapses. In particular, any language in NP could be solved with access to an oracle for factoring. We also consider subtle requirements that classical ZKPS'S do not address, such as the privacy of the verifier, and show that some ZKPS'S may permit subtle attacks in which useful knowledge is leaked undetectable. To remedy these problems, we propose a robust model for adaptive zero-knowledge proof systems that embodies broader security aspects of transmitting confidence in the validity of a claim. Within this model, we resolve the informal conjecture behind [GMW86] by showing that the " prove-good-behavior " paradigm can be employed with provable security against adaptive adversaries. Permission to make digitallhard copies of all or pmt of WIS material for personal or classroom use is granted without fee provided that the copies are not made or dkibuted for profit or commercial advantage, the copyright notice, the title of the publication and its date appear, and notice is Abstract) Beaver *