Skip to main content
SpringerLink
Log in

Multi-party Threshold Private Set Intersection with Sublinear Communication

  • Conference paper
  • First Online:
Public-Key Cryptography – PKC 2021 (PKC 2021)

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

Included in the following conference series:

Abstract

In multi-party threshold private set intersection (PSI), n parties each with a private set wish to compute the intersection of their sets if the intersection is sufficiently large. Previously, Ghosh and Simkin (CRYPTO 2019) studied this problem for the two-party case and demonstrated interesting lower and upper bounds on the communication complexity. In this work, we investigate the communication complexity of the multi-party setting \((n\ge 2)\). We consider two functionalities for multi-party threshold PSI. In the first, parties learn the intersection if each of their sets and the intersection differ by at most T. In the second functionality, parties learn the intersection if the union of all their sets and the intersection differ by at most T.

For both functionalities, we show that any protocol must have communication complexity \(\varOmega (nT)\). We build protocols with a matching upper bound of O(nT) communication complexity for both functionalities assuming threshold FHE. We also construct a computationally more efficient protocol for the second functionality with communication complexity \(\widetilde{O}(nT)\) under a weaker assumption of threshold additive homomorphic encryption. As a direct implication, we solve one of the open problems in the work of Ghosh and Simkin (CRYPTO 2019) by designing a two-party protocol with communication cost \(\widetilde{O}(T)\) from assumptions weaker than FHE.

As a consequence of our results, we achieve the first “regular” multi-party PSI protocol where the communication complexity only grows with the size of the set difference and does not depend on the size of the input sets.

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

Access this chapter

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

Notes

  1. 1.

    \(\widetilde{O}(\cdot )\) hides \(\mathsf {polylog}\) factors. All the upper bounds omit a \(\mathsf {poly}(\lambda )\) factor where \(\lambda \) is the security parameter.

  2. 2.

    By “regular” PSI, we refer to the standard notion of PSI without threshold.

  3. 3.

    A rational function is a fraction of two polynomials. We refer to Minskey et al. [MTZ03] for details on rational function interpolation over a field. Also, we note that monic polynomials can be interpolated with 2T evaluation but we use \(2T+1\) for consistency with our other protocols.

  4. 4.

    In fact, this subtle issue was initially overlooked by [GS19b] in their recent update of the multi-party protocol. It has subsequently been fixed after we notified them.

  5. 5.

    We define the communication complexity of a party \(P_i\) in any protocol execution as the complexity of all the communication that \(P_i\) is involved in. That is, the complexity of the messages both incoming to and outgoing from \(P_i\).

References

  1. Applebaum, B., Ishai, Y., Kushilevitz, E.: Computationally private randomizing polynomials and their applications. In: CCC (2005)

    Google Scholar 

  2. Branco, P., Döttling, N., Pu, S.: Multiparty cardinality testing for threshold private set intersection. In: PKC (2021)

    Google Scholar 

  3. Benaloh, J.: Dense probabilistic encryption May 1994

    Google Scholar 

  4. Badrinarayanan, S., Fernando, R., Koppula, V., Sahai, A., Waters, B.: Output compression, MPC, and IO for turing machines. In: ASIACRYPT (2019)

    Google Scholar 

  5. Boneh, D., Gennaro, R., Goldfeder, S., Jain, A., Kim, S., Rasmussen, P.M.R., Sahai, A.: Threshold cryptosystems from threshold fully homomorphic encryption. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 565–596. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_19

    Chapter  Google Scholar 

  6. Brent, R.P., Gustavson, F.G., Yun, D.Y.Y.: Fast solution of Toeplitz systems of equations and computation of padé approximants. J. Algorithms 1(3), 259–295 (1980)

    Article  MathSciNet  Google Scholar 

  7. Braverman, M., Oshman, R.: On information complexity in the broadcast model. In: PODC (2015)

    Google Scholar 

  8. Brickell, J., Porter, D.E., Shmatikov, V., Witchel, E.: Privacy-preserving remote diagnostics. In: CCS (2007)

    Google Scholar 

  9. Cramer, R., Damgård, I., Nielsen, J.B.: Multiparty computation from threshold homomorphic encryption. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 280–300. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44987-6_18

    Chapter  Google Scholar 

  10. Chase, M., Miao, P.: Private set intersection in the internet setting from lightweight oblivious PRF. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12172, pp. 34–63. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56877-1_2

    Chapter  Google Scholar 

  11. De Cristofaro, E., Tsudik, G.: Practical private set intersection protocols with linear complexity. In: FC (2010)

    Google Scholar 

  12. Dong, C., Chen, L., Wen, Z.: When private set intersection meets big data: an efficient and scalable protocol. In: CCS (2013)

    Google Scholar 

  13. Damgård, I., Ishai, Y., Krøigaard, M., Nielsen, J.B., Smith, A.: Scalable multiparty computation with nearly optimal work and resilience. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 241–261. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_14

    Chapter  Google Scholar 

  14. Franklin, M., Haber, S.: Joint encryption and message-efficient secure computation. J. Cryptol. 9, 217–232 (1996)

    Article  MathSciNet  Google Scholar 

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

  16. Grigorescu, E., Jung, K., Rubinfeld, R.: A local decision test for sparse polynomials. Inf. Process. Lett. 110(20), 898–901 (2010)

    Article  MathSciNet  Google Scholar 

  17. Ghosh, S., Nilges, T.: An algebraic approach to maliciously secure private set intersection. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11478, pp. 154–185. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17659-4_6

    Chapter  Google Scholar 

  18. Ghosh, S., Simkin, M.: The communication complexity of threshold private set intersection. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11693, pp. 3–29. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_1

    Chapter  Google Scholar 

  19. Ghosh, S., Simkin, M.: The communication complexity of threshold private set intersection (2019). ia.cr/2019/175

    Google Scholar 

  20. Huberman, B.A., Franklin, M., Hogg, T.: Enhancing privacy and trust in electronic communities. In: Proceedings of the 1st ACM Conference on Electronic Commerce (1999)

    Google Scholar 

  21. Per, A., Hallgren, C.O., Sabelfeld, A.: Privacy-preserving ridesharing. In: CSF, Privatepool (2017)

    Google Scholar 

  22. Hazay, C., Venkitasubramaniam, M.: Scalable multi-party private set-intersection. In: PKC (2017)

    Google Scholar 

  23. Hubáček, P., Wichs, D.: On the communication complexity of secure function evaluation with long output. In: ITCS (2015)

    Google Scholar 

  24. Ion, M., et al.: Private intersection-sum protocol with applications to attributing aggregate ad conversions (2017). ia.cr/2017/738

    Google Scholar 

  25. Kolesnikov, V., Kumaresan, R., Rosulek, M., Trieu, N.: Efficient batched oblivious PRF with applications to private set intersection. In: CCS (2016)

    Google Scholar 

  26. Kolesnikov, V., Matania, N., Pinkas, B., Rosulek, M., Trieu, N.: Practical multi-party private set intersection from symmetric-key techniques. In: CCS (2017)

    Google Scholar 

  27. Kiltz, E., Mohassel, P., Weinreb, E., Franklin, M.: Secure linear algebra using linearly recurrent sequences. In: TCC (2007)

    Google Scholar 

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

  29. Miao, P., Patel, S., Raykova, M., Seth, K., Yung, M.: Two-sided malicious security for private intersection-sum with cardinality. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12172, pp. 3–33. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56877-1_1

    Chapter  Google Scholar 

  30. Minsky, Y., Trachtenberg, A., Zippel, R.: Set reconciliation with nearly optimal communication complexity. IEEE Trans. Inf. Theory 49, 2213–2218 (2003)

    Article  MathSciNet  Google Scholar 

  31. Mohassel, P., Zhang, Y.: SecureML: a system for scalable privacy-preserving machine learning. In: IEEE S and P (2017)

    Google Scholar 

  32. Nagaraja, S., Mittal, P., Hong, C.-Y., Caesar, M., Borisov, N.: BotGrep: finding P2P bots with structured graph analysis. In: USENIX security symposium (2010)

    Google Scholar 

  33. Orrù, M., Orsini, E., Scholl, P.: Actively secure 1-out-of-n OT extension with application to private set intersection. In: CT-RSA (2016)

    Google Scholar 

  34. Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_16

    Chapter  Google Scholar 

  35. Pinkas, B., Rosulek, M., Trieu, N., Yanai, A.: SpOT-light: lightweight private set intersection from sparse OT extension. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11694, pp. 401–431. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26954-8_13

    Chapter  Google Scholar 

  36. Pinkas, B., Rosulek, M., Trieu, N., Yanai, A.: PSI from PaXoS: fast, malicious private set intersection. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12106, pp. 739–767. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45724-2_25

    Chapter  Google Scholar 

  37. Pinkas, B., Schneider, T., Segev, G., Zohner, M.: Phasing: private set intersection using permutation-based hashing. In USENIX (2015)

    Google Scholar 

  38. Pinkas, B., Schneider, T., Weinert, C., Wieder, U.: Efficient circuit-based PSI via cuckoo hashing. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10822, pp. 125–157. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78372-7_5

    Chapter  Google Scholar 

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

    Google Scholar 

  40. Rindal, P., Rosulek, M.: Malicious-secure private set intersection via dual execution. In: CCS (2017)

    Google Scholar 

  41. Troncoso-Pastoriza, J.R., Katzenbeisser, S., Celik, M.: Privacy preserving error resilient dna searching through oblivious automata. In: CCS (2007)

    Google Scholar 

  42. Thull, K., Yap, C.: A unified approach to HGCD algorithms for polynomials and integers. Manuscript (1990)

    Google Scholar 

  43. Yao, A.C.-C.: How to generate and exchange secrets (extended abstract). In: FOCS (1986)

    Google Scholar 

  44. Zhao, Y., Chow, S.S.M.: Can you find the one for me? Privacy-preserving matchmaking via threshold PSI (2018). ia.cr/2018/184

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Visa Research, Palo Alto, USA

    Saikrishna Badrinarayanan, Srinivasan Raghuraman & Peter Rindal

  2. University of Illinois at Chicago, Chicago, USA

    Peihan Miao

Authors
  1. Saikrishna Badrinarayanan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Peihan Miao
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Srinivasan Raghuraman
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Peter Rindal
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Saikrishna Badrinarayanan .

Editor information

Editors and Affiliations

  1. Texas A&M University, College Station, TX, USA

    Juan A. Garay

Rights and permissions

Reprints and permissions

Copyright information

© 2021 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Badrinarayanan, S., Miao, P., Raghuraman, S., Rindal, P. (2021). Multi-party Threshold Private Set Intersection with Sublinear Communication. In: Garay, J.A. (eds) Public-Key Cryptography – PKC 2021. PKC 2021. Lecture Notes in Computer Science(), vol 12711. Springer, Cham. https://doi.org/10.1007/978-3-030-75248-4_13

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-75248-4_13

  • Published:

  • Publisher Name: Springer, Cham

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

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

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation