research-article

Accountable Private Set Cardinality for Distributed Measurement

Authors:

Micah SherrAuthors Info & Claims

ACM Transactions on Privacy and Security, Volume 25, Issue 4

Article No.: 25, Pages 1 - 35

https://doi.org/10.1145/3477531

Published: 21 July 2022 Publication History

Abstract

We introduce cryptographic protocols for securely and efficiently computing the cardinality of set union and set intersection. Our private set-cardinality protocols (PSC) are designed for the setting in which a large set of parties in a distributed system makes observations, and a small set of parties with more resources and higher reliability aggregates the observations. PSC allows for secure and useful statistics gathering in privacy-preserving distributed systems. For example, it allows operators of anonymity networks such as Tor to securely answer the questions: How many unique users are using the network? and How many hidden services are being accessed?

We prove the correctness and security of PSC in the Universal Composability framework against an active adversary that compromises all but one of the aggregating parties. Although successful output cannot be guaranteed in this setting, PSC either succeeds or terminates with an abort, and we furthermore make the adversary accountable for causing an abort by blaming at least one malicious party. We also show that PSC prevents adaptive corruption of the data parties from revealing past observations, which prevents them from being victims of targeted compromise, and we ensure safe measurements by making outputs differentially private.

We present a proof-of-concept implementation of PSC and use it to demonstrate that PSC operates with low computational overhead and reasonable bandwidth. It can count tens of thousands of unique observations from tens to hundreds of data-collecting parties while completing within hours. PSC is thus suitable for daily measurements in a distributed system.

References

[1]

Gilad Asharov and Yehuda Lindell. 2017. A full proof of the BGW protocol for perfectly secure multiparty computation. Journal of Cryptology 30, 1 (2017).

Digital Library

[2]

Carsten Baum, Emmanuela Orsini, and Peter Scholl. 2016. Efficient secure multiparty computation with identifiable abort. In Theory of Cryptography Conference (TCC’16).

Digital Library

[3]

Carsten Baum, Emmanuela Orsini, Peter Scholl, and Eduardo Soria-Vazquez. 2020. Efficient constant-round MPC with identifiable abort and public verifiability. In Annual International Cryptology Conference (Crypto’20).

Digital Library

[4]

Stephanie Bayer and Jens Groth. 2012. Efficient zero-knowledge argument for correctness of a shuffle. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt).

Digital Library

[5]

Mihir Bellare and Phillip Rogaway. 1993. Random oracles are practical: A paradigm for designing efficient protocols. In ACM Conference on Computer and Communications Security (CCS’93).

Digital Library

[6]

Josh Benaloh. 1994. Dense probabilistic encryption. In Workshop on Selected Areas of Cryptography (SAC’94).

[7]

Avrim Blum, Katrina Ligett, and Aaron Roth. 2013. A learning theory approach to noninteractive database privacy. Journal of the ACM (JACM’13) 60, 2 (2013).

[8]

Felix Brandt. 2005. Efficient cryptographic protocol design based on distributed El Gamal encryption. In International Conference on Information Security and Cryptology (ICISC’05).

[9]

Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Greg Maxwell. 2018. Bulletproofs: Short proofs for confidential transactions and more. In IEEE Symposium on Security and Privacy (S&P’18).

[10]

Jan Camenisch, Manu Drijvers, and Maria Dubovitskaya. 2017. Practical UC-secure delegatable credentials with attributes and their application to blockchain. In ACM Conference on Computer and Communications Security (CCS’17).

Digital Library

[11]

Ran Canetti. 2001. Universally composable security: A new paradigm for cryptographic protocols. In Foundations of Computer Science (FOCS’01).

[12]

Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, and Amit Sahai. 2002. Universally composable two-party and multi-party secure computation. In Symposium on Theory of Computing (STOC’02).

[13]

Seung Geol Choi, Dana Dachman-Soled, Mukul Kulkarni, and Arkady Yerukhimovich. 2020. Differentially-private multi-party sketching for large-scale statistics. Proceedings on Privacy Enhancing Technologies 3 (2020).

[14]

Ivan Damgård. 2010. On \(\Sigma\)-protocols. Lecture Notes on Cryptologic Protocol Theory, v.2.

[15]

Ivan Damgård, Valerio Pastro, Nigel Smart, and Sarah Zakarias. 2012. Multiparty computation from somewhat homomorphic encryption. In Annual International Cryptology Conference (Crypto).

Digital Library

[16]

Emiliano De Cristofaro, Paolo Gasti, and Gene Tsudik. 2012. Fast and private computation of cardinality of set intersection and union. In International Conference on Cryptology and Network Security (CANS’12).

[17]

Daniël de Kok. 2020. Go Par package for parallel for-loops. https://github.com/danieldk/par.

[18]

Roger Dingledine, Nick Mathewson, and Paul Syverson. 2004. Tor: The second-generation onion router. In USENIX Security Symposium (USENIX’04).

[19]

Danny Dolev and H. Raymond Strong. 1983. Authenticated algorithms for Byzantine agreement. SIAM J. Comput. 12, 4 (1983).

Digital Library

[20]

Marianne Durand and Philippe Flajolet. 2003. Loglog counting of large cardinalities. In European Symposium on Algorithms (ESA’03).

[21]

Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. 2006. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology (Eurocrypt’06).

[22]

Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference (TCC’06).

Digital Library

[23]

Cynthia Dwork, Aaron Roth, et al. 2014. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science 9, 3–4 (2014).

Digital Library

[24]

Rolf Egert, Marc Fischlin, David Gens, Sven Jacob, Matthias Senker, and Jörn Tillmanns. 2015. Privately computing set-union and set-intersection cardinality via Bloom filters. In Australasian Conference on Information Security and Privacy.

[25]

Tariq Elahi, George Danezis, and Ian Goldberg. 2014. PrivEx: Private collection of traffic statistics for anonymous communication networks. In ACM Conference on Computer and Communications Security (CCS’14).

Digital Library

[26]

Ellis Fenske, Akshaya Mani, Aaron Johnson, and Micah Sherr. 2017. Distributed measurement with private set-union cardinality. In ACM Conference on Computer and Communications Security (CCS’17). ACM.

Digital Library

[27]

Amos Fiat and Adi Shamir. 1987. How to prove yourself: Practical solutions to identification and signature problems. In Advances in Cryptology (CRYPTO’86).

[28]

Michael J. Freedman, Kobbi Nissim, and Benny Pinkas. 2004. Efficient private matching and set intersection. In Advances in Cryptology (Eurocrypt’04).

[29]

Jun Furukawa, Hiroshi Miyauchi, Kengo Mori, Satoshi Obana, and Kazue Sako. 2003. An implementation of a universally verifiable electronic voting scheme based on shuffling. In Financial Cryptography (FC’02).

[30]

O. Goldreich. 2001. Foundations of Cryptography: Volume 2, Basic Applications. Cambridge University Press.

[31]

Oded Goldreich, Silvio Micali, and Avi Wigderson. 1987. How to play ANY mental game. In ACM Symposium on Theory of Computing (STOC’87).

[32]

Oded Goldreich and Yair Oren. 1994. Definitions and properties of zero-knowledge proof systems. Journal of Cryptology 7, 1 (1994).

Digital Library

[33]

Jens Groth. 2003. A verifiable secret shuffle of homomorphic encryptions. In Theory and Practice in Public Key Cryptography (PKC’03).

[34]

Jens Groth, Rafail Ostrovsky, and Amit Sahai. 2006. Perfect non-interactive zero knowledge for NP. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’06).

Digital Library

[35]

Carmit Hazay, Gert Læssøe Mikkelsen, Tal Rabin, Tomas Toft, and Angelo Agatino Nicolosi. 2012. Efficient RSA key generation and threshold Paillier in the two-party setting. In Topics in Cryptology – CT-RSA.

[36]

Carmit Hazay and Kobbi Nissim. 2012. Efficient set operations in the presence of malicious adversaries. Journal of Cryptology 25, 3 (2012).

Digital Library

[37]

Ali Inan, Murat Kantarcioglu, Gabriel Ghinita, and Elisa Bertino. 2010. Private record matching using differential privacy. In International Conference on Extending Database Technology.

Digital Library

[38]

Yuval Ishai, Rafail Ostrovsky, and Vassilis Zikas. 2014. Secure multi-party computation with identifiable abort. In Annual Cryptology Conference (CRYPTO’14).

[39]

Rob Jansen and Aaron Johnson. 2016. Safely measuring Tor. In ACM Conference on Computer and Communications Security (CCS’16).

Digital Library

[40]

Shiva P. Kasiviswanathan and Adam Smith. 2014. On the ‘semantics’ of differential privacy: A Bayesian formulation. Journal of Privacy and Confidentiality 6, 1 (2014).

[41]

Jonathan Katz, Ueli Maurer, Björn Tackmann, and Vassilis Zikas. 2013. Universally composable synchronous computation. In Theory of Cryptography Conference (TCC’13).

Digital Library

[42]

Aggelos Kiayias, Hong-Sheng Zhou, and Vassilis Zikas. 2016. Fair and robust multi-party computation using a global transaction ledger. In Advances in Cryptology (EUROCRYPT’16).

[43]

Lea Kissner and Dawn Song. 2005. Privacy-preserving set operations. In Annual International Cryptology Conference (Crypto’05).

[44]

kyber. 2020. kyber: DEDIS Advanced Crypto Library for Go. https://godoc.org/go.dedis.ch/kyber.

[45]

Enrique Larraia, Emmanuela Orsini, and Nigel P. Smart. 2014. Dishonest majority multi-party computation for binary circuits. In Annual International Cryptology Conference (Crypto’14).

[46]

Yehida Lindell. 2005. Secure multiparty computation for privacy preserving data mining. In Encyclopedia of Data Warehousing and Mining. 1005–1009.

[47]

Yehuda Lindell. 2015. An efficient transform from sigma protocols to NIZK with a CRS and non-programmable random oracle. In Theory of Cryptography (TCC’15).

[48]

Yehuda Lindell, Benny Pinkas, Nigel P. Smart, and Avishay Yanai. 2015. Efficient constant round multi-party computation combining BMR and SPDZ. In Annual Cryptology Conference (Crypto’15).

Digital Library

[49]

Akshaya Mani and M. Sherr. 2017. Histor\(\epsilon\): Differentially private and robust statistics collection for Tor. In Network and Distributed System Security Symposium (NDSS’17).

[50]

Damon McCoy, Kevin Bauer, Dirk Grunwald, Tadayoshi Kohno, and Douglas Sicker. 2008. Shining light in dark places: Understanding the Tor network. In Privacy Enhancing Technologies Symposium (PETS’08).

[51]

Frank McSherry and Kunal Talwar. 2007. Mechanism design via differential privacy. In Foundations of Computer Science (FOCS’07).

[52]

Luca Melis, George Danezis, and Emiliano De Cristofaro. 2016. Efficient private statistics with succinct sketches. In Network and Distributed System Security Symposium (NDSS’16).

[53]

C. Andrew Neff. 2001. A verifiable secret shuffle and its application to e-voting. In ACM Conference on Computer and Communications Security (CCS’01).

Digital Library

[54]

Lan Nguyen, Rei Safavi-Naini, and Kaoru Kurosawa. 2004. Verifiable shuffles: A formal model and a Paillier-based efficient construction with provable security. In Applied Cryptography and Network Security (ACNS’04).

[55]

Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. 2007. Smooth sensitivity and sampling in private data analysis. In Symposium on Theory of Computing (STOC’07).

[56]

Craig Partridge and Mark Allman. 2016. Ethical considerations in network measurement papers. Commun. ACM 59, 10 (2016).

Digital Library

[57]

Martin Pettai and Peeter Laud. 2015. Combining differential privacy and secure multiparty computation. In Annual Computer Security Applications Conference (ACSAC’15).

Digital Library

[58]

Shai Halevi, Ran Canetti, and Oded Goldreich. 2004. The random oracle methodology, revisited. Journal of the ACM (JACM’04) 51, 4 (2004).

[59]

Claus-Peter Schnorr. 1991. Efficient signature generation by smart cards. Journal of Cryptology 4, 3 (1991).

Digital Library

[60]

Christopher Soghoian. 2011. Enforced community standards for research on users of the Tor anonymity network. In Workshop on Ethics in Computer Security Research (WECSR’11).

[61]

Rade Stanojevic, Mohamed Nabeel, and Ting Yu. 2017. Distributed cardinality estimation of set operations with differential privacy. In IEEE Symposium on Privacy-Aware Computing (PAC’17).

[62]

Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan. 2001. Chord: A scalable peer-to-peer lookup service for internet applications. In Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM’01).

Digital Library

[63]

Rene Struik. 2021. Alternative Elliptic Curve Representations. Internet-Draft draft-ietf-lwig-curve-representations-20. Internet Engineering Task Force. Work in Progress.

[64]

Tor Metrics. 2020. https://metrics.torproject.org/.

[65]

Jaideep Vaidya and Chris Clifton. 2005. Secure set intersection cardinality with application to association rule mining. Journal of Computer Security 13, 4 (2005).

Digital Library

[66]

Kenton Varda. 2008. Protocol Buffers: Google’s Data Interchange Format. https://opensource.googleblog.com/2008/07/protocol-buffers-googles-data.html.

[67]

Ryan Wails, Aaron Johnson, Daniel Starin, Arkady Yerukhimovich, and S. Dov Gordon. 2019. Stormy: Statistics in Tor by measuring securely. ACM Conference on Computer and Communications Security (CCS’19).

[68]

Xiao Wang, Samuel Ranellucci, and Jonathan Katz. 2017. Global-scale secure multiparty computation. In ACM Conference on Computer and Communications Security (CCS’17).

Digital Library

[69]

Douglas Wikström. 2005. A sender verifiable mix-net and a new proof of a shuffle. In International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT’05).

Digital Library

Cited By

Cheng BChen PZhang XFang KQin XLiu W(2023)Personalized Privacy Protection-Preserving Collaborative Filtering Algorithm for Recommendation SystemsApplied Sciences10.3390/app1307460013:7(4600)Online publication date: 5-Apr-2023
https://doi.org/10.3390/app13074600
Wang PYang CXie DZhao JLi HTao JGuan X(2023)An Effective and Differentially Private Protocol for Secure Distributed Cardinality EstimationProceedings of the ACM on Management of Data10.1145/35889141:1(1-24)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.1145/3588914

Index Terms

Accountable Private Set Cardinality for Distributed Measurement
1. Security and privacy
  1. Cryptography
  2. Network security
    1. Security protocols

Recommendations

Distributed Measurement with Private Set-Union Cardinality
CCS '17: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security

This paper introduces a cryptographic protocol for efficiently aggregating a count of unique items across a set of data parties privately - that is, without exposing any information other than the count. Our protocol allows for more secure and useful ...
Efficient Batched Oblivious PRF with Applications to Private Set Intersection
CCS '16: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security

We describe a lightweight protocol for oblivious evaluation of a pseudorandom function (OPRF) in the presence of semihonest adversaries. In an OPRF protocol a receiver has an input r; the sender gets output s and the receiver gets output F(s; r), where ...
What Security Can We Achieve Within 4 Rounds?
Abstract
Katz and Ostrovsky (Crypto 2004) proved that five rounds are necessary for stand-alone general black-box constructions of secure two-party protocols and at least four rounds are necessary if only one party needs to receive the output. Recently, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Privacy and Security

ACM Transactions on Privacy and Security Volume 25, Issue 4

November 2022

330 pages

ISSN:2471-2566

EISSN:2471-2574

DOI:10.1145/3544004

Editor:
Ninghui Li
Purdue University, USA

Issue’s Table of Contents

Publication rights licensed to ACM. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of the United States government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 July 2022

Online AM: 27 April 2022

Accepted: 01 July 2021

Received: 01 February 2021

Published in TOPS Volume 25, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Refereed

Funding Sources

National Science Foundation
Canada Research Chairs program, the Office of Naval Research

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
365
Total Downloads

Downloads (Last 12 months)58
Downloads (Last 6 weeks)11

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cheng BChen PZhang XFang KQin XLiu W(2023)Personalized Privacy Protection-Preserving Collaborative Filtering Algorithm for Recommendation SystemsApplied Sciences10.3390/app1307460013:7(4600)Online publication date: 5-Apr-2023
https://doi.org/10.3390/app13074600
Wang PYang CXie DZhao JLi HTao JGuan X(2023)An Effective and Differentially Private Protocol for Secure Distributed Cardinality EstimationProceedings of the ACM on Management of Data10.1145/35889141:1(1-24)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.1145/3588914

View Options

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Full Text

View this article in Full Text.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View full text|Download PDF

View Issue’s Table of Contents