黑盒分离下界，密码协议的轮效率与困难性假设

In this project, focusing on the security reduction methods, we study the round complexity of some cryptographic protocols and the problems whether we can base public-key cryptography on more general hardness assumptions. In particular, we will recheck the well-known black-box separations, aiming to a better understanding of the problem of which ones can be broken; we will develop some new type of reduction/simulation methods, and construct some concurrent zero knowledge protocols and concurrently secure cryptographic protocols that break the black-box lower bounds on their round complexity; for those classic 3-round protocols, such as the Blum's protocols and Schnorr and G-Q identification schemes, we will develop some new black-box techniques to bypass some known restricted black-box lower bounds and prove that they are more secure than the known negative results suggested.

本项目将围绕安全性归约技术研究密码协议的轮复杂性，探索将公钥密码系统建立在更低困难性假设的可能性。我们将重新检查公钥密码系统和协议中已知的黑盒归约下界，厘清哪些黑盒下界是必然可以被新的非通用归约技术突破的；拟开发新的归约/模拟技术，构造网络并发环境下安全在轮复杂性上能突破目前已知黑盒下界的零知识证明和若干其他密码协议；针对一些经典的高效证据隐藏和身份认证协议，如3-轮的Blum协议，Schnorr以及G-Q身份认证协议，拟开发新的黑盒归约技巧绕过已知的在一些限制条件下的黑盒下界，证明它们具有目前还未被证明的更强的安全性。

围绕安全性规约技术，我们取得了一系列原创新的研究成果：1.开发了全新的安全性归约方法-个体化归约技术。利用这一技术，我们突破了一系列黑盒归约下界，在公钥密码领域取得了如下的正面结果：a) 公钥模型下三轮并发零知识协议（Alwen在Crypto05上证明黑盒归约下是不可能的）；b) 两轮的选择性打开安全的承诺方案（Xiao在TCC13上证明黑盒归约下是不可能的）；c) 大大简化了标准模型下低轮复杂度零知识证明（如两/三轮弱零知识证明与证据隐藏协议等）的构造和其安全性证明。2.提出了新的输入分布转换和嵌入式黑盒归约技术，在针对单个证据断言的证明系统安全性上打破了已知在某种限制条件下的黑盒下界[Pass, STOC 11]，证明了大量经典构造的证据隐藏性；在Schnorr和G-Q身份认证的安全性证明上改进了2002年Bellare等人的结果，进一步降低了它们的安全性所依赖的假设。3.基于iO假设和抗碰撞hash函数假设第一次给出了常数轮的并发不可延展性零知识协议的构造和证明；通过研究零知识协议中的同时可重置性和并发不可延展性两种不同敌手下的安全性，第一次给出了具有同时可重置和并发不可延展性两种性质的零知识协议的构造。4. 提出了一种新的基于PCP机制的非黑盒模拟技术，并利用该技术对目前轮复杂度最优的公开抛币并发零知识协议[Canetti, Lin, Paneth TCC2013 ]进行优化，从而给出了一种改进的对数轮的低通信量公开抛币并发零知识协议；通过使用[Barak, Goldreich, Sahai FOCS2001]转换技术，可以直接对我们的公开抛币并发零知识协议进行转换从而获得一种改进的具有可重置合理性的并发零知识协议，进而利用[Deng, Goyal, Sahai FOCS2009]的技术可以实现同时可重置并发零知识协议。