CT-ISG: New Directions in Cryptographic Proof Systems

密码证明系统在密码学中发挥了重要作用。密码证明系统在电子投票、数据库安全、安全电子商务、身份管理、秘密数据计算、可信计算和网络等一系列问题上的应用是众所周知的。通用密码验证系统的广泛使用仍然存在显著的效率障碍。我们提出了一个雄心勃勃的重点研究计划来克服这些障碍，通过开发一种新的基于椭圆曲线群的方法来显著提高密码证明系统的效率。我们的研究计划有两个主要的技术推动力：(1)我们提出了一个新的技术框架来构建非交互式密码证明系统(如零知识证明)，基于直接提交和证明技术。我们的框架承诺大大减少密码证明的证明大小。在最一般的情况下，我们得到一个布尔回路C，并希望证明存在一些输入x使得C(X)=1，我们寻找只包含O(|C|)群元素的证明，其中|C|表示回路的大小。(2)将要证明的语句本身解释为布尔电路本身往往会带来相当大的开销。我们注意到，基于双线性群的密码方案最近有了相当大的发展。我们建议开发一套技术，可以用来直接证明关于基本上任何基于双线性群的密码方案的各种有趣的陈述。

Cryptographic proof systems have played an instrumental role incryptography. The applications of cryptographic proof systems to an widearray of problems such as electronic voting, database security, secureelectronic commerce, identity management, computing on secret data,trusted computing, and networking are well know. Significant efficiencybarriers remain to the widespread use of general cryptographic proofsystems. We propose an ambitious focused research plan to overcome thesebarriers, by developing a new methodology based on elliptic-curve groupsto dramatically increase the efficiency of cryptographic proof systems.Our research plan has two main technical thrusts:(1) We propose to introduce a new technical framework for constructingnon-interactive cryptographic proof systems (such as zero-knowledgeproofs), based on a direct commit-and-prove technique. Our frameworkpromises to greatly reduce proof sizes for cryptographic proofs. In themost general setting, where we are given a boolean circuit C and wish toprove that there exists some input x such that C(x) = 1, we seek proofsthat contain only O(|C|) group elements, where |C| denotes the size of thecircuit. (2) The very act of interpreting the statement to be proven as a booleancircuit itself often introduces a substantial overhead. We observe thatthere has been considerable recent development of cryptographic schemesbased on bilinear groups. We propose to develop a set of techniques thatcan be used to directly prove a variety of interesting statements aboutessentially any cryptographic scheme based on bilinear groups.