nach oben

Erschienen in:

2021 | OriginalPaper | Buchkapitel

Multi-party Threshold Private Set Intersection with Sublinear Communication

verfasst von : Saikrishna Badrinarayanan, Peihan Miao, Srinivasan Raghuraman, Peter Rindal

Erschienen in: Public-Key Cryptography – PKC 2021

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Masked Triples

Nächstes Kapitel On the (In)Security of the Diffie-Hellman Oblivious PRF with Multiplicative Blinding

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

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

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.

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.

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\).

[AIK05]

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

[BDP21]

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

[Ben94]

Benaloh, J.: Dense probabilistic encryption May 1994

[BFK+19]

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

[BGG+18]

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_19CrossRef

[BGY80]

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)MathSciNetCrossRef

[BO15]

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

[BPSW07]

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

[CDN01]

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_18CrossRef

[CM20]

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_2CrossRef

[DCT10]

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

[DCW13]

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

[DIK+08]

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_14CrossRef

[FH96]

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

[FNP04]

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_1CrossRef

[GJR10]

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

[GN19]

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_6CrossRef

[GS19a]

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_1CrossRef

[GS19b]

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

[HFH99]

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)

[HOS17]

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

[HV17]

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

[HW15]

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

[IKN+17]

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

[KKRT16]

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

[KMP+17]

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

[KMWF07]

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

[KS05]

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_15CrossRef

[MPR+20]

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_1CrossRef

[MTZ03]

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

[MZ17]

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

[NMH+10]

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

[OOS16]

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

[Pai99]

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_16CrossRef

[PRTY19]

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_13CrossRef

[PRTY20]

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_25CrossRef

[PSSZ15]

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

[PSWW18]

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_5CrossRef

[PSZ14]

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

[RR17]

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

[TPKC07]

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

[TY90]

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

[Yao86]

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

[ZC18]

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

Titel: Multi-party Threshold Private Set Intersection with Sublinear Communication
verfasst von: Saikrishna Badrinarayanan
Peihan Miao
Srinivasan Raghuraman
Peter Rindal
Verlag: Springer International Publishing
Buch: Public-Key Cryptography – PKC 2021
Print ISBN: 978-3-030-75247-7

Electronic ISBN: 978-3-030-75248-4

Copyright-Jahr: 2021
DOI: https://doi.org/10.1007/978-3-030-75248-4_13

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner