论文部分内容阅读
零知识证明是当今密码学中一个令人着迷的领域,它在现代密码学中有着极广的应用。零知识证明具有两点看起来相互矛盾的性质,一方面它能使有效的验证者能够接受某个正确论断,另一方面验证者却不能从该证明中学到任何新知识。在传统定义中,零知识性是指多项式时间验证者在交互中的视能在多项式时间内被重构。然而,一些文献指出零知识的这种传统定义是不精确的。最近一些研究者提出一称为精确零知识的新概念,该概念的引入动机是将传统零知识的定义精确化。一个证明称之为是精确零知识的,是指任何验证者在交互中的视都能被模拟器在几乎相同的时间内重构。可见,精确零知识的概念对零知识性的刻画非常得精细。而且,一些研究者们又进一步将这个概念从单机环境下推广至并发环境,提出了精确并发零知识的概念。在本文中,我们考察了精确零知识研究的以下方面,包括具有良好性质的精确有界并发零知识协议的构造、精确零知识协议的通信复杂性、精确零知识协议的顺序合成以及如何提出新的刻画精确模拟的方法等。在第一个方面,我们试问对于任意NP语言是否能够构造具有较低轮复杂性的精确有界并发零知识协议?对于任意NP语言是否能够构造出精确有界并发零知识证明?在第二个方面,我们试问是否能降低目前精确零知识协议的通信量?比如由多项式降至多项式对数?在第三个方面,我们试问是否能为顺序合成后的精确零知识协议提供紧的精度?在第四个方面,我们试问是否能提出一种新的、更强的刻画精确模拟的方法?以下是本文的主要贡献,其中所有的结论都需要使用非黑盒模拟技术。精确有界并发零知识论证有界并发是指在构造相应的协议前需要预先知道并发会话的个数,已知的精确并发零知识协议均是超对数轮的,即使在有界并发环境下也是如此。对于协议来说,轮数是其复杂性的一个重要指标,因此在本文中,我们考察是否能够构造具有较低轮复杂性的精确有界并发零知识论证。我们对这个问题给出了肯定回答,即我们对任意NP语言构造了第一个公开硬币的精确有界并发零知识论证,该论证仅使用几乎常数轮。精确有界并发零知识证明目前已知的精确并发零知识协议都是论证系统,这就意味着协议的合理性仅对任意多项式时间的敌手成立。我们对任意NP语言构造了第一个精确有界并发零知识证明系统。相比于论证系统,证明系统的优势在于其合理性对任意计算能力不受限的欺骗证明者均成立。具有多项式对数通信量的精确零知识协议的通信量是协议复杂性的另一重要衡量指标。目前已知的精确零知识协议其各轮消息的长度和都是多项式的,因此在本文中,我们考察如何降低精确零知识协议的通信量。我们将构造精确零知识协议的新模拟技术与已知的具有多项式对数通信量的零知识协议相结合,证明了对任意NP语言均存在具有多项式对数通信量的精确零知识论证系统,多项式对数通信量即指协议中各轮消息的长度和是多项式对数的。关于精确零知识的顺序合成已知的精确零知识的顺序合成引理指出,精确零知识协议在顺序合成时仍然是精确的,但合成后的协议却不能很好地保持原子协议的精度。在本文中,我们针对一类特殊的精确零知识协议提出了一顺序合成引理,该引理说明合成后的协议也能很好地保持原有协议的精度。我们称这类特殊协议为仿效黑盒精确零知识协议,由于已知的精确零知识协议很多是仿效黑盒的,因此我们的结论仍具有一般性。精确时间与空间可模拟零知识已有的精确零知识概念通过模拟器与验证者运行时间的关系来刻画精确模拟。但是,任何算法在执行时都需消耗两种基本资源,即时间与空间。由于已有工作并不考虑空间上的精确模拟,因此所有已知的零知识协议不能实现同时时间与空间上的精确模拟。本文中,我们提出了精确时间与空间可模拟零知识的概念,该概念比已有的精确零知识概念更强,其本质思想是指验证者在交互中所学到的知识能被模拟器不仅在相同的时间、而且在相同的空间内重构。我们进而对任意NP语言构造出第一批精确时间与空间可模拟零知识证明与论证。在本文的最后一部分,我们对全文进行总结并给出了未来工作展望。