零知识论证系统:可重置性与并发性
文献类型:学位论文
作者 | 邓燚 |
学位类别 | 博士 |
答辩日期 | 2008-01-14 |
授予单位 | 中国科学院软件研究所 |
授予地点 | 软件研究所 |
关键词 | 零知识 双重可重置性 纯公钥模型 并发零知识 在线知识提取器 |
其他题名 | Zero Knowledge Arguments: Resettability and Concurrency |
中文摘要 | 零知识证明在密码学和计算复杂性领域都有着极为深远的影响。本文研究在现实的异步通信环境(如互联网)下关于零知识论证系统的可重置性(最强安全性)和并发性的一些根本性问题,其中包括由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等人的构造一般来讲相对要高。 |
语种 | 中文 |
公开日期 | 2011-03-17 |
页码 | 177 |
源URL | [http://124.16.136.157/handle/311060/7482] ![]() |
专题 | 软件研究所_基础软件国家工程研究中心_学位论文 |
推荐引用方式 GB/T 7714 | 邓燚. 零知识论证系统:可重置性与并发性[D]. 软件研究所. 中国科学院软件研究所. 2008. |
入库方式: OAI收割
来源:软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。