Úlfar Erlingsson
Vasyl Pihur
ABSTRACT
Randomized Aggregatable Privacy-Preserving Ordinal Response, or RAPPOR, is a technology for crowdsourcing statistics from end-user client software, anonymously, with strong privacy guarantees. In short, RAPPORs allow the forest of client data to be studied, without permitting the possibility of looking at individual trees. By applying randomized response in a novel manner, RAPPOR provides the mechanisms for such collection as well as for efficient, high-utility analysis of the collected data. In particular, RAPPOR permits statistics to be collected on the population of client-side strings with strong privacy guarantees for each client, and without linkability of their reports. This paper describes and motivates RAPPOR, details its differential-privacy and utility guarantees, discusses its practical deployment and properties in the face of different attack models, and, finally, gives results of its application to both synthetic and real-world data.
- Charu C. Aggarwal and Philip S. Yu. On privacy-preservation of text and sparse binary data with sketches. In Proceedings of the 2007 SIAM International Conference on Data Mining (SDM), pages 57--67, 2007.Google Scholar
- Istemi Ekin Akkus, Ruichuan Chen, Michaela Hardt, Paul Francis, and Johannes Gehrke. Non-tracking web analytics. In Proceedings of the 2012 ACM Conference on Computer and Communications Security (CCS), pages 687--698, 2012. Google ScholarDigital Library
- Yoav Benjamini and Yosef Hochberg. Controlling the false discovery rate: A practical and powerful approach to multiple testing. Journal of the Royal Statistical Society Series B (Methodological), 57(1):289--300, 1995.Google ScholarCross Ref
- Giuseppe Bianchi, Lorenzo Bracciale, and Pierpaolo Loreti. 'Better Than Nothing' privacy with Bloom filters: To what extent? In Proceedings of the 2012 International Conference on Privacy in Statistical Databases (PSD), pages 348--363, 2012. Google ScholarDigital Library
- Burton H. Bloom. Space/time trade-offs in hash coding with allowable errors. Commun. ACM, 13(7):422--426, July 1970. Google ScholarDigital Library
- Andrei Z. Broder and Michael Mitzenmacher. Network applications of Bloom filters: A Survey. Internet Mathematics, 1(4):485--509, 2003.Google ScholarCross Ref
- T.-H. Hubert Chan, Mingfei Li, Elaine Shi, and Wenchang Xu. Differentially private continual monitoring of heavy hitters from distributed streams. In Proceedings of the 12th International Conference on Privacy Enhancing Technologies (PETS), pages 140--159, 2012. Google ScholarDigital Library
- Ruichuan Chen, Alexey Reznichenko, Paul Francis, and Johannes Gehrke. Towards statistical queries over distributed private user data. In Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation (NSDI), pages 169--182, 2012. Google ScholarDigital Library
- Chromium.org. Design Documents: RAPPOR (Randomized Aggregatable Privacy Preserving Ordinal Responses). http://www.chromium.org/developers/design-documents/rappor.Google Scholar
- Cynthia Dwork. A firm foundation for private data analysis. Commun. ACM, 54(1):86--95, January 2011. Google ScholarDigital Library
- Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Proceedings of 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), pages 486--503, 2006. Google ScholarDigital Library
- Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the 3rd Theory of Cryptography Conference (TCC), pages 265--284, 2006. Google ScholarDigital Library
- Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), pages 715--724, 2010. Google ScholarDigital Library
- Cynthia Dwork, Moni Naor, Toniann Pitassi, Guy N. Rothblum, and Sergey Yekhanin. Pan-private streaming algorithms. In Proceedings of The 1st Symposium on Innovations in Computer Science (ICS), pages 66--80, 2010.Google Scholar
- Justin Hsu, Marco Gaboardi, Andreas Haeberlen, Sanjeev Khanna, Arjun Narayan, Benjamin C. Pierce, and Aaron Roth. Differential privacy: An economic method for choosing epsilon. In Proceedings of 27th IEEE Computer Security Foundations Symposium (CSF), 2014.Google Scholar
- Justin Hsu, Sanjeev Khanna, and Aaron Roth. Distributed private heavy hitters. In Proceedings of the 39th International Colloquium Conference on Automata, Languages, and Programming (ICALP) - Volume Part I, pages 461--472, 2012. Google ScholarDigital Library
- Krishnaram Kenthapadi, Aleksandra Korolova, Ilya Mironov, and Nina Mishra. Privacy via the Johnson-Lindenstrauss transform. Journal of Privacy and Confidentiality, 5(1):39--71, 2013.Google ScholarCross Ref
- Daniel Keren, Guy Sagy, Amir Abboud, David Ben-David, Assaf Schuster, Izchak Sharfman, and Antonios Deligiannakis. Monitoring distributed, heterogeneous data streams: The emergence of safe zones. In Proceedings of the 1st International Conference on Applied Algorithms (ICAA), pages 17--28, 2014.Google ScholarDigital Library
- Daniel Kifer and Ashwin Machanavajjhala. No free lunch in data privacy. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD), pages 193--204, 2011. Google ScholarDigital Library
- Bin Liu, Yurong Jiang, Fei Sha, and Ramesh Govindan. Cloud-enabled privacy-preserving collaborative learning for mobile sensing. In Proceedings of the 10th ACM Conference on Embedded Network Sensor Systems (SenSys), pages 57--70, 2012. Google ScholarDigital Library
- Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 94--103, 2007. Google ScholarDigital Library
- Darakhshan J. Mir, S. Muthukrishnan, Aleksandar Nikolov, and Rebecca N. Wright. Pan-private algorithms via statistics on sketches. In Proceedings of Symposium on Principles of Database Systems (PODS), pages 37--48, 2011. Google ScholarDigital Library
- Ilya Mironov. On significance of the least significant bits for differential privacy. In Proceedings of ACM Conference on Computer and Communications Security (CCS), pages 650--661, 2012. Google ScholarDigital Library
- Nina Mishra and Mark Sandler. Privacy via pseudorandom sketches. In Proceedings of Symposium on Principles of Database Systems (PODS), pages 143--152, 2006. Google ScholarDigital Library
- Aaron Roth and Tim Roughgarden. Interactive privacy via the median mechanism. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), pages 765--774, 2010. Google ScholarDigital Library
- Robert Tibshirani. Regression shrinkage and selection via the Lasso. Journal of the Royal Statistical Society, Series B, 58:267--288, 1994.Google Scholar
- Stanley L. Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309):pp. 63--69, 1965.Google ScholarCross Ref
- Wikipedia. Randomized response. http://en.wikipedia.org/wiki/Randomized_response.Google Scholar
Index Terms
- RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response
Recommendations
A Privacy Protection Evaluation Mechanism for Dynamic Data Based on Chunk-Confusion
Nowadays big data security plays a major issue in cloud computing. Chunk-confusion-based privacy protection mechanism (CCPPM) protects the privacy of the tenants in plaintext. But both multi-tenant applications' data and tenants' privacy requirements ...
A novel anonymization algorithm: Privacy protection and knowledge preservation
In data mining and knowledge discovery, there are two conflicting goals: privacy protection and knowledge preservation. On the one hand, we anonymize data to protect privacy; on the other hand, we allow miners to discover useful knowledge from ...
Privacy consensus in anonymization systems via game theory
DBSec'12: Proceedings of the 26th Annual IFIP WG 11.3 conference on Data and Applications Security and PrivacyPrivacy protection appears as a fundamental concern when personal data is collected, stored, and published. Several anonymization methods have been proposed to address privacy issues in private datasets. Every anonymization method has at least one ...
Comments