Resolving the Simultaneous Resettability Conjecture and a New Non-Black-Box Simulation Strategy
Resolving the Simultaneous Resettability Conjecture and a New Non-Black-Box Simulation Strategy
复制标题
DOI：
10.1109/focs.2009.59
复制
发表时间：
2009-10
期刊：
影响因子：
--
通讯作者：
Yi Deng;Vipul Goyal;A. Sahai
中科院分区：
文献类型：
--
作者：
Yi Deng;Vipul Goyal;A. Sahai
Canetti、Goldreich、Goldwasser 和 Micali (STOC 2000) 引入了可重置零知识证明的概念，其中协议必须是零知识，即使作弊验证者可以重置证明者并进行多次交互，其中证明者使用相同的随机磁带。不久之后，Barak、Goldreich、Goldwasser 和 Lindell (FOCS 2001) 研究了密切相关的可重置健全性概念，其中即使作弊证明者可以重置验证者以与同一验证者的随机磁带进行多次交互，协议的健全性条件也必须成立。这项工作留下的主要问题是是否有可能拥有一个同时可重置零知识和可重置健全的协议。我们通过构建这样一个协议来解决这个问题。我们构建的核心是一种新的非黑盒模拟策略，我们相信它具有独立的意义。这种新策略允许模拟器将递归倒带技术（在并发模拟中常见）与非黑盒模拟“结合”。以前的非黑盒策略会导致这种情况下计算复杂性呈指数级增长，而我们的新策略能够避免这种情况。
Canetti, Goldreich, Goldwasser, and Micali (STOC 2000) introduced the notion of resettable zero-knowledge proofs, where the protocol must be zero-knowledge even if a cheating verifier can reset the prover and have several interactions in which the prover uses the same random tape. Soon afterwards, Barak, Goldreich, Goldwasser, and Lindell (FOCS 2001) studied the closely related notion of resettable soundness, where the soundness condition of the protocol must hold even if the cheating prover can reset the verifier to have multiple interactions with the same verifier's random tape. The main problem left open by this work was whether it is possible to have a single protocol that is simultaneously resettable zero knowledge and resettably sound. We resolve this question by constructing such a protocol. At the heart of our construction is a new non-black-box simulation strategy, which we believe to be of independent interest. This new strategy allows for simulators which "marry'' recursive rewinding techniques (common in the context of concurrent simulation) with non-black-box simulation. Previous non-black-box strategies led to exponential blowups in computational complexity in such circumstances, which our new strategy is able to avoid.