e22b2b54 
 372250e6 
 XPost: cs.bboard, columbia.general.bboard 
 From: rocco@news.cs.columbia.edu 
  
 Hi all, 
  
 Salil Vadhan will be giving the theory seminar this Thursday, April 21, at 
 2:30pm in the CS conference room.  Title and abstract are given below. 
  
 -- Rocco 
  
 ==================================================================== 
  
 THEORY SEMINAR 
 2:30pm, Thursday, April 21, 2005 
  CS Conference Room 
 Title: "An Unconditional Study of Computational Zero Knowledge" 
  
 Speaker: Salil Vadhan 
    Computer Science 
          Harvard University 
  
 ABSTRACT: 
  
 We prove a number of general theorems about ZK, the class of problems 
 possessing computational zero-knowledge proofs. Our results are 
 *unconditional*, in contrast to most previous works on ZK, which rely on 
 the assumption that one-way functions exist. 
  
 In particular, we show that: 
 - Honest-verifier ZK equals general ZK, 
 - Public-coin ZK equals private-coin ZK, 
 - ZK is closed under union, and 
 - ZK with imperfect completeness equals ZK with perfect completeness. 
  
 Our approach is to combine the conditional techniques previously used in 
 the study of ZK with the unconditional techniques that we and others 
 developed in the study of SZK, the class of problems possessing 
 statistical zero-knowledge proofs.  To enable this combination, we prove 
 that every problem in ZK can be decomposed into a problem in SZK together 
 with a set of instances from which a one-way function can be constructed. 
  
 --- SoupGate-Win32 v1.05 
  * Origin: you cannot sedate... all the things you hate (1:229/2)