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 one half. 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.
Andrew Chi-Chih Yao received his BS in Physics from National Taiwan University (1967), PhD in Physics from Harvard University (1972), and PhD in Computer Science from the University of Illinois (1975). From 1975 onward, Yao served on the faculty at MIT, Stanford, UC Berkeley and, during 1986 – 2004, as William and Edna Macaleer Professor of Engineering and Applied Science at Princeton University. In 2004, he left Princeton to join Tsinghua University in Beijing. He is also a Distinguished Professor-at-Large at the Chinese University of Hong Kong.
Yao’s research interests are in the theory of computation and its applications to cryptography and quantum computing. He is recipient of the prestigious A.M. Turing Award in year 2000 for his contributions to the theory of computation, including pseudorandom number generation, cryptography, and communication complexity. He has received numerous other honors and awards, including the George Polya Prize, the Donald E. Knuth Prize, and honorary doctorates from the Chinese University of Hong Kong, the City University of Hong Kong, the Hong Kong University of Science and Technology, and the University of Waterloo. He is a member of the US National Academy of Sciences, the American Academy of Arts and Sciences, and the Chinese Academy of Sciences.
