[Colloquium] REMINDER: today's talk by Salil Vadhan

[Margery Ishmael]

DEPARTMENT OF COMPUTER SCIENCE - TALK

Date: Wednesday, May 10, 2006
Time: 2:30 p.m.
Place: Ryerson 251

-------------------------------------------

Speaker:  SALIL VADHAN

From:  Harvard University

Url:  http://www.eecs.harvard.edu/~salil/

Title:  The Complexity of Zero Knowledge

Abstract:

The study of zero-knowledge proofs has been one of the most fertile  
grounds
for interaction between cryptography and complexity theory.  On one  
hand,
zero-knowledge proofs and their cryptographic applications naturally  
raise
interesting complexity issues, such as tradeoffs between various  
efficiency
measures and the minimal assumptions needed to construct zero-knowledge
proofs.  On the other hand, the study of proofs is intimately related  
to the
central questions of complexity theory, and zero knowledge enriches this
study by incorporating such intriguing concepts as interaction,  
randomness,
knowledge, and secrecy.

In this talk, I will survey our efforts in the complexity-theoretic  
study of
zero knowledge, where we have characterized the classes of problems  
having
various types of zero-knowledge proofs, established general theorems  
about
these classes, and minimized (indeed, often eliminated) complexity
assumptions in the study of zero knowledge.  In particular, I will  
discuss
our most recent result, showing that all of NP has "statistical
zero-knowledge arguments" under the (minimal) assumption that one-way
functions exist, which resolves an open problem posed by Naor,  
Ostrovsky,
Venkatesan, and Yung in 1992.

Joint works with Minh Nguyen, Shien Jin Ong, and others.

***The talk will be followed by refreshments in Ryerson 255***

-------------------------------------------------------

Host:  Lance Fortnow

People in need of assistance should call 773-834-8977 in advance.

For information on future CS talks, please see: http:// 
www.cs.uchicago.edu/events









-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20060510/6cfec27d/attachment.htm