skip to main content
research-article

SplitX: high-performance private analytics

Published: 27 August 2013 Publication History

Abstract

There is a growing body of research on mechanisms for preserving online user privacy while still allowing aggregate queries over private user data. A common approach is to store user data at users' devices, and to query the data in such a way that a differentially private noisy result is produced without exposing individual user data to any system component. A particular challenge is to design a system that scales well while limiting how much the malicious users can distort the result. This paper presents SplitX, a high-performance analytics system for making differentially private queries over distributed user data. SplitX is typically two to three orders of magnitude more efficient in bandwidth, and from three to five orders of magnitude more efficient in computation than previous comparable systems, while operating under a similar trust model. SplitX accomplishes this performance by replacing public-key operations with exclusive-or operations. This paper presents the design of SplitX, analyzes its security and performance, and describes its implementation and deployment across 416 users.

References

[1]
Apache Thrift. http://thrift.apache.org/.
[2]
Directive 2009/136/EC of the European Parliament and of the Council. http://eur-lex.europa.eu/LexUriServ/LexUriServ.do?uri=OJ:L:2009:337: 0011:0036:en:PDF.
[3]
Web Tracking Protection. http://www.w3.org/Submission/web-tracking-protection/.
[4]
I. E. Akkus, R. Chen, M. Hardt, P. Francis, and J. Gehrke. Non-tracking web analytics. In CCS, 2012.
[5]
B. Applebaum, H. Ringberg, M. J. Freedman, M. Caesar, and J. Rexford. Collaborative, Privacy-Preserving Data Aggregation at Scale. In Privacy Enhancing Technologies, 2010.
[6]
M. Backes, A. Kate, M. Maffei, and K. Pecina. ObliviAd: Provably Secure and Practical Online Behavioral Advertising. In IEEE Symposium on Security and Privacy, 2012.
[7]
C. Castelluccia and A. Narayanan. Privacy considerations of online behavioural tracking. In European Network and Information Security Agency (ENISA), 2012.
[8]
D. Chaum. The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability. J. Cryptology, 1(1):65--75, 1988.
[9]
R. Chen, A. Reznichenko, P. Francis, and J. Gehrke. Towards Statistical Queries over Distributed Private User Data. In NSDI, 2012.
[10]
Y. Duan, J. Canny, and J. Z. Zhan. P4P: Practical Large-Scale Privacy-Preserving Distributed Computation Robust against Malicious Users. In USENIX Security Symposium, 2010.
[11]
C. Dwork. Differential Privacy. In ICALP, 2006.
[12]
C. Dwork. Differential Privacy: A Survey of Results. In TAMC, 2008.
[13]
C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor. Our Data, Ourselves: Privacy Via Distributed Noise Generation. In EUROCRYPT, 2006.
[14]
C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating Noise to Sensitivity in Private Data Analysis. In TCC, 2006.
[15]
J. Freudiger, N. Vratonjic, and J.-P. Hubaux. Towards Privacy-Friendly Online Advertising. In W2SP, 2009.
[16]
B. C. M. Fung, K. Wang, R. Chen, and P. S. Yu. Privacy-preserving data publishing: A survey of recent developments. ACM Comput. Surv., 42(4), 2010.
[17]
S. Goldwasser and S. Micali. Probabilistic Encryption and How to Play Mental Poker Keeping Secret All Partial Information. In STOC, 1982.
[18]
S. Goldwasser and S. Micali. Probabilistic Encryption. J. Comput. Syst. Sci., 28(2):270--299, 1984.
[19]
S. Guha, B. Cheng, and P. Francis. Privad: Practical Privacy in Online Advertising. In NSDI, 2011.
[20]
M. Hardt and S. Nath. Privacy-aware personalization for mobile advertising. In CCS, 2012.
[21]
S. Katti, J. Cohen, and D. Katabi. Information Slicing: Anonymity Using Unreliable Overlays. In NSDI, 2007.
[22]
A. Machanavajjhala, J. Gehrke, D. Kifer, and M. Venkitasubramaniam. l-Diversity: Privacy Beyond k-Anonymity. In ICDE, 2006.
[23]
A. Nandi, A. Aghasaryan, and M. Bouzid. P3: A Privacy Preserving Personalization Middleware for Recommendation-based Services. In HotPETS, 2011.
[24]
R. A. Popa, C. M. S. Redfield, N. Zeldovich, and H. Balakrishnan. CryptDB: protecting confidentiality with encrypted query processing. In SOSP, 2011.
[25]
K. P. N. Puttaswamy, R. Bhagwan, and V. N. Padmanabhan. Anonygator: Privacy and Integrity Preserving Data Aggregation. In Middleware, 2010.
[26]
V. Rastogi and S. Nath. Differentially private aggregation of distributed time-series with transformation and encryption. In SIGMOD, 2010.
[27]
E. Shi, J. Bethencourt, H. T.-H. Chan, D. X. Song, and A. Perrig. Multi-Dimensional Range Query over Encrypted Data. In IEEE Symposium on Security and Privacy, 2007.
[28]
E. Shi, T.-H. H. Chan, E. G. Rieffel, R. Chow, and D. Song. Privacy-Preserving Aggregation of Time-Series Data. In NDSS, 2011.
[29]
E. G. Sirer, S. Goel, M. Robson, and D. Engin. Eluding carnivores: file sharing with strong anonymity. In ACM SIGOPS European Workshop, 2004.
[30]
D. X. Song, D. Wagner, and A. Perrig. Practical Techniques for Searches on Encrypted Data. In IEEE Symposium on Security and Privacy, 2000.
[31]
L. Sweeney. k-Anonymity: A Model for Protecting Privacy. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 10(5):557--570, 2002.
[32]
V. Toubiana, A. Narayanan, D. Boneh, H. Nissenbaum, and S. Barocas. Adnostic: Privacy Preserving Targeted Advertising. In NDSS, 2010.
[33]
D. I. Wolinsky, H. Corrigan-Gibbs, B. Ford, and A. Johnson. Dissent in Numbers: Making Strong Anonymity Scale. In OSDI, 2012.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM SIGCOMM Computer Communication Review
ACM SIGCOMM Computer Communication Review  Volume 43, Issue 4
October 2013
595 pages
ISSN:0146-4833
DOI:10.1145/2534169
Issue’s Table of Contents
  • cover image ACM Conferences
    SIGCOMM '13: Proceedings of the ACM SIGCOMM 2013 conference on SIGCOMM
    August 2013
    580 pages
    ISBN:9781450320566
    DOI:10.1145/2486001
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 August 2013
Published in SIGCOMM-CCR Volume 43, Issue 4

Check for updates

Author Tags

  1. analytics
  2. differential privacy
  3. xor cryptography

Qualifiers

  • Research-article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)134
  • Downloads (Last 6 weeks)24
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)ELSA: Secure Aggregation for Federated Learning with Malicious Actors2023 IEEE Symposium on Security and Privacy (SP)10.1109/SP46215.2023.10179468(1961-1979)Online publication date: May-2023
  • (2023)Privacy-preserving targeted mobile advertisingJournal of Network and Computer Applications10.1016/j.jnca.2022.103559211:COnline publication date: 1-Feb-2023
  • (2022)Achieving Private and Fair Truth Discovery in Crowdsourcing SystemsSecurity and Communication Networks10.1155/2022/92817292022Online publication date: 1-Jan-2022
  • (2022)Joint Optimization of Privacy and Cost of in-App Mobile User Profiling and Targeted AdsIEEE Access10.1109/ACCESS.2022.316615210(38664-38683)Online publication date: 2022
  • (2022)Web-based practical privacy-preserving distributed image storage for financial services in cloud computingWorld Wide Web10.1007/s11280-022-01090-726:3(1223-1241)Online publication date: 4-Aug-2022
  • (2020)Protecting Private Attributes in App Based Mobile User ProfilingIEEE Access10.1109/ACCESS.2020.30144248(143818-143836)Online publication date: 2020
  • (2018)SecSAKEProceedings of the 2018 on Asia Conference on Computer and Communications Security10.1145/3196494.3196513(537-550)Online publication date: 29-May-2018
  • (2017)PrioProceedings of the 14th USENIX Conference on Networked Systems Design and Implementation10.5555/3154630.3154652(259-282)Online publication date: 27-Mar-2017
  • (2017)SOMARProceedings of the 2017 on Workshop on Privacy in the Electronic Society10.1145/3139550.3139563(21-30)Online publication date: 30-Oct-2017
  • (2017)Enabling Privacy Preserving Mobile Advertising via Private Information Retrieval2017 IEEE 42nd Conference on Local Computer Networks (LCN)10.1109/LCN.2017.63(347-355)Online publication date: Oct-2017
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media