Abstract. Differential privacy and secure multiparty computation and are two powerful tools that address orthogonal concerns: the former, roughly, describes what functions are "safe" to compute, and the latter tells how to securely compute arbitrary functions. It is of course possible to use secure computation to evaluate a differentially private function, but doing so may be overkill and thus lead to sub-optimal performance.
We show here one particular example based on the recent shuffle model of differential privacy. That model assumes a trusted shuffler who anonymizes users' results before sending them to a server for analysis. It is natural to try to replace the shuffler with a distributed shuffling protocol run by the N users themselves; however, existing fully secure shuffling protocols require O(N^2) communication. We put forth a notion of differential obliviousness for shuffling, prove that this notion suffices for implementing the shuffle model, and show a differentially oblivious shuffling protocol with O(N log N) communication.
This talk will not assume any prior background on differential privacy or secure computation.
Biography. Jonathan Katz is a professor in the Department of Computer Science at the University of Maryland, where he served as director of the Maryland Cybersecurity Center for over 5 years. He is passionate about education, and has co-authored one of the leading textbooks on cryptography and offers a free online cryptography course at Coursera.org. He is an IACR Fellow, was named University of Maryland Distinguished Scholar-Teacher in 2017-2018, and received the ACM SIGSAC Outstanding Contribution Award in 2019.