CT-ISG: New Directions in Cryptographic Proof Systems

University Of California-Los Angeles, Los Angeles CA

Investigators

Abstract

Cryptographic proof systems have played an instrumental role in cryptography. The applications of cryptographic proof systems to an wide array of problems such as electronic voting, database security, secure electronic commerce, identity management, computing on secret data, trusted computing, and networking are well know. Significant efficiency barriers remain to the widespread use of general cryptographic proof systems. We propose an ambitious focused research plan to overcome these barriers, by developing a new methodology based on elliptic-curve groups to 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 constructing non-interactive cryptographic proof systems (such as zero-knowledge proofs), based on a direct commit-and-prove technique. Our framework promises to greatly reduce proof sizes for cryptographic proofs. In the most general setting, where we are given a boolean circuit C and wish to prove that there exists some input x such that C(x) = 1, we seek proofs that contain only O(|C|) group elements, where |C| denotes the size of the circuit. (2) The very act of interpreting the statement to be proven as a boolean circuit itself often introduces a substantial overhead. We observe that there has been considerable recent development of cryptographic schemes based on bilinear groups. We propose to develop a set of techniques that can be used to directly prove a variety of interesting statements about essentially any cryptographic scheme based on bilinear groups.