phyllis@utcsrgv.UUCP (Phyllis Eve Bregman) (12/09/83)
UofT Department of Computer Science Seminar Schedule for the week of December 12th 1983 Thursday, December 15th, 2:00 P.M., GB248: Mr. Silvio Micali, Laboratory for Computer Science, Cambridge, Mass.: "How to construct random functions". ABSTRACT: We assume that functions that are one-way in a very weak sense exist. We prove that in probabilistic polynomial time it is possible to construct **deterministic** polynomial time computable functions g: {1,...,2 sup k} ---> {1,...2 sup k} that cannot be distinguished from a **random** function by any polynomial time algorithm. This complexity theoretic result has many applications to probabilistic constructions, cryptography, protocols, hashing and counting arguments. -- Phyllis Eve Bregman CSRG, Univ. of Toronto {decvax,linus,ihnp4,uw-beaver,floyd,utzoo}!utcsrgv!phyllis