Title:

“Garbled Circuits: 30 Years After”

Who:

Rafail Ostrovsky

Professor of Computer Science and Mathematics

UCLA

When:

December 4, 2015 @ 2:00 pm

Reception to follow

Where:

Klaus Advanced Computing Building, 1116 East & West

Presented by:

The School of Computer Science

Abstract

30 years ago Andy Yao introduced the notion of “Garbled Circuits” in a seminal paper which has over 2000 citations according to Google Scholar. The paper showed how a Boolean circuit can be “garbled” in such a way that it can still be evaluated (on a separately garbled input), yet without the evaluator understanding internal wire values while performing the evaluation. However, several key questions puzzled researchers for over a quarter century: how do you garble general computer programs instead of circuits, and how do you make it useful for delegating computation to the cloud (the so-called adaptive security problem). Resolution of these questions eluded researchers for decades. We recently made progress on both problems, and I will describe these advances and their fascinating applications.  

Bio

Rafail Ostrovsky is a Professor of Computer Science and Professor of Mathematics at UCLA. Prof. Ostrovsky came to UCLA in 2003 from Bellcore where he was a Senior Research Scientist. Prior to beginning his career at Bellcore, he was an NSF Mathematical Sciences Postdoctoral Research Fellow at UC Berkeley. Dr. Ostrovsky received his Ph.D. in computer science from MIT in 1992, in the Theory of Computation Group (advisor: Silvio Micali, thesis: Software Protection). Prof. Ostrovsky is an honorary Fellow of the IACR; he has 14 U.S. issued patents and over 240 papers published in refereed journals and conferences. Dr. Ostrovsky currently serves as a Chair of the IEEE Technical Committee on Mathematical Foundations of Computing and has served on 40 international conference Program Committees including serving as a PC chair of FOCS 2011. He is a member of the Editorial Board of Journal of ACM; Editorial Board of Algorithmica; and the Editorial Board of Journal of Cryptology. Dr. Ostrovsky's awards include: 2014 Rosalinde and Arthur Gilbert Foundation Research Award; 2012 Pazy Memorial Research Award; the Best Paper Award of the 2008 International Conference on Computing and Combinatorics (COCOON-2008); 2006 and 2005 Xerox Corporate Innovation Faculty Awards; 2006 IBM Faculty Award; 2006 Xerox Corporation Distinguished Lecture Series; 2005 Distinguished Cryptographer of the Year Lecture Series NTT Labs, Japan; OKAWA Foundation 2004 Research Award; three SAIC Awards for the best published work of the year (1999, 2001, 2002) in computer science and mathematics; the 1996 Bellcore Prize for excellence in research; 1993 Henry Taub Prize; and multiple papers solicited to journal special issues dedicated to highest PC-ranked STOC/FOCS articles. At UCLA, Prof. Ostrovsky heads security and cryptography multi-disciplinary Research Center (http://www.cs.ucla.edu/security/) at Henry Samueli School of Engineering and Applied Science.