精确零知识证明系统研究

被引量 : 5次 | 上传用户:yinyilin183
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
零知识证明是当今密码学中一个令人着迷的领域,它在现代密码学中有着极广的应用。零知识证明具有两点看起来相互矛盾的性质,一方面它能使有效的验证者能够接受某个正确论断,另一方面验证者却不能从该证明中学到任何新知识。在传统定义中,零知识性是指多项式时间验证者在交互中的视能在多项式时间内被重构。然而,一些文献指出零知识的这种传统定义是不精确的。最近一些研究者提出一称为精确零知识的新概念,该概念的引入动机是将传统零知识的定义精确化。一个证明称之为是精确零知识的,是指任何验证者在交互中的视都能被模拟器在几乎相同的时间内重构。可见,精确零知识的概念对零知识性的刻画非常得精细。而且,一些研究者们又进一步将这个概念从单机环境下推广至并发环境,提出了精确并发零知识的概念。在本文中,我们考察了精确零知识研究的以下方面,包括具有良好性质的精确有界并发零知识协议的构造、精确零知识协议的通信复杂性、精确零知识协议的顺序合成以及如何提出新的刻画精确模拟的方法等。在第一个方面,我们试问对于任意NP语言是否能够构造具有较低轮复杂性的精确有界并发零知识协议?对于任意NP语言是否能够构造出精确有界并发零知识证明?在第二个方面,我们试问是否能降低目前精确零知识协议的通信量?比如由多项式降至多项式对数?在第三个方面,我们试问是否能为顺序合成后的精确零知识协议提供紧的精度?在第四个方面,我们试问是否能提出一种新的、更强的刻画精确模拟的方法?以下是本文的主要贡献,其中所有的结论都需要使用非黑盒模拟技术。精确有界并发零知识论证有界并发是指在构造相应的协议前需要预先知道并发会话的个数,已知的精确并发零知识协议均是超对数轮的,即使在有界并发环境下也是如此。对于协议来说,轮数是其复杂性的一个重要指标,因此在本文中,我们考察是否能够构造具有较低轮复杂性的精确有界并发零知识论证。我们对这个问题给出了肯定回答,即我们对任意NP语言构造了第一个公开硬币的精确有界并发零知识论证,该论证仅使用几乎常数轮。精确有界并发零知识证明目前已知的精确并发零知识协议都是论证系统,这就意味着协议的合理性仅对任意多项式时间的敌手成立。我们对任意NP语言构造了第一个精确有界并发零知识证明系统。相比于论证系统,证明系统的优势在于其合理性对任意计算能力不受限的欺骗证明者均成立。具有多项式对数通信量的精确零知识协议的通信量是协议复杂性的另一重要衡量指标。目前已知的精确零知识协议其各轮消息的长度和都是多项式的,因此在本文中,我们考察如何降低精确零知识协议的通信量。我们将构造精确零知识协议的新模拟技术与已知的具有多项式对数通信量的零知识协议相结合,证明了对任意NP语言均存在具有多项式对数通信量的精确零知识论证系统,多项式对数通信量即指协议中各轮消息的长度和是多项式对数的。关于精确零知识的顺序合成已知的精确零知识的顺序合成引理指出,精确零知识协议在顺序合成时仍然是精确的,但合成后的协议却不能很好地保持原子协议的精度。在本文中,我们针对一类特殊的精确零知识协议提出了一顺序合成引理,该引理说明合成后的协议也能很好地保持原有协议的精度。我们称这类特殊协议为仿效黑盒精确零知识协议,由于已知的精确零知识协议很多是仿效黑盒的,因此我们的结论仍具有一般性。精确时间与空间可模拟零知识已有的精确零知识概念通过模拟器与验证者运行时间的关系来刻画精确模拟。但是,任何算法在执行时都需消耗两种基本资源,即时间与空间。由于已有工作并不考虑空间上的精确模拟,因此所有已知的零知识协议不能实现同时时间与空间上的精确模拟。本文中,我们提出了精确时间与空间可模拟零知识的概念,该概念比已有的精确零知识概念更强,其本质思想是指验证者在交互中所学到的知识能被模拟器不仅在相同的时间、而且在相同的空间内重构。我们进而对任意NP语言构造出第一批精确时间与空间可模拟零知识证明与论证。在本文的最后一部分,我们对全文进行总结并给出了未来工作展望。
其他文献
目的对支原体培养计数及药敏结果耐药率分析,指导临床合理使用抗生素及临床送检意义探讨。方法整群选取该院2011年1—12月门诊患者,男性946例,女性2 267例,以初诊为尿道炎、
区域经济发展问题历来是学术界研究的热点问题。本文旨在立足前人所做研究的基础上,运用经济地理学、发展经济学、区域经济学的理论和方法,并结合当代全球经济形势,特别是在
目的:评价文拉法辛与舍曲林抑郁症的疗效及安全性。方法:将76例抑郁症患者随机分为两组,分别给予文拉法辛和舍曲林治疗,疗程8周。用汉密尔顿抑郁量表(HAMD)评定临床疗效,副反
如今,地理信息系统在环境保护领域的应用得到了越来越多的关注,GIS与环境应用模型的集成问题逐渐成为地理信息系统应用研究的热点之一。随着《建设项目环境风险评价技术导则
<正>电视剧《历史转折中的邓小平》热播简介:2014年8月22日,是邓小平诞辰110周年纪念日。8月8日,48集电视剧《历史转折中的邓小平》在央视首播,收视率高于同时段其他影视剧。
《民族音乐学研究:31个概念和问题》是内特尔在1983年出版的《民族音乐学研究:29个概念和问题》的基础上进行修订的新版。全书共分四部分:笔者负责翻译其中的第一和第四部分:
建立实验动物脑血栓模型,对探讨缺血性脑损伤的发生机制及对防治脑血栓、脑缺血的相关研究有理论和实践价值。本文对脑血栓动物模型的建模原理及方法进行综述,并对各类模型的
研究目的梳理糖尿病社区管理的业务流程和各类信息工具的功能、应用现状,分析当前信息工具在支持糖尿病社区管理中存在的主要问题,并探讨其原因;结合典型案例,分析探讨糖尿病
为定量描述水果形状以便为后续识别提供特征信息,以黄瓜为研究对象,通过对黄瓜图像进行增强、阈值、形态学及边界提取操作,提取黄瓜边界并用数对表示。采用椭圆傅里叶描述子
形状表示是模式识别和计算机视觉中最重要的研究内容之一。针对传统形状表示算法对形状的整体特征和细节信息不能同时描述、通用性不高的问题,提出了一种基于高斯多尺度分析下