On the Round Complexity of the Shuffle Model

A pseudorandom generator from any one-way function

Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby · 1999

Earlier work this paper cites.

Our data, ourselves: Privacy via distributed noise generation

Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor · 2006

Earlier work this paper cites.

Calibrating noise to sensitivity in private data analysis

Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith · 2006

Earlier work this paper cites.

Cryptography from anonymity

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai · 2006

Earlier work this paper cites.

Distributed private data analysis: Simultaneously solving how and what

Amos Beimel, Kobbi Nissim, and Eran Omri · 2008

Earlier work this paper cites.

Pan-private streaming algorithms

Cynthia Dwork, Moni Naor, Toniann Pitassi, Guy N. Rothblum, and Sergey Yekhanin · 2010

Earlier work this paper cites.

What can we learn privately?

Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith · 2011

Earlier work this paper cites.

Bounds on the sample complexity for private learning and private data release

Amos Beimel, Hai Brenner, Shiva Prasad Kasiviswanathan, and Kobbi Nissim · 2014

Earlier work this paper cites.

Local, private, efficient protocols for succinct histograms

Raef Bassily and Adam D. Smith · 2015

Earlier work this paper cites.

Practical locally private heavy hitters

Raef Bassily, Kobbi Nissim, Uri Stemmer, and Abhradeep Guha Thakurta · 2017

Cited alongside, same era.

Prochlo: Strong privacy for analytics in the crowd

Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnés, and Bernhard Seefeld · 2017

Cited alongside, same era.

The complexity of differential privacy

Original

Salil Vadhan · 2017

Cited alongside, same era.

Perfect secure computation in two rounds

Benny Applebaum, Zvika Brakerski, and Rotem Tsabary · 2018

Cited alongside, same era.

Fingerprinting codes and the price of approximate differential privacy

Mark Bun, Jonathan Ullman, and Salil P. Vadhan · 2018

Cited alongside, same era.

Two-round MPC: information-theoretic and black-box

Sanjam Garg, Yuval Ishai, and Akshayaram Srinivasan · 2018

Distributed differential privacy via shuffling

Albert Cheu, Adam D. Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev · 2019

Later among the works it cites.

Amplification by shuffling: From local to central differential privacy via anonymity

Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta · 2019

Later among the works it cites.

On the power of multiple anonymous messages

Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, and Ameya Velingker · 2019

Later among the works it cites.

Scalable and differentially private distributed aggregation in the shuffled model

Original

Badih Ghazi, Rasmus Pagh, and Ameya Velingker · 2019

Later among the works it cites.

Separating local & shuffled differential privacy via histograms

Victor Balcer and Albert Cheu · 2020

Closest in time.