零知识证明若干基本问题的研究

零知识证明是密码学以及复杂性理论的核心内容之一，对它的一些基本问题的研究一直倍受关注。Barak由非黑箱模拟技术所得结论引发了人们对一些有关零知识协议的否定性结论的重新思考，而且随后对零知识证明在可并发性、可重置性、轮复杂性等方面的研究也取得了一些成果，但目前仍有许多基本问题尚未解决或很好地解决，如常数轮可并发（甚至可重置）的零知识证明的存在性问题，常数轮可并发的知识的零知识证明的存在性问题等。最近，申请者利用一种新的非黑箱模拟思想和新的交互证明模式，解决了标准假设下NP问题的3轮零知识证明系统的存在性这一公开问题，而且在知识的零知识证明、以及可并发的知识的零知识论证方面也取得了很好的结果。本项目将在已有的研究基础上，对可并发或可重置的常数轮零知识协议的存在性、不可延展的可并发（乃至可重置）的零知识协议的存在性，以及有关知识的（强）零知识证明和（强）证据不可区分等一些基本问题进行深入研究。

零知识证明在密码学中有着广泛的应用，为满足各种复杂环境下安全性的要求，人们提出满足更强安全性的零知识协议，如可并发性、不可延展性、可容忍泄露等，因此有许多倍受关注的基本问题都有待研究解决。此外，各种零知识协议的轮复杂性以及无复杂性假设的零知识协议的存在性也是研究者关注的问题。本项目在已有的研究积累的基础上，对这些基本问题进行了深入的研究。研究工作基本按原有研究计划逐步进行，提出了一些新的思想和方法，在可并发零知识证明、知识的零知识证明等方面取得了一些比较理想的研究成果。随着研究工作的逐步深入，我们对研究了零知识证明中一些本质问题，如零知识的定义问题。此外，我们也关注了新近提出的泄露容忍零知识协议，目前已经在泄露容忍知识的零知识证明的存在性方面取得了有意义的结果。项目对可重置零知识协议的研究遇到较大的困难，目前尚未能取得较理想的结果，但这方面的研究仍在进行中。总的来说，项目的研究工作按计划基本完成了预定研究目标，取得了许多很有价值的结果,主要研究成果如下：1）在抗碰撞hash函数存在的条件下，分别利用claw-free函数与统计隐藏承诺方案给出了NP问题的两个可有界并发常数轮知识的零知识论证系统；2）证明了若1-1 单向函数和2 轮具有统计隐藏性的承诺方案存在， 则NP问题的常数轮知识的零知识证明系统的存在性；3）在轮复杂性方面，利用Claw-free陷门置换，给出了NP问题的5轮 (黑箱)零知识的零知识证明系统，而依据Katz在TCC2008上发表的结果，该5轮证明系统其轮复杂性是最优的（若多项式分层不坍塌）；另外，在因子分解的困难性假设下，采用特殊的非黑箱模拟方法给出NP问题的3轮非黑箱零知识证明系统；4）在抗碰撞hash函数存在的条件下，利用claw-free函数和强陷门置换，给出了具有多项式时间的知识抽取器的常数轮知识的零知识证明系统；5）研究了泄露容忍知识的零知识协议的存在性，利用2轮统计隐藏承诺方案的，首次给出了 (1+a)-泄露容忍知识的零知识证明系统，其中a>0问任意常数；6）假设抗碰撞hash函数存在和DDH假设成立，在抗碰撞hash函数存在和DDH假设成立的条件下，首次给出了常数轮泄露容忍知识的零知识证明系统。除此之外，对理性多方安全计算、分布式OT协议等方面的研究也得到了有意义的结果。