## 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)

20 July (Thursday) at 1630 hrs
Gates 4B (opposite 490)