Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Two-Client and Multi-client Functional Encryption for Set Intersection

  • Conference paper
  • First Online:
Information Security and Privacy (ACISP 2019)

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

Included in the following conference series:

Abstract

We propose several functional encryption schemes for set intersection and variants on two or multiple sets. In these schemes, a party may learn the set intersection from the sets of two or more clients, without having to learn the plaintext set of each individual client. For the case of two clients, we construct efficient schemes for determining the set intersection and the cardinality of the intersection. To evaluate the cardinality of the intersection, no overhead is incurred when compared to operating on plaintext data. We also present other functionalities with a scheme for set intersection with data transfer and a threshold scheme that only discloses the intersection if both clients have at least t elements in common. Finally, we consider set intersection and set intersection cardinality schemes for the case of three or more clients from a theoretical perspective. Our proof-of-concept implementations show that the two-client constructions are efficient and scale linearly in the set sizes.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 79.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 99.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

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Available at https://github.com/CRIPTIM/nipsi.

References

  1. Abadi, A., Terzis, S., Dong, C.: O-PSI: delegated private set intersection on outsourced datasets. In: Federrath, H., Gollmann, D. (eds.) SEC 2015. IAICT, vol. 455, pp. 3–17. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-18467-8_1

    Chapter  Google Scholar 

  2. Abadi, A., Terzis, S., Dong, C.: VD-PSI: verifiable delegated private set intersection on outsourced private datasets. In: Grossklags, J., Preneel, B. (eds.) FC 2016. LNCS, vol. 9603, pp. 149–168. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-662-54970-4_9

    Chapter  Google Scholar 

  3. Abdalla, M., Benhamouda, F., Kohlweiss, M., Waldner, H.: Decentralizing inner-product functional encryption. In: Lin, D., Sako, K. (eds.) PKC 2019, Part II. LNCS, vol. 11443, pp. 128–157. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17259-6_5

    Chapter  Google Scholar 

  4. Bellare, M., Keelveedhi, S., Ristenpart, T.: Message-locked encryption and secure deduplication. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 296–312. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38348-9_18

    Chapter  Google Scholar 

  5. Bellare, M., Namprempre, C.: Authenticated encryption: relations among notions and analysis of the generic composition paradigm. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 531–545. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44448-3_41

    Chapter  Google Scholar 

  6. Boneh, D., Lewi, K., Raykova, M., Sahai, A., Zhandry, M., Zimmerman, J.: Semantically secure order-revealing encryption: multi-input functional encryption without obfuscation. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part II. LNCS, vol. 9057, pp. 563–594. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_19

    Chapter  Google Scholar 

  7. Carpent, X., Faber, S., Sander, T., Tsudik, G.: Private set projections & variants. In: WPES. ACM (2017). https://doi.org/10.1145/3139550.3139554

  8. Chotard, J., Dufour Sans, E., Gay, R., Phan, D.H., Pointcheval, D.: Decentralized multi-client functional encryption for inner product. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018. LNCS, vol. 11273, pp. 703–732. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03329-3_24

    Chapter  Google Scholar 

  9. 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). https://doi.org/10.1007/978-3-642-14577-3_13

    Chapter  Google Scholar 

  10. Ding, B., König, A.C.: Fast set intersection in memory. In: Jagadish, H.V., Koudas, N. (ed.) Proceedings of the VLDB Endowment 4.4, pp. 255–266, January 2011. ISSN: 2150–8097. https://doi.org/10.14778/1938545.1938550

    Article  Google Scholar 

  11. Dong, C., Chen, L., Wen, Z.: When private set intersection meets big data: an efficient and scalable protocol. In: CCS. ACM (2013). https://doi.org/10.1145/2508859.2516701

  12. Douceur, J.R., Adya, A., Bolosky, W.J., Simon, D., Theimer, M.: Reclaiming space from duplicate files in a serverless distributed file system. In: ICDCS. IEEE (2002). https://doi.org/10.1109/ICDCS.2002.1022312

  13. 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). https://doi.org/10.1007/978-3-540-24676-3_1

    Chapter  Google Scholar 

  14. Galindo, D., Hoepman, J.-H.: Non-interactive distributed encryption: a new primitive for revocable privacy. In: WPES. ACM (2011). https://doi.org/10.1145/2046556.2046567

  15. Goldwasser, S., et al.: Multi-input functional encryption. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 578–602. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-55220-5_32

    Chapter  Google Scholar 

  16. 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). https://doi.org/10.1007/978-3-642-15317-4_26

    Chapter  Google Scholar 

  17. 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). https://doi.org/10.1007/978-3-662-45472-5_13

    Chapter  Google Scholar 

  18. Kerschbaum, F.: Collusion-resistant outsourcing of private set intersection. In: SAC. ACM (2012). https://doi.org/10.1145/2245276.2232008

  19. Kerschbaum, F.: Outsourced private set intersection using homomorphic encryption. In: ASIACCS. ACM (2012). https://doi.org/10.1145/2414456.2414506

  20. Kim, S., Lewi, K., Mandal, A., Montgomery, H., Roy, A., Wu, D.J.: Function-hiding inner product encryption is practical. In: Catalano, D., De Prisco, R. (eds.) SCN 2018. LNCS, vol. 11035, pp. 544–562. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-98113-0_29

    Chapter  Google Scholar 

  21. Kissner, L., Song, D.: Privacy-preserving set operations. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 241–257. Springer, Heidelberg (2005). https://doi.org/10.1007/11535218_15

    Chapter  Google Scholar 

  22. Lewko, A., Waters, B.: Decentralizing attribute-based encryption. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 568–588. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20465-4_31

    Chapter  Google Scholar 

  23. Liu, F., Ng, W.K., Zhang, W., Giang, D.H., Han, S.: Encrypted set intersection protocol for outsourced datasets. In: IC2E. IEEE (2014). https://doi.org/10.1109/IC2E.2014.18

  24. Lueks, W., Hoepman, J.-H., Kursawe, K.: Forward-secure distributed encryption. In: De Cristofaro, E., Murdoch, S.J. (eds.) PETS 2014. LNCS, vol. 8555, pp. 123–142. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-08506-7_7

    Chapter  Google Scholar 

  25. Meadows, C.: A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party. In: S&P. IEEE (1986). https://doi.org/10.1109/SP.1986.10022

  26. Pandey, O., Rouselakis, Y.: Property preserving symmetric encryption. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 375–391. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_23

    Chapter  Google Scholar 

  27. Pinkas, B., Schneider, T., Zohner, M.: Faster private set intersection based on OT extension. In: USENIX Security. USENIX Association (2014)

    Google Scholar 

  28. Shi, E., Chan, T.H., Rieffel, E.G., Chow, R., Song, D.: Privacy-preserving aggregation of time-series data. In: NDSS. The Internet Society (2011)

    Google Scholar 

  29. Smart, N.P.: Cryptography Made Simple. Information Security and Cryptography. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-21936-3. ISBN: 978-3-319-21936-3. Ed. by D. Basin and K. Paterson

    Book  MATH  Google Scholar 

  30. van de Kamp, T., Peter, A., Everts, M.H., Jonker, W.: Multi-client predicate-only encryption for conjunctive equality tests. In: Capkun, S., Chow, S.S.M. (eds.) CANS 2017. LNCS, vol. 11261, pp. 135–157. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-02641-7_7

    Chapter  Google Scholar 

  31. Zheng, Q., Xu, S.: Verifiable delegated set intersection operations on outsourced encrypted data. In: IC2E. IEEE (2015). https://doi.org/10.1109/IC2E.2015.38

