2019

Improving Utility and Security of the Shuffler-based Differential Privacy

Wang, Tianhao, Ding, Bolin, Xu, Min et al.

Understand

When collecting information, local differential privacy (LDP) alleviates privacy concerns of users because their private information is randomized before being sent it to the central aggregator.

LDP imposes large amount of noise as each user executes the randomization independently.
To address this issue, recent work introduced an intermediate server with the assumption that this intermediate server does not collude with the aggregator.
Under this assumption, less noise can be added to achieve the same privacy guarantee as LDP, thus improving utility for the data collection task.

Built on

S. L. Warner, “Randomized response: A survey technique for eliminating evasive answer bias,” Journal of the American Statistical Association , vol. 60, no. 309, pp. 63–69, 1965
1965
Earlier work this paper cites.
S. Pohlig and M. Hellman, “An improved algorithm for computing logarithms overgf(p)and its cryptographic significance (corresp.),” IEEE Transactions on Information Theory , 1978
1978
Earlier work this paper cites.
P. Paillier, “Public-key cryptosystems based on composite degree residuosity classes,” in International Conference on the Theory and Applications of Cryptographic Techniques . Springer, 1999, pp. 223–238
1999
Earlier work this paper cites.
C. Dwork, “Differential privacy,” in ICALP , 2006, pp. 1–12
2006
Earlier work this paper cites.
C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor, “Our data, ourselves: Privacy via distributed noise generation,” in EUROCRYPT , ser. Lecture Notes in Computer Science, S. Vaudenay, Ed., vol. 4004. Springer, 2006, pp. 486–503
2006
Earlier work this paper cites.
I. Damgård, M. Geisler, and M. Krøigaard, “Efficient and secure comparison for on-line auctions,” in Australasian Conference on Information Security and Privacy . Springer, 2007, pp. 416–430
2007
Earlier work this paper cites.
D. Bogdanov, S. Laur, and J. Willemson, “Sharemind: A framework for fast privacy-preserving computations,” in European Symposium on Research in Computer Security . Springer, 2008, pp. 192–206
2008
Earlier work this paper cites.
I. Damgard, M. Geisler, and M. Kroigard, “Homomorphic encryption and secure comparison,” Int. J. Appl. Cryptol. , vol. 1, no. 1, pp. 22–31, Feb. 2008
2008
Earlier work this paper cites.
I. Mironov, O. Pandey, O. Reingold, and S. Vadhan, “Computational differential privacy,” in Annual International Cryptology Conference . Springer, 2009, pp. 126–142
2009
Earlier work this paper cites.
A. McGregor, I. Mironov, T. Pitassi, O. Reingold, K. Talwar, and S. Vadhan, “The limits of two-party differential privacy,” in 2010 IEEE 51st Annual Symposium on Foundations of Computer Science . IEEE, 2010, pp. 81–90
2010
Earlier work this paper cites.
S. Laur, J. Willemson, and B. Zhang, “Round-efficient oblivious database manipulation,” in International Conference on Information Security . Springer, 2011, pp. 262–277
2011
Earlier work this paper cites.
M. Andrés, N. Bordenabe, K. Chatzikokolakis, and C. Palamidessi, “Geo-indistinguishability: Differential privacy for location-based systems,” in 20th ACM Conference on Computer and Communications Security . ACM, 2013, pp. 901–914
2013
Earlier work this paper cites.
J. C. Duchi, M. I. Jordan, and M. J. Wainwright, “Local privacy and statistical minimax rates,” in FOCS , 2013, pp. 429–438
2013
Earlier work this paper cites.
T. Elahi, G. Danezis, and I. Goldberg, “Privex: Private collection of traffic statistics for anonymous communication networks,” in Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security , 2014, pp. 1068–1079
2014
Earlier work this paper cites.
Ú. Erlingsson, V. Pihur, and A. Korolova, “Rappor: Randomized aggregatable privacy-preserving ordinal response,” in CCS . ACM, 2014, pp. 1054–1067
2014
Earlier work this paper cites.
R. Bassily and A. Smith, “Local, private, efficient protocols for succinct histograms,” in Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing . ACM, 2015, pp. 127–135
2015
Earlier work this paper cites.
R. Bassily and A. D. Smith, “Local, private, efficient protocols for succinct histograms,” in STOC , 2015
2015
Earlier work this paper cites.
L. Melis, G. Danezis, and E. De Cristofaro, “Efficient private statistics with succinct sketches,” arXiv preprint arXiv:1508.06110 , 2015
Original
2015
Earlier work this paper cites.

Similar

R. Bassily, K. Nissim, U. Stemmer, and A. Thakurta, “Practical locally private heavy hitters,” arXiv preprint arXiv:1707.04982 , 2017
Original
2017
Cited alongside, same era.
R. Bassily, K. Nissim, U. Stemmer, and A. G. Thakurta, “Practical locally private heavy hitters,” in NIPS , 2017
2017
Cited alongside, same era.
A. Bittau, U. Erlingsson, P. Maniatis, I. Mironov, A. Raghunathan, D. Lie, M. Rudominer, U. Kode, J. Tinnes, and B. Seefeld, “Prochlo: Strong privacy for analytics in the crowd,” in SOSP . ACM, 2017
2017
Cited alongside, same era.
B. Ding, J. Kulkarni, and S. Yekhanin, “Collecting telemetry data privately,” in Advances in Neural Information Processing Systems , 2017, pp. 3574–3583
2017
Cited alongside, same era.
S. Doudalis, I. Kotsogiannis, S. Haney, A. Machanavajjhala, and S. Mehrotra, “One-sided differential privacy,” arXiv preprint arXiv:1712.05888 , 2017
Original
2017
Cited alongside, same era.
D. Froelicher, P. Egger, J. S. Sousa, J. L. Raisaro, Z. Huang, C. Mouchet, B. Ford, and J.-P. Hubaux, “Unlynx: a decentralized system for privacy-conscious data sharing,” Proceedings on Privacy Enhancing Technologies , vol. 2017, no. 4, pp. 232–250, 2017
2017
Cited alongside, same era.
X. He, A. Machanavajjhala, C. Flynn, and D. Srivastava, “Composing differential privacy and secure computation: A case study on scaling private record linkage,” in Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security . ACM, 2017, pp. 1389–1406
2017
Cited alongside, same era.
B. McMahan and D. Ramage, “Federated learning: Collaborative machine learning without centralized training data,” Google Research Blog , vol. 3, 2017
2017
Cited alongside, same era.
S. Wang, Y. Nie, P. Wang, H. Xu, W. Yang, and L. Huang, “Local private ordinal data distribution estimation,” in INFOCOM 2017-IEEE Conference on Computer Communications, IEEE . IEEE, 2017, pp. 1–9
2017
Cited alongside, same era.
T. Wang, J. Blocki, N. Li, and S. Jha, “Locally differentially private protocols for frequency estimation,” in 26th USENIX Security Symposium , 2017
2017
Cited alongside, same era.
J. M. Abowd, “Protecting the confidentiality of america’s statistics: Adopting modern disclosure avoidance methods at the census bureau,” https://www.census.gov/newsroom/blogs/research-matters/2018/08/protecting_the_confi.html , 2018
2018
Cited alongside, same era.
A. Bhowmick, J. Duchi, J. Freudiger, G. Kapoor, and R. Rogers, “Protection against reconstruction and its applications in private federated learning,” arXiv preprint arXiv:1812.00984 , 2018
Original
2018
Cited alongside, same era.

Then

T. H. Chan, K.-M. Chung, B. M. Maggs, and E. Shi, “Foundations of differentially oblivious algorithms,” in SODA . SIAM, 2019
2019
Closest in time.
A. Cheu, A. D. Smith, J. Ullman, D. Zeber, and M. Zhilyaev, “Distributed differential privacy via shuffling,” in EUROCRYPT , 2019
2019
Closest in time.
Ú. Erlingsson, V. Feldman, I. Mironov, A. Raghunathan, K. Talwar, and A. Thakurta, “Amplification by shuffling: From local to central differential privacy via anonymity,” in SODA , 2019, pp. 2468–2479
2019
Closest in time.
B. Ghazi, N. Golowich, R. Kumar, R. Pagh, and A. Velingker, “On the power of multiple anonymous messages,” arXiv preprint arXiv:1908.11358 , 2019
Original
2019
Closest in time.
B. Ghazi, P. Manurangsi, R. Pagh, and A. Velingker, “Private aggregation from fewer anonymous messages,” arXiv preprint arXiv:1909.11073 , 2019
Original
2019
Closest in time.
B. Ghazi, R. Pagh, and A. Velingker, “Scalable and differentially private distributed aggregation in the shuffled model,” arXiv preprint arXiv:1906.08320 , 2019
Original
2019
Closest in time.
X. Gu, M. Li, Y. Cao, and L. Xiong, “Supporting both range queries and frequency estimation with local differential privacy,” in 2019 IEEE Conference on Communications and Network Security (CNS) . IEEE, 2019, pp. 124–132
2019
Closest in time.
M. E. Gursoy, A. Tamersoy, S. Truex, W. Wei, and L. Liu, “Secure and utility-aware data collection with condensed local differential privacy,” arXiv preprint arXiv:1905.06361 , 2019
Original
2019
Closest in time.
T. Murakami and Y. Kawamoto, “Utility-optimized local differential privacy mechanisms for distribution estimation,” in 28th USENIX Security Symposium , 2019
2019
Closest in time.
F.-Y. Rao, J. Cao, E. Bertino, and M. Kantarcioglu, “Hybrid private record linkage: Separating differentially private synopses from matching records,” ACM Transactions on Privacy and Security (TOPS) , vol. 22, no. 3, p. 15, 2019
2019
Closest in time.
E. Roth, D. Noble, B. H. Falk, and A. Haeberlen, “Honeycrisp: large-scale differentially private aggregation without a trusted core,” in Proceedings of the 27th ACM Symposium on Operating Systems Principles . ACM, 2019, pp. 196–210
2019
Closest in time.
S. Ruggles, S. Flood, R. Goeken, J. Grover, E. Meyer, J. Pacas, and M. Sobek, “Integrated public use microdata series: Version 9.0 [database],” 2019
2019
Closest in time.
T. Wang, B. Ding, J. Zhou, C. Hong, Z. Huang, N. Li, and S. Jha, “Answering multi-dimensional analytical queries under local differential privacy,” in SIGMOD , 2019
2019
Closest in time.
——, “Private summation in the multi-message shuffle model,” arXiv preprint arXiv:2002.00817 , 2020
Original
2020
Closest in time.
A. R. Chowdhury, C. Wang, X. He, A. Machanavajjhala, and S. Jha, “Crypt ϵ \epsilon : Crypto-assisted differential privacy on untrusted servers,” SIGMOD , 2020
2020
Closest in time.
Ú. Erlingsson, V. Feldman, I. Mironov, A. Raghunathan, S. Song, K. Talwar, and A. Thakurta, “Encode, shuffle, analyze privacy revisited: Formalizations and empirical evaluation,” arXiv preprint arXiv:2001.03618 , 2020
Original
2020
Closest in time.
X. Gu, M. Li, L. Xiong, and Y. Cao, “Providing input-discriminative protection for local differential privacy,” in ICDE , 2020
2020
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…