Skip to main content
SpringerLink
Log in
Book cover

Australasian Conference on Information Security and Privacy

ACISP 2015: Information Security and Privacy pp 413–430Cite as

Privately Computing Set-Union and Set-Intersection Cardinality via Bloom Filters

  • Conference paper
  • First Online:

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 9144))

Abstract

In this paper we propose a new approach to privately compute the set-union cardinality and the set-intersection cardinality among multiple honest-but-curious parties. Our approach is inspired by a proposal of Ashok and Mukkamala (DBSec’14) which deploys Bloom filters to approximate the size tightly. One advantage of their solution is that it avoids ample public-key cryptography. Unfortunately, we show here that their protocol is vulnerable to actual attacks. We therefore propose a new Bloom filter based protocol, also forgoing heavy cryptography, and prove its security.

This is a preview of subscription content, log in via an institution.

Chapter
USD   29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD   39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD   54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Learn about institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Ashok, V.G., Mukkamala, R.: A scalable and efficient privacy preserving global itemset support approximation using bloom filters. In: Atluri, V., Pernul, G. (eds.) DBSec 2014. LNCS, vol. 8566, pp. 382–389. Springer, Heidelberg (2014)

    Google Scholar 

  2. Blanton, M., Aguiar, E.: Private and oblivious set and multiset operations. In: Youm, H.Y., Won, Y. (eds.) ASIACCS 2012, pp. 40–41. ACM Press, May 2012

    Google Scholar 

  3. Bloom, B.H.: Space/time trade-offs in hash coding with allowable errors. Communications of the ACM 13(7), 422–426 (1970)

    Article  MATH  Google Scholar 

  4. De Cristofaro, E., Gasti, P., Tsudik, G.: Fast and private computation of cardinality of set intersection and union. In: Pieprzyk, J., Sadeghi, A.-R., Manulis, M. (eds.) CANS 2012. LNCS, vol. 7712, pp. 218–231. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

  5. Dachman-Soled, D., Malkin, T., Raykova, M., Yung, M.: Efficient robust private set intersection. In: Abdalla, M., Pointcheval, D., Fouque, P.-A., Vergnaud, D. (eds.) ACNS 2009. LNCS, vol. 5536, pp. 125–142. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  6. De Cristofaro, E., Kim, J., Tsudik, G.: Linear-complexity private set intersection protocols secure in malicious model. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 213–231. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  7. De Cristofaro, E., Tsudik, G.: Practical private set intersection protocols with linear complexity. In: Sion, R. (ed.) FC 2010. LNCS, vol. 6052, pp. 143–159. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  8. Dong, C., Chen, L., Wen, Z.: When private set intersection meets big data: an efficient and scalable protocol. In: Sadeghi, A.R., Gligor, V.D., Yung, M. (eds.) ACM CCS 2013, pp. 789–800. ACM Press, November 2013

    Google Scholar 

  9. Fischlin, M., Pinkas, B., Sadeghi, A.-R., Schneider, T., Visconti, I.: Secure set intersection with untrusted hardware tokens. In: Kiayias, A. (ed.) CT-RSA 2011. LNCS, vol. 6558, pp. 1–16. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  10. Freedman, M.J., Ishai, Y., Pinkas, B., Reingold, O.: Keyword search and oblivious pseudorandom functions. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 303–324. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  11. Freedman, M.J., Nissim, K., Pinkas, B.: Efficient private matching and set intersection. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 1–19. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  12. Frikken, K.B.: Privacy-preserving set union. In: Katz, J., Yung, M. (eds.) ACNS 2007. LNCS, vol. 4521, pp. 237–252. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  13. Goldreich, O.: The Foundations of Cryptography, vol. 2. Cambridge University Press (2004)

    Google Scholar 

  14. Hazay, C.: Oblivious polynomial evaluation and secure set-intersection from algebraic PRFs. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part II. LNCS, vol. 9015, pp. 90–120. Springer, Heidelberg (2015)

    Google Scholar 

  15. Hazay, C., Lindell, Y.: Constructions of truly practical secure protocols using standardsmartcards. In: Ning, P., Syverson, P.F., Jha, S. (eds.) ACM CCS 2008, pp. 491–500. ACM Press, October 2008

    Google Scholar 

  16. Hazay, C., Lindell, Y.: Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries. Journal of Cryptology 23(3), 422–456 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  17. Hazay, C., Nissim, K.: Efficient set operations in the presence of malicious adversaries. Journal of Cryptology 25(3), 383–433 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  18. Hohenberger, S., Weis, S.A.: Honest-verifier private disjointness testing without random oracles. In: Danezis, G., Golle, P. (eds.) PET 2006. LNCS, vol. 4258, pp. 277–294. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  19. Jarecki, S., Liu, X.: Efficient oblivious pseudorandom function with applications to adaptive OT and secure computation of set intersection. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 577–594. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  20. Jarecki, S., Liu, X.: Fast secure computation of set intersection. In: Garay, J.A., De Prisco, R. (eds.) SCN 2010. LNCS, vol. 6280, pp. 418–435. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  21. Kamara, S., Mohassel, P., Raykova, M., Sadeghian, S.: Scaling private set intersection to billion-element sets. In: Christin, N., Safavi-Naini, R. (eds.) FC 2014. LNCS, vol. 8437, pp. 195–215. Springer, Heidelberg (2014)

    Google Scholar 

  22. Kerschbaum, F.: Public-key encrypted bloom filters with applications to supply chain integrity. In: Li, Y. (ed.) Data and Applications Security and Privacy XXV. LNCS, vol. 6818, pp. 60–75. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  23. Kerschbaum, F.: Outsourced private set intersection using homomorphic encryption. In: Youm, H.Y., Won, Y. (eds.) ASIACCS 2012, pp. 85–86. ACM Press, May 2012

    Google Scholar 

  24. Kiayias, A., Mitrofanova, A.: Testing disjointness of private datasets. In: S. Patrick, A., Yung, M. (eds.) FC 2005. LNCS, vol. 3570, pp. 109–124. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  25. Kissner, L., Song, D.: Privacy-preserving set operations. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 241–257. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  26. Many, D., Burkhart, M., Dimitropoulos, X.: Tech. Rep. TIK report no. 345, ETH Zurich, Switzerland (2012)

    Google Scholar 

  27. Papapetrou, O., Siberski, W., Nejdl, W.: Cardinality estimation and dynamic length adaptation for bloom filters. Distributed and Parallel Databases 28(2–3), 119–156 (2010)

    Article  Google Scholar 

  28. Pinkas, B., Schneider, T., Zohner, M.: Faster private set intersection based on OT extension. In: Proceedings of the 23rd USENIX Security Symposium, San Diego, CA, USA, August 20–22, pp. 797–812. USENIX Association (2014)

    Google Scholar 

  29. Tarkoma, S., Rothenberg, C.E., Lagerspetz, E.: Theory and practice of bloom filters for distributed systems. IEEE Communications Surveys and Tutorials 14(1), 131–155 (2012)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Technische Universität Darmstadt, Darmstadt, Germany

    Rolf Egert, Marc Fischlin, David Gens, Sven Jacob, Matthias Senker & Jörn Tillmanns

Authors
  1. Rolf Egert
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Marc Fischlin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. David Gens
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Sven Jacob
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Matthias Senker
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Jörn Tillmanns
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Marc Fischlin .

Editor information

Editors and Affiliations

  1. Queensland University of Technology, Brisbane, Queensland, Australia

    Ernest Foo

  2. Queensland University of Technology, Brisbane, Queensland, Australia

    Douglas Stebila

Rights and permissions

Reprints and permissions

Copyright information

© 2015 Springer International Publishing Switzerland

About this paper

Cite this paper

Egert, R., Fischlin, M., Gens, D., Jacob, S., Senker, M., Tillmanns, J. (2015). Privately Computing Set-Union and Set-Intersection Cardinality via Bloom Filters. In: Foo, E., Stebila, D. (eds) Information Security and Privacy. ACISP 2015. Lecture Notes in Computer Science(), vol 9144. Springer, Cham. https://doi.org/10.1007/978-3-319-19962-7_24

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-19962-7_24

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-19961-0

  • Online ISBN: 978-3-319-19962-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation