New Techniques for Zero Knowledge

Amit Sahai, Computer Science Department, UCLA

Non-interactive zero-knowledge (NIZK) protocols are fundamental cryptographic primitives used in many constructions. In this talk, we will discuss new techniques for constructing NIZK protocols using computational assumptions over elliptic curve groups and associated bilinear maps.

Using these new techniques, we resolve a number of open questions about NIZK, such as:

• We show how to construct Perfect NIZK Arguments for any language in NP.
• We show how to construct Non-interactive Witness-Indistinguishable Proofs for any language in NP, without a common reference string (such a result was only known previously under a non-standard assumption).
• We show how to construct NIZK Proofs and Arguments for Circuit Satisfiability, where the length of the Common Reference String is O(k) and the length of the proof is O(k|C|), where |C| is the size of the circuit.

(joint work with Jens Groth and Rafail Ostrovsky, appearing in Eurocrypt 2006 and Crypto 2006)

Gates 4B (opposite 490)