零知识证明的两种变体与非延展性质的研究

零知识证明已经成为密码协议设计中一个非常重要的工具，它的发展也对计算复杂性的发展有着极为深远的影响。本文研究了零知识证明的两种变体和零知识证明的非延展性质。 文中所研究的零知识证明的两种变体是指Pass在EUROCRYPT'03上提出来的$n^{poly(logn)}$-模拟的证明和他在CRYPTO'03上提出来的公共参考串模型下的可否认零知识。对这两种变体，得到了如下结果： （1）基于抵抗亚指数线路的单向置换的存在性，构造了5-轮的高效并发的$n^{poly(logn)}$-模拟的知识论证系统。该方案使用了普通的$\Sigma$-协议作为工具。在EUROCRYPT'03中，使用了特殊的诚实验证者完全零知识（我们称之为完全$\Sigma$-协议）来构造4-轮$n^{poly(logn)}$-完全模拟的知识论证系统。这个构造是基于无爪函数的存在性的，并且它在并发合成下的封闭性紧紧依赖于$\Sigma$-协议的完全模拟性质。在EUROCRYPT'03的方案中，若使用普通的$\Sigma$-协议代替完全$\Sigma$-协议作为构造模块，得到的协议在并发合成下未必封闭。 （2）给出了公共参考串模型下的可否认零知识的一个正面结果，即：从$\Sigma$-协议到公共参考串模型下的可否认零知识的高效转化。由Pass给出的关于非平凡语言的公共参考串模型下的可否认零知识的轮数下界可知，该 转化取得了最优的轮效率。另外，转化前后增加的通信复杂度比较低。 关于非延展零知识，我们的工作主要是对现有的非延展的非交互零知识证明方案进行分析和简化。另外，引入了实例依赖的可验证随机函数（简写为InstD-VRF）这一新工具来构造非延展的非交互零知识协议。 得到的结果如下： （1）利用签名方案构造非延展的非交互零知识协议： 把Garay等人在EUROCRYPT'03中给出的公共参考串模型下的3-轮并发非延展零知识论证转化成了健壮的非交互零知识论证系统。一方面，与Garay的方案相比，在相同的模型下，提高了轮效率。另一方面，和现有的健壮非交互零知识方案相比，新方案中证明的长度比较短，并且归约计算的速度比较快。 （2）利用“隐藏地选取不可拷贝的集合”技术构造非延展的非交互零知识协议：对De Santis等给出的基于“隐藏地选取不可拷贝的集合”（hidden unduplicatable set selection）技术的方案做了如下简化：去掉了公共参考串中的冗余部分，缩短了公共参考串中部分随机串的长度，同时简化了两个子协议中所要证明的定理。这使得证明过程中的归约效率有所提高，同时缩短了证明的长度。 （3）利用InstD-VRF构造模非延展的非交互零知识证明：以InstD-VRF为工具，构造了比较简单的非延展的非交互零知识证明。实际上，由于InstD-VRF的构造方法有很多种，这个方案可以看成是构造非延展的非交互零知识证明的一个框架。在某种程度上，利用个框架，可以把构造高效的非延展的非交互零知识证明问题归结为构造高效的InstD-VRF的问题。