TIME: 3:30-4:30 pm,  Friday, May 16, 2008

PLACE: CSE 503  

SPEAKER: Salil Vadhan
         Harvard University (visiting UC Berkeley)

TITLE: An Equivalence between Zero Knowledge and Commitments


ABSTRACT:

We show an equivalence between two fundamental cryptographic
primitives: zero-knowledge protocols, which are interactive proofs
that reveal nothing other than the validity of the statement being
proven; and commitment schemes, which are the digital analogues of
"safes".

Specifically, we show that a language in NP has a zero-knowledge
protocol if and only if the language has an "instance-dependent"
commitment scheme.  An instance-dependent commitment schemes for a
given language is a commitment scheme that can depend on an instance
of the language, and where the hiding and binding properties are
required to hold only on the YES and NO instances of the language,
respectively.

The novel direction is the "only if" direction. Thus, we confirm the
widely held belief that commitments are not only sufficient for zero
knowledge protocols, but *necessary* as well.  Previous results of
this type either held only for restricted types of protocols or
languages, or used nonstandard relaxations of (instance-dependent)
commitment schemes.

Joint work with Shien Jin Ong.