Penn Arts & Sciences Logo

Tuesday, November 6, 2001 - 3:00pm

Cynthia Dwork

Microsoft Silicon Valley Research Center

Location

University of Pennsylvania

Towne Bldg. - Room 337

[lecture is from 3:00 - 4:30]

A zero-knowledge interactive proof system allows a prover to convince a verifier of the truth of a statement, without revealing any additional information about "why" the statement is true. Determining the minimum amount of interaction needed for zero-knowledge proofs has been the subject of intensive study since the concept was introduced in 1985 by Goldwasser, Micali, and Rackoff. Consider a setting in which the prover enters a special ``proving chamber'' from which access to the outside world is impossible and into which only a certain amount of information, or ``advice,'' may be carried. Such a setting might be realized by means of a special smart-card reader. We show that in this setting there exist two-round (that is, two-message) zero-knowledge proof systems for any language in NP. The talk will be self-contained. [Joint work with Larry Stockmeyer.]