From:                     Kendra Smith

Sent:                      Tuesday, April 18, 2000 8:25 PM

To:                         M?crosöft Research Tech Talk, Sem. Notice

Cc:                         Kendra Smith

Subject:                 UW-CSE Colloq / 5-2-2000 / Sahai / MIT / Statistical Zero Knowledge

UW-CSE Colloq / 5-2-2000 / Sahai / MIT / Statistical Zero Knowledge

 

*NOTE* This lecture will be broadcast live via the Internet. See

http://www.cs.washington.edu/news/colloq.info.html for more information.

 

UNIVERSITY OF WASHINGTON

Seattle, Washington 98195

 

Department of Computer Science and Engineering

Box 352350

(206) 543-1695

 

COLLOQUIUM

 

SPEAKER:      Amit Sahai, MIT

 

TITLE:          Statistical Zero Knowledge

 

DATE:           Tuesday, May 2, 2000

 

TIME:           3:30 pm

 

PLACE:                   134 Sieg Hall

 

HOST:           Paul Beame

 

ABSTRACT:

 

Zero-knowledge proofs, introduced by Goldwasser, Micali, and Rackoff,

are fascinating constructs in which one party (the "prover") convinces

another party (the "verifier") that some assertion is true, without

revealing anything else to the verifier.  Zero-knowledge proofs are

powerful tools for constructing secure cryptographic protocols, and

also yield rich classes of computational problems that are of

complexity-theoretic interest as well.  In this talk, we investigate

statistical zero-knowledge proofs, which are zero-knowledge proofs

where the condition that nothing is revealed to the verifier is

interpreted in a strong information-theoretic sense.

 

Our goal is to build a unified understanding of Statistical Zero

Knowledge.  We accomplish this goal by establishing two results:

 

- We show that the class of all problems possessing statistical

  zero-knowledge proofs has a natural complete problem.  This problem

  provides a new and simple characterization of statistical zero

  knowledge -- one which makes no reference to interaction or

  zero knowledge.

 

- We show how to transform any interactive proof system that is

  statistical zero knowledge only for an honest verifier (i.e., a

  verifier that follows the specified protocol) into one which is also

  zero knowledge against dishonest verifiers -- ones that may deviate

  arbitrarily from the specified protocol.

 

Using these results, we are able to unify and simplify nearly all

previously known results about statistical zero knowledge, and prove

several results answering many fundamental questions in this area.

 

An important feature of all our results is that, unlike many results

in cryptography, we require no unproven assumptions.

 

(Joint work with Oded Goldreich and Salil Vadhan)

 

Refreshments to follow.

 

Email: talk-info@cs.washington.edu

Info: http://www.cs.washington.edu