Distributed Differential Privacy in the Shuffle Model

Abstract: How can we analyze sensitive data without compromising those users’ privacy?  And how can we do it when data is distributed across millions of devices, and no one is trusted to aggregate the data?  These problems are currently being solved using systems that combine differential privacy and lightweight forms of cryptographic secure computation, which impose significant restrictions on what differentially private algorithms we can implement.  In this work I will introduce the shuffle model of differential privacy as a way to study how to design differentially private algorithms for these systems and to understand their limitations.  I will present both algorithms and lower bounds for this model showing that for low-dimensional problems---computing counts, means, or histograms---this model is extremely powerful, but for high-dimensional problems---selecting relevant features or learning parities---this model is extremely limited.
This talk will be based on joint work with Albert Cheu, Adam Smith, David Zeber, and Maxim Zhilyaev.
Bio: Jonathan Ullman is an Associate Professor in the Khoury College of Computer Sciences at Northeastern University.  Before joining Northeastern, he received his PhD from Harvard in 2013, and in 2014 was a Junior Fellow in the Simons Society of Fellows.   His research centers on privacy for machine learning and statistics, and its surprising connections to topics like statistical validity, robustness, cryptography, and fairness.  He has been recognized with an NSF CAREER award and the Ruth and Joel Spira Outstanding Teacher Award.