零知识证明:知识的抽取与公钥密码黑盒下界

摘要

零知识证明近年来在两个主流方向——复杂环境下的安全性和简洁高效短证明——上的发展都遇到了一个巨大的瓶颈,即如何从敌手程序中抽取相应陷门知识来进行安全性归约.目前已知的知识抽取都是利用一个构造性的算法来实现的,这一构造性的实现给零知识证明本身的发展带来了许多障碍,如何通过证明抽取算法的存在性来绕过这些障碍是一个巨大的挑战.在本报告里我们将介绍这一挑战,着重阐述这一挑战与许多看似毫无关联的公钥密码理论中一些经典问题之间的联系,重新审视一系列被证明无法利用黑盒归约来证明其安全性的公钥密码系统/协议,并讨论突破黑盒归约下界和建立新型个体化安全性归约方法的可能途径.