Provost Distinguished International Scholar
Andrew Chi-Chih Yao
Tsinghua University
"Secure Multiparty Computation and Percolation Theory"
Abstract:
In secure multiparty computations, participants each with a secret input would like to jointly compute a function while keeping their input values private. For instance, the participants may want to compute the average value of their salaries without revealing their individual ones. In this talk we discuss the problem of secure multiparty computations in the recent elegant graph-based computation model of Desmedt et al, where the inputs are elements over a group. In particular, we show that secure computations are possible as long as the fraction of honest participants exceeds at least slightly over the majority. Curiously, the solution uses tools and deep results from percolation theory, which is an active branch of mathematical physics. This appears to be the first time when percolation theory is applied to cryptography. (This is joint work with Xiaoming Sun and Christophe Tartary.)
Bio
Prof. Andrew Chi-Chih Yao is a Professor of Computer Science at Tsinghua University and the Director of the Institute for Theoretical Computer Science. Dr. Yao has won many prestigious awards including the Turing Award (the Nobel Prize of Computer Science), the Guggenheim Fellowship, the George Polya Prize, Donald E. Knuth Prize, and the Pan Wen-Yuan Research Award. He is a Fellow of the National Academy of Sciences, the Association for Computing Machinery, and the American Academy of Arts and Sciences. After obtaining his Ph.D. in Physics from Harvard in 1972 and his Ph.D. in Computer Science from the University of Illinois in 1975, he has been a professor at MIT, Stanford, Berkeley, and Princeton. He is the
recipient
of three honorary doctorates. Dr. Yao has been a seminal researcher in many areas of theoretical computer science including circuit complexity, cryptography, quantum computing, and the interplay between randomness and computation. His website: http://itcs.tsinghua.edu.cn/yao/ contains the list of his students, past and present, and an extensive publication list.
URL: http://www.castu.tsinghua.edu.cn/yao/
Thursday, October 23, 2008
3:00 - 4:15
Wu & Chen
101 Levine Hall