Courant Lectures Part II
Tuesday, April 28, 2015, 11:00am
Warren Weaver Hall, Room 102
Professor Shafi Goldwasser
ACM Turing Award Laureate and the RSA Professor of Electrical Engineering & Computer Science at MIT and Professor of Computer Science and Applied Mathematics at the Weizmann Institute
On Time and Order in Cryptography
The availability of vast amounts of data is changing how we can make medical discoveries, predict global market trends, save energy, improve our infrastructures, and develop new educational strategies. One obstacle to this revolution is the willingness of different entities to share their data with others.
The theory of secure multiparty computation (MPC) seemingly addresses this problem in the best way possible. Namely, parties learn the minimum necessary information: the value of the function computed on their joint data and nothing else. However, the theory of MPC does not deal with an important aspect: when do different players receive their output?
The concepts of time and order of events is fundamental to our way of thinking. In time-sensitive applications, the timing and order of output discovery may be another important deciding factor in whether parties choose to share their data. In this work, we incorporate time and order of output delivery into the theory of MPC and show general completeness theorems for newly defined ordered MPCs and timed-delay MPCs. Next, we show how ordered MPC can give rise to MPCs which are provably “worth” joining, in competitive settings where relative time of output discovery changes the utility of discovery. We formalize a model of collaboration and design a mechanism in which n self interested parties can decide, based on their inputs, on an ordering of output delivery and a distribution of outputs to be delivered which guarantees a higher reward for all participants if such a guarantee is possible.
Joint work with Sunoo Park and Pablo Azar.