clarke@csri.toronto.edu (Jim Clarke) (05/11/88)
(GB = Galbraith Building, 35 St. George Street) SUMMARY: THEORY SEMINAR, Monday, May 16, 11:00 am, GB244 -- Shafi Goldwasser "Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation" THEORY SEMINAR, Wednesday, May 18, 11:00 am, GB244 -- Silvio Micali "Non-Interactive Zero-Knowledge and Its Applications" -------- THEORY SEMINAR, Monday, May 16, 11:00 am, GB244 Professor Shafi Goldwasser M.I.T. "Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation" Every function of n inputs can be efficiently computed by a complete net- work of n processors in such a way that: 1. If no faults occur, no set of size t<n/2 of players gets any addi- tional information (other than the function value), 2. Even if Byzantine faults are allowed, no set of size t<n/3 can either disrupt the computation or get additional information. Furthermore, the above bounds on t are tight. This is joint work with Michael Ben-Or and Avi Wigderson. THEORY SEMINAR, Wednesday, May 18, 11:00 am, GB244 Professor Silvio Micali M.I.T. "Non-Interactive Zero-Knowledge and Its Applications" We show that interaction in ANY zero-knowledge proof can be replaced by sharing a common, short, random string. We use this result to construct the FIRST public-key cryptosystem secure against chose ciphertext attack. This is joint work with Manuel Blum and Paul Feldman. -- Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4 (416) 978-4058 BITNET,CSNET: clarke@csri.toronto.edu CDNNET: clarke@csri.toronto.cdn UUCP: {allegra,cornell,decvax,linus,utzoo}!utcsri!clarke