skip to main content
10.1145/3064176.3064218acmconferencesArticle/Chapter ViewAbstractPublication PageseurosysConference Proceedingsconference-collections
research-article
Public Access

DStress: Efficient Differentially Private Computations on Distributed Data

Published: 23 April 2017 Publication History

Abstract

In this paper, we present DStress, a system that can efficiently perform computations on graphs that contain confidential data. DStress assumes that the graph is physically distributed across many participants, and that each participant only knows a small subgraph; it protects privacy by enforcing tight, provable limits on how much each participant can learn about the rest of the graph.
We also study one concrete instance of this problem: measuring systemic risk in financial networks. Systemic risk is the likelihood of cascading bankruptcies -- as, e.g., during the financial crisis of 2008 -- and it can be quantified based on the dependencies between financial institutions; however, the necessary data is highly sensitive and cannot be safely disclosed. We show that DStress can implement two different systemic risk models from the theoretical economics literature. Our experimental evaluation suggests that DStress can run the corresponding computations in about five hours, whereas a naïve approach could take several decades.

References

[1]
E. A. Abbe, A. E. Khandani, and A. W. Lo. Privacy-preserving methods for sharing financial risk exposures. The American Economic Review, 102(3):65--70, 2012.
[2]
Bank for International Settlements. International regulatory framework for banks (Basel III) website. http://www.bis.org/bcbs/basel3.htm.
[3]
M. Barbaro, T. Zeller, and S. Hansell. A face is exposed for AOL searcher No. 4417749. New York Times, Aug 9, 2006.
[4]
G. Barthe, B. Köpf, F. Olmedo, and S. Zanella-Béguelin. Probabilistic relational reasoning for differential privacy. In Proc. POPL, 2013.
[5]
A. Beimel, K. Nissim, and E. Omri. Distributed private data analysis: Simultaneously solving how and what. In Proc. CRYPTO, 2008.
[6]
R. M. Bell and Y. Koren. Lessons from the Netflix prize challenge. ACM SIGKDD Explorations Newsletter, 9(2):75--79, 2007.
[7]
A. Ben-David, N. Nisan, and B. Pinkas. FairplayMP: A system for secure multi-party computation. In Proc. ACM CCS, 2008.
[8]
M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In Proc. STOC, 1988.
[9]
D. Bisias, M. Flood, A. W. Lo, and S. Valavanis. A survey of systemic risk analytics. Annu. Rev. Financ. Econ., 4(1):255--296, 2012.
[10]
J. Blocki, A. Blum, A. Datta, and O. Sheffet. Differentially private data analysis of social networks via restricted sensitivity. In Proc. ITCS, 2013.
[11]
Board of Governors of the Federal Reserve System. Dodd-Frank Act Stress Test 2015: Supervisory stress test methodology and results, Mar. 2015. http://www.federalreserve.gov/newsevents/press/bcreg/bcreg20150305a1.pdf.
[12]
D. Bogdanov, S. Laur, and J. Willemson. Sharemind: A framework for fast privacy-preserving computations. In Proc. ESORICS, 2008.
[13]
R. Bookstaber, J. Cetina, G. Feldberg, M. Flood, and P. Glasserman. Stress tests to promote financial stability: Assessing progress and looking to the future. Journal of Risk Management in Financial Institutions, 7(1):16--25, 2014.
[14]
S. P. Borgatti, A. Mehra, D. J. Brass, and G. Labianca. Network analysis in the social sciences. Science, 323(5916):892--895, 2009.
[15]
M. Burkhart, M. Strasser, D. Many, and X. Dimitropoulos. SEPIA: Privacy-preserving aggregation of multi-domain network events and statistics. In Proc. USENIX Security, 2010.
[16]
R. Chen, A. Reznichenko, P. Francis, and J. Gehrke. Towards statistical queries over distributed private user data. In Proc. NSDI, 2012.
[17]
S. G. Choi, K.-W. Hwang, J. Katz, T. Malkin, and D. Rubenstein. Secure multi-party computation of boolean circuits with applications to privacy in on-line marketplaces. In Proc. CTRSA. Springer, 2012.
[18]
J. F. Cocco, F. J. Gomes, and N. C. Martins. Lending relationships in the interbank market. Journal of Financial Intermediation, 18(1):24--48, 2009.
[19]
R. Cramer, R. Gennaro, and B. Schoenmakers. A secure and optimally efficient multi-authority election scheme. Transactions on Emerging Telecommunications Technologies, 8(5):481--490, 1997.
[20]
I. Damgård, M. Geisler, M. Krøigaard, and J. B. Nielsen. Asynchronous multiparty computation: Theory and implementation. In PKC, 2009.
[21]
Y. Dodis, I. Mironov, and N. Stephens-Davidowitz. Message transmission with reverse firewalls---secure communication on corrupted machines. Technical report, Cryptology ePrint Archive, Report 2015/548, 2015. http://eprint.iacr.org/2015/548, 2015.
[22]
C. Dwork. Differential privacy: A survey of results. In Proc. TAMC, 2008.
[23]
C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor. Our data, ourselves: Privacy via distributed noise generation. In Proc. EUROCRYPT, 2006.
[24]
C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference (TCC), 2006.
[25]
L. Eisenberg and T. H. Noe. Systemic risk in financial systems. Management Science, 47(2):236--249, 2001.
[26]
T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE transactions on information theory, 31(4):469--472, 1985.
[27]
M. Elliott, B. Golub, and M. O. Jackson. Financial networks and contagion. The American economic review, 104(10):3115--3153, 2014.
[28]
J. Fantuzzo and D. P. Culhane. Actionable intelligence: Using integrated data systems to achieve a more effective, efficient, and ethical government. Palgrave Macmillan, 2015.
[29]
Federal Deposit Insurance Corporation (FDIC). Dodd-Frank Act Stress Test. February 17, 2017; https://www.fdic.gov/regulations/reform/dfast/index.html.
[30]
M. Flood, J. Katz, S. Ong, and A. Smith. Cryptography and the economics of supervisory information: Balancing transparency and confidentiality. U.S. Department of Treasury Office of Financial Research Working Paper Series, 1(11), 2013.
[31]
M. Gaboardi, A. Haeberlen, J. Hsu, A. Narayan, and B. C. Pierce. Linear dependent types for differential privacy. In Proc. POPL, 2013.
[32]
C. Gentry, S. Halevi, and V. Vaikuntanathan. i-hop homomorphic encryption and rerandomizable yao circuits. In CRYPTO, 2010.
[33]
A. Ghosh, T. Roughgarden, and M. Sundararajan. Universally utility-maximizing privacy mechanisms. SIAM Journal on Computing, 41(6):1673--1693, 2012.
[34]
O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game. In Proc. STOC, 1987.
[35]
J. E. Gonzalez, Y. Low, H. Gu, D. Bickso, and C. Guestrin. PowerGraph: Distributed graph-parallel computation on natural graphs. In Proc. OSDI, 2012.
[36]
J. E. Gonzalez, R. S. Xin, A. Dave, D. Crankshaw, M. J. Franklin, and I. Stoica. GraphX: Graph processing in a distributed dataflow framework. In Proc. OSDI, 2014.
[37]
J. Groth. Rerandomizable and replayable adaptive chosen ciphertext attack secure cryptosystems. In Theory of Cryptography, 2004.
[38]
A. Haeberlen, B. C. Pierce, and A. Narayan. Differential privacy under fire. In Proc. USENIX Security, 2011.
[39]
B. Hemenway and S. Khanna. Sensitivity and computational complexity in financial networks. In submission; manuscript available from http://www.cis.upenn.edu/~sanjeev/papers/financial_network.pdf, 2015.
[40]
J. Hsu, M. Gaboardi, A. Haeberlen, S. Khanna, A. Narayan, B. C. Pierce, and A. Roth. Differential privacy: An economic method for choosing epsilon. In Proc. IEEE CSF, 2014.
[41]
Y. Ishai, J. Kilian, K. Nissim, and E. Petrank. Extending oblivious transfers efficiently. In Proc. CRYPTO, 2003.
[42]
V. Karwa, S. Raskhodnikova, A. Smith, and G. Yaroslavtsev. Private analysis of graph structure. Proc. VLDB Endowment, 4(11):1146--1157, 2011.
[43]
V. E. Krebs. Mapping networks of terrorist cells. Connections, 24(3):43--52, 2002.
[44]
K. Kurosawa. Multi-recipient public-key encryption with shortened ciphertext. In PKC, 2002.
[45]
D. Lazer, A. Pentland, L. Adamic, S. Aral, A.-L. Barabási, D. Brewer, N. Christakis, N. Contractor, J. Fowler, M. Gutmann, T. Jebara, G. King, M. Macy, D. Roy, and M. Van Alstyne. Computational social science. Science, 323(5915):721--723, 2009.
[46]
B. Li, H. Li, G. Xu, and H. Xu. Efficient reduction of 1 out of n oblivious transfers in random oracle model. IACR Cryptology ePrint Archive, 2005:279, 2005.
[47]
Y. Low, J. E. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, and J. M. Hellerstein. GraphLab: A new framework for parallel machine learning. In Proc. UAI, 2010.
[48]
G. Malewicz, M. H. Austern, A. J. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski. Pregel: A system for large-scale graph processing. In Proc. SIGMOD, 2010.
[49]
F. McSherry. Privacy integrated queries. In Proc. SIGMOD, 2009.
[50]
I. Mironov, O. Pandey, O. Reingold, and S. Vadhan. Computational differential privacy. In Proc. CRYPTO, 2009.
[51]
A. Narayan and A. Haeberlen. DJoin: Differentially private join queries over distributed databases. In Proc. OSDI, 2012.
[52]
A. Narayan, A. Papadimitriou, and A. Haeberlen. Compute globally, act locally: Protecting federated systems from systemic threats. In Proc. HotDep, 2014.
[53]
A. Narayanan and V. Shmatikov. Robust de-anonymization of large sparse datasets. In Proc. IEEE S&P, 2008.
[54]
National Information Center of the Federal Reserve System. Insured U.S. chartered commercial banks that have consolidated assets of $300 million or more. http://www.federalreserve.gov/releases/lbr/current/default.htm, 2014.
[55]
K. Nayak, X. S. Wang, S. Ioannidis, U. Weinsberg, N. Taft, and E. Shi. GraphSC: Parallel secure computation made easy. In Proc. IEEE S&P, 2015.
[56]
V. Nikolaenko, S. Ioannidis, U. Weinsberg, M. Joye, N. Taft, and D. Boneh. Privacy-preserving matrix factorization. In Proc. ACM CCS, 2013.
[57]
A. Papadimitriou, A. Narayan, and A. Haeberlen. DStress: Efficient differentially private computations on distributed data. Technical Report MS-CIS-17-03, University of Pennsylvania, 2017.
[58]
D. Proserpio, S. Goldberg, and F. McSherry. Calibrating data to sensitivity in private data analysis: A platform for differentially-private analysis of weighted datasets. In Proc. VLDB, 2014.
[59]
A. Rastogi, M. A. Hammer, and M. Hicks. Wysteria: A programming language for generic, mixed-mode multiparty computations. In Proc. IEEE S&P, 2014.
[60]
N. Raymond and A. Viswanatha. U.S. regulator sues 16 banks for rigging Libor rate. Reuters, March 14, 2014; http://www.reuters.com/article/2014/03/14/us-fdic-libor-idUSBREA2D1KR20140314.
[61]
I. Roy, S. Setty, A. Kilzer, V. Shmatikov, and E. Witchel. Airavat: Security and privacy for MapReduce. In Proc. NSDI, 2010.
[62]
M. K. Sparrow. The application of network analysis to criminal intelligence: An assessment of the prospects. Social networks, 13(3):251--274, 1991.
[63]
A. Yao. Protocols for secure computations. In Proc. FOCS, 1982.
[64]
E. Zhai, R. Chen, D. I. Wolinsky, and B. Ford. Heading off correlated failures through independence-as-a-service. In Proc. OSDI, 2014.
[65]
Y. Zhang, A. Steele, and M. Blanton. Picco: A generalpurpose compiler for private distributed computation. In Proc. ACM CCS, 2013.

Cited By

View all
  • (2025)Outsourcing collaboration analysis of multiparty privacy data using the improved YannakakisThe Journal of Supercomputing10.1007/s11227-025-06994-581:3Online publication date: 14-Feb-2025
  • (2024)SecretFlow-SCQL: A Secure Collaborative Query PlatformProceedings of the VLDB Endowment10.14778/3685800.368582117:12(3987-4000)Online publication date: 8-Nov-2024
  • (2024)Shortcut: Making MPC-based Collaborative Analytics Efficient on Dynamic DatabasesProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690314(854-868)Online publication date: 2-Dec-2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
EuroSys '17: Proceedings of the Twelfth European Conference on Computer Systems
April 2017
648 pages
ISBN:9781450349383
DOI:10.1145/3064176
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 the author(s) 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 April 2017

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Research-article
  • Research
  • Refereed limited

Funding Sources

Conference

EuroSys '17
Sponsor:
EuroSys '17: Twelfth EuroSys Conference 2017
April 23 - 26, 2017
Belgrade, Serbia

Acceptance Rates

Overall Acceptance Rate 241 of 1,308 submissions, 18%

Upcoming Conference

EuroSys '25
Twentieth European Conference on Computer Systems
March 30 - April 3, 2025
Rotterdam , Netherlands

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

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

Other Metrics

Citations

Cited By

View all
  • (2025)Outsourcing collaboration analysis of multiparty privacy data using the improved YannakakisThe Journal of Supercomputing10.1007/s11227-025-06994-581:3Online publication date: 14-Feb-2025
  • (2024)SecretFlow-SCQL: A Secure Collaborative Query PlatformProceedings of the VLDB Endowment10.14778/3685800.368582117:12(3987-4000)Online publication date: 8-Nov-2024
  • (2024)Shortcut: Making MPC-based Collaborative Analytics Efficient on Dynamic DatabasesProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690314(854-868)Online publication date: 2-Dec-2024
  • (2024)Making Privacy-preserving Federated Graph Analytics Practical (for Certain Queries)Proceedings of the 29th ACM Symposium on Access Control Models and Technologies10.1145/3649158.3657047(31-39)Online publication date: 24-Jun-2024
  • (2024)Periscoping: Private Key Distribution for Large-Scale MixnetsIEEE INFOCOM 2024 - IEEE Conference on Computer Communications10.1109/INFOCOM52122.2024.10621274(681-690)Online publication date: 20-May-2024
  • (2023)TPMDP: Threshold Personalized Multi-party Differential Privacy via Optimal Gaussian Mechanism2023 IEEE 20th International Conference on Mobile Ad Hoc and Smart Systems (MASS)10.1109/MASS58611.2023.00027(161-169)Online publication date: 25-Sep-2023
  • (2021)MyceliumProceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles10.1145/3477132.3483585(327-343)Online publication date: 26-Oct-2021
  • (2021)Differentially Private Publication of Vertically Partitioned DataIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2019.290523718:2(780-795)Online publication date: 1-Mar-2021
  • (2020)OrchardProceedings of the 14th USENIX Conference on Operating Systems Design and Implementation10.5555/3488766.3488826(1065-1081)Online publication date: 4-Nov-2020
  • (2019)Cheaper Private Set Intersection via Differentially Private LeakageProceedings on Privacy Enhancing Technologies10.2478/popets-2019-00342019:3(6-25)Online publication date: 12-Jul-2019
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media