Download references

Acknowledgments

This work was supported by the Netherlands Organisation for Scientific Research (Nederlandse Organisatie voor Wetenschappelijk Onderzoek, NWO) in the context of the CRIPTIM project.

Author information

Authors and Affiliations

  1. University of Twente, Enschede, The Netherlands

    Tim van de Kamp, David Stritzl, Willem Jonker & Andreas Peter

Authors
  1. Tim van de Kamp
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. David Stritzl
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Willem Jonker
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Andreas Peter
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tim van de Kamp .

Editor information

Editors and Affiliations

  1. Massey University, Palmerston North, New Zealand

    Julian Jang-Jaccard

  2. University of Wollongong, Wollongong, NSW, Australia

    Fuchun Guo

Rights and permissions

Reprints and permissions

Copyright information

© 2019 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

van de Kamp, T., Stritzl, D., Jonker, W., Peter, A. (2019). Two-Client and Multi-client Functional Encryption for Set Intersection. In: Jang-Jaccard, J., Guo, F. (eds) Information Security and Privacy. ACISP 2019. Lecture Notes in Computer Science(), vol 11547. Springer, Cham. https://doi.org/10.1007/978-3-030-21548-4_6

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-21548-4_6

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-21547-7

  • Online ISBN: 978-3-030-21548-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation