research-article

Free access

SplitX: high-performance private analytics

Authors:

Istemi Ekin Akkus,

Paul FrancisAuthors Info & Claims

SIGCOMM '13: Proceedings of the ACM SIGCOMM 2013 conference on SIGCOMM

Pages 315 - 326

https://doi.org/10.1145/2486001.2486013

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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[9]

R. Chen, A. Reznichenko, P. Francis, and J. Gehrke. Towards Statistical Queries over Distributed Private User Data. In NSDI, 2012.

Digital Library

[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.

Digital Library

[11]

C. Dwork. Differential Privacy. In ICALP, 2006.

Digital Library

[12]

C. Dwork. Differential Privacy: A Survey of Results. In TAMC, 2008.

Digital Library

[13]

C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor. Our Data, Ourselves: Privacy Via Distributed Noise Generation. In EUROCRYPT, 2006.

Digital Library

[14]

C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating Noise to Sensitivity in Private Data Analysis. In TCC, 2006.

Digital Library

[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.

Digital Library

[17]

S. Goldwasser and S. Micali. Probabilistic Encryption and How to Play Mental Poker Keeping Secret All Partial Information. In STOC, 1982.

Digital Library

[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.

Digital Library

[20]

M. Hardt and S. Nath. Privacy-aware personalization for mobile advertising. In CCS, 2012.

Digital Library

[21]

S. Katti, J. Cohen, and D. Katabi. Information Slicing: Anonymity Using Unreliable Overlays. In NSDI, 2007.

Digital Library

[22]

A. Machanavajjhala, J. Gehrke, D. Kifer, and M. Venkitasubramaniam. l-Diversity: Privacy Beyond k-Anonymity. In ICDE, 2006.

Digital Library

[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.

Digital Library

[25]

K. P. N. Puttaswamy, R. Bhagwan, and V. N. Padmanabhan. Anonygator: Privacy and Integrity Preserving Data Aggregation. In Middleware, 2010.

Digital Library

[26]

V. Rastogi and S. Nath. Differentially private aggregation of distributed time-series with transformation and encryption. In SIGMOD, 2010.

Digital Library

[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.

Digital Library

[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.

Digital Library

[30]

D. X. Song, D. Wagner, and A. Perrig. Practical Techniques for Searches on Encrypted Data. In IEEE Symposium on Security and Privacy, 2000.

Digital Library

[31]

L. Sweeney. k-Anonymity: A Model for Protecting Privacy. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 10(5):557--570, 2002.

Digital Library

[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.

Digital Library

Cited By

Li HMao RLi JLiu CLi JGuo Y(2024)Detonation Decision Support System Based on Rapid Damage Effectiveness Evaluation2024 IEEE International Conference on Unmanned Systems (ICUS)10.1109/ICUS61736.2024.10840049(627-635)Online publication date: 18-Oct-2024
https://doi.org/10.1109/ICUS61736.2024.10840049
Fei XZhao HCheng YTian J(2024)Research on the Impact Calculation of Penetrators on Typical Metal Protective Structures Based on Unity3D2024 5th International Conference on Computer Engineering and Intelligent Control (ICCEIC)10.1109/ICCEIC64099.2024.10775765(42-46)Online publication date: 11-Oct-2024
https://doi.org/10.1109/ICCEIC64099.2024.10775765
Rathee MShen CWagh SPopa R(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
https://doi.org/10.1109/SP46215.2023.10179468
Show More Cited By

Index Terms

SplitX: high-performance private analytics

Recommendations

SplitX: high-performance private analytics

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 ...
A privacy framework: indistinguishable privacy
EDBT '13: Proceedings of the Joint EDBT/ICDT 2013 Workshops

In this paper we illustrate a privacy framework named Indistinguishable Privacy. Indistinguishable privacy could be deemed as the formalization of the existing privacy definitions in privacy preserving data publishing as well as secure multi-party ...
Protecting sensitive place visits in privacy-preserving trajectory publishing
Highlights
- We propose a method for privacy-preserving trajectory publishing.
- It aims at ...
Abstract
The rise of mobile computing has generated huge amount of trajectory data. Since these data are valuable for many people, publishing them while providing adequate individual privacy protection has been a challenging task. In this paper,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

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

General Chairs:
Dah Ming Chiu
Chinese University of Hong Kong, China
,
Jia Wang
AT&T Labs - Research, USA
,
Program Chairs:
Paul Barford
University of Wisconsin, USA
,
Srinivasan Seshan
Carnegie Mellon University, USA

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

Copyright © 2013 ACM.

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]

Sponsors

SIGCOMM: ACM Special Interest Group on Data Communication

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 August 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGCOMM'13

Sponsor:

SIGCOMM

SIGCOMM'13: ACM SIGCOMM 2013 Conference

August 12 - 16, 2013

Hong Kong, China

Acceptance Rates

SIGCOMM '13 Paper Acceptance Rate 38 of 246 submissions, 15%;

Overall Acceptance Rate 462 of 3,389 submissions, 14%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

37
Total Citations
View Citations
680
Total Downloads

Downloads (Last 12 months)129
Downloads (Last 6 weeks)24

Reflects downloads up to 27 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Li HMao RLi JLiu CLi JGuo Y(2024)Detonation Decision Support System Based on Rapid Damage Effectiveness Evaluation2024 IEEE International Conference on Unmanned Systems (ICUS)10.1109/ICUS61736.2024.10840049(627-635)Online publication date: 18-Oct-2024
https://doi.org/10.1109/ICUS61736.2024.10840049
Fei XZhao HCheng YTian J(2024)Research on the Impact Calculation of Penetrators on Typical Metal Protective Structures Based on Unity3D2024 5th International Conference on Computer Engineering and Intelligent Control (ICCEIC)10.1109/ICCEIC64099.2024.10775765(42-46)Online publication date: 11-Oct-2024
https://doi.org/10.1109/ICCEIC64099.2024.10775765
Rathee MShen CWagh SPopa R(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
https://doi.org/10.1109/SP46215.2023.10179468
Ullah IBoreli RKanhere S(2022)Privacy in targeted advertising on mobile devices: a surveyInternational Journal of Information Security10.1007/s10207-022-00655-x22:3(647-678)Online publication date: 24-Dec-2022
https://doi.org/10.1007/s10207-022-00655-x
Zheng YDuan HYuan XWang C(2020)Privacy-Aware and Efficient Mobile Crowdsensing with Truth DiscoveryIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2017.275324517:1(121-133)Online publication date: 1-Jan-2020
https://doi.org/10.1109/TDSC.2017.2753245
Primault VLampos VCox IDe Cristofaro E(2019)Privacy-Preserving Crowd-Sourcing of Web Searches with Private Data DonorThe World Wide Web Conference10.1145/3308558.3313474(1487-1497)Online publication date: 13-May-2019
https://dl.acm.org/doi/10.1145/3308558.3313474
Quoc DBeck MBhatotia PChen RFetzer CStrufe T(2019)Privacy-Preserving Data AnalyticsEncyclopedia of Big Data Technologies10.1007/978-3-319-77525-8_152(1292-1300)Online publication date: 20-Feb-2019
https://doi.org/10.1007/978-3-319-77525-8_152
Maffei MMalavolta GReinert MSchröder D(2018)Group ORAM for privacy and access control in outsourced personal recordsJournal of Computer Security10.3233/JCS-17103027:1(1-47)Online publication date: 26-Oct-2018
https://doi.org/10.3233/JCS-171030
Wang SChang J(2018)Differentially Private Principal Component Analysis Over Horizontally Partitioned Data2018 IEEE Conference on Dependable and Secure Computing (DSC)10.1109/DESEC.2018.8625131(1-8)Online publication date: Dec-2018
https://doi.org/10.1109/DESEC.2018.8625131
Quoc DBeck MBhatotia PChen RFetzer CStrufe T(2018)Privacy-Preserving Data AnalyticsEncyclopedia of Big Data Technologies10.1007/978-3-319-63962-8_152-1(1-8)Online publication date: 1-Feb-2018
https://doi.org/10.1007/978-3-319-63962-8_152-1
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten