Institutional Repository
| 零知识论证系统：可重置性与并发性 | |
| Alternative Title | Zero Knowledge Arguments: Resettability and Concurrency |
| 邓燚 | |
| 2008-01-14 | |
| Degree Grantor | 中国科学院软件研究所 |
| Degree Level | 博士 |
| Place of Degree Grantor | 软件研究所 |
| Keyword | 零知识 双重可重置性 纯公钥模型 并发零知识 在线知识提取器 |
| English Abstract | 零知识证明在密码学和计算复杂性领域都有着极为深远的影响。本文研究在现实的异步通信环境（如互联网）下关于零知识论证系统的可重置性（最强安全性）和并发性的一些根本性问题，其中包括由Barak，Goldreich，Goldwasser和Lindell在FOCS'01上提出的双重可重置猜想―猜想在标准模型中存在对NP语言的重置合理的可重置零知识论证系统，纯公钥模型（简记为BPK模型，由Canetti等人在STOC'00上提出）中一些重要的公开问题等。本文提出并实现了一系列的新的密码学概念，利用这些概念作为工具，对这些根本性问题进行了回答。详细地，本文取得了如下成果： 新密码学工具. 提出了两个新的实例依赖的密码学概念：实例依赖的可验证随机函数和实例依赖的WI。在一些标准的困难性假设下，我们实现了这两个新概念。 双重可重置猜想. 利用新开发的工具，在双重可重置猜想上取得了第一个重要的进展―在一些标准的困难性假设下证明了： 1. 在标准模型中存在对NP语言的重置合理的类有界可重置零知识论证系统； 2. 如果存在对NP语言的公开掷币的并发零知识论证系统，则双重可重置猜想成立。 完全解决BPK模型中两个公开问题. 利用实例依赖的WI作为工具，提出了一个我们称为Sigma-难题协议的新构造，对BPK模型中两个重要的公开问题给予了肯定的回答，这包括： 1. 证明了BPK模型中在标准的困难性假设下存在对NP语言的同时具有重置合理性和可重置零知识的常数轮论证系统， 即双重可重置猜想在BPK模型中成立； 2. 构造了BPK模型中第一个只依赖于多项式时间困难性假设（即标准的困难性假设）的对NP语言的具有并发合理性和黑盒可重置零知识的常数轮论证系统。 高效的并发零知识论证系统和在线知识提取器. 给出了一系列对某些具体数论问题的只需常数个模指数运算的§-协议，利用它们作为模块，提出了一个把对NP语言L的Sigma-协议转化成一个在BPK模型中对语言L 的4-轮并发合理的并发零知识论证系统的方法，这一转化本身只增加常数个额外的模指数运算并且能保持完美并发零知识性，而此前已知的转化方式需要线性个额外的模指数运算而且只能取得计算零知识性。沿Garay等人的研究路线，本文对图的汉密尔顿圈这一NP完全问题在公共参考串模型直接构造了一个3-轮具有在线知识提取器的-协议（进而可以利用它来对任意的NP语言构造这样的协议），这个论证系统具有某种消息结构上的对称性，并且对于那些在证明之前需要进行NP-归约的语言，这一构造在效率上比Garay等人的构造一般来讲相对要高。 |
| Abstract | The notion of zero knowledge proof has had a great impact on both cryptography and computational complexity. In this thesis we study some fundamental problems regarding zero knowledge arguments with strong notions of security―resettability (strongest notion of security) and concurrency which capture some nature security concerns raised by malicious asynchronous environment such as internet. These problems include the simultaneous resettability conjecture posed by Barak, Goldreich, Goldwasser, and Lindell in FOCS'01 which statesthere exist resettably-sound resettable zero knowledge arguments for NP, and some open problems in the bare public-key model (BPK for short, introduced by Canetti et al. in STOC'01). We put forward and realize several new cryptographic primitives, and using them as tools, we solve (partially or completely) these fundamental problems. In particular, the main results are the following: New cryptographic primitives. We put forward and realize, under some standard hardness assumptions, two useful notions of instance-dependent primitives: instance-dependent verifiable random functions and instance-dependent resettably-sound resettable WI argument of knowledge. Simultaneous resettability conjecture. Using above new primitives as tools, we make the first important progress toward the simultaneous resettability conjecture. Specifically, under some standard hardness assumptions,we show 1. There exist resettably-sound class-bounded resettable ZK arguments for NP in the plain model; 2. If public-coin concurrent ZK arguments exist for NP, then the simultaneous resettability conjecture is true. Settling two open problems in the BPK model completely. Using these new primitives as components, we put forward a novel structurefor simultaneously resettable argument we call Sigma-puzzles, and settle two important open problems positively, including: 1. Proving that there exist constant-round resettably-sound resettable zero knowledge arguments for NP in the BPK model under standard assumptions, namely, the simultaneous resettability conjecture is true in the BPK model; 2. Constructing the first constant-round concurrently-sound resettable zero knowledge arguments for NP in the BPK model under polynomial-time hardness (standard) assumptions. Efficient concurrent zero knowledge argument and online extractor. We present several very efficient constructions of Sigma-protocol for several number-theoretic problems, and using them as building blocks, we give a transformation of Sigma-protocol into 4-round concurrently-sound concurrent zero knowledge arguments for NP in the BPK model, and this transformation incurs only small constant number of additional modular exponentiations, and preserves perfect zero knowledge property. Following the research line initiated by Garay et al., we construct an Omega-protocol with online extractor for the Hamiltonian Cycle (and therefore yields Omega-protocols for NP). Our construction has nice symmetric property in the structure of transcript, and for those languages for which proof is carried out via NP-reduction, it is more efficient than the generic construction proposed by Garay et al.. |
| Pages | 177 |
| Language | 中文 |
| Content Type | 学位论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/7482 |
| Collection | 基础软件国家工程研究中心 |
| Recommended Citation GB/T 7714 | 邓燚. 零知识论证系统：可重置性与并发性[D]. 软件研究所. 中国科学院软件研究所,2008. |
| Files in This Item: | ||||||
| File Name/Size | DocType | Version | Access | License | ||
| 10001_20041801502907（1435KB） | 开放获取 | -- | Application Full Text | |||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment