Non-Interactive Circuit Based Proofs and Non-Interactive Perfect Zero-knowledge with Preprocessing

In the first part of this paper, we present a non-interactive zero-knowledge proof system for Circuit Satisfiability. With this protocol, we can prove an arbitrary NP-statement non-interactively without using Karp-reductions to 3-SAT or Graph Hamiltonicity. The proof system is based on the quadratic residuosity problem and allows processing of XOR and NOT gates at virtually no cost. It is significantly more efficient than previously known non-interactive proof systems. In the second part, we present protocols based on the existence of collision intractable hash functions, leading to a statistical zero-knowledge non-interactive argument with preprocessing for any NP-statement. Under the certified discrete log assumption, the protocol is perfect zero-knowledge. In the preprocessing, the parties need only exchange messages of length independent of the theorem to be proved later. This is the first protocol with such efficient preprocessing that does not need to assume oblivious transfer. Finally we present a perfect zero-knowledge non-interactive protocol based on discrete logarithms that may potentially remove the need for preprocessing.