nach oben

Erschienen in:

2021 | OriginalPaper | Buchkapitel

Multiparty Cardinality Testing for Threshold Private Intersection

verfasst von : Pedro Branco, Nico Döttling, Sihang Pu

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

Threshold Private Set Intersection (PSI) allows multiple parties to compute the intersection of their input sets if and only if the intersection is larger than \(n-t\), where n is the size of each set and t is some threshold. The main appeal of this primitive is that, in contrast to standard PSI, known upper-bounds on the communication complexity only depend on the threshold t and not on the sizes of the input sets. Current threshold PSI protocols split themselves into two components: A Cardinality Testing phase, where parties decide if the intersection is larger than some threshold; and a PSI phase, where the intersection is computed. The main source of inefficiency of threshold PSI is the former part.

In this work, we present a new Cardinality Testing protocol that allows N parties to check if the intersection of their input sets is larger than \(n-t\). The protocol incurs in \(\tilde{ \mathcal {O}} (Nt^2)\) communication complexity. We thus obtain a Threshold PSI scheme for N parties with communication complexity \(\tilde{\mathcal {O}}(Nt^2)\).

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 More Efficient Digital Signatures with Tight Multi-user Security

Nächstes Kapitel Verifiable Random Functions with Optimal Tightness

Nur mit Berechtigung zugänglich

It is a slightly different problem from the one we solve in this work. Here, we want to disclosure the intersection \(\cap _{i=1}^N S_i\) if \(|\cap _{i=1}^N S_i|\ge n-t\), which is denoted as

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-75248-4_2/515134_1_En_2_IEq24_HTML.gif

in [1].

Given this, we conclude that the communication complexity of the threshold PSI protocol of [17] is dominated by this Cardinality Testing protocol.

We need a bit-conversion protocol such as [37] to convert between binary circuits and algebra operations.

We actually need to randomize the polynomials in the numerator to guarantee correctness, that is, we need to multiply each term in the numerator by a uniformly chosen element. This is in contrast with the two-party setting where correctness holds even without randomizing the numerator. However, we omit this step for simplicity.

Again, we omit the randomization of the polynomials. Actually, without randomization, these methods (including [17]) are exactly the same as the technique for set reconciliation problem in [28].

This is important to us since, in the threshols PSI setting, \(t\ll n\) where t is the threshold and n is the set size. Kiltz et al. solve linear algebra problems via minimal polynomials, and use adaptors between garbled circuits and additive homomorphic encryption to reduce round complexity. In this work, we extend Kiltz’s protocol to the multiparty case without using garbled circuits (otherwise the circuit size would depend on number of parties) while preserving the same communication complexity for each party (\(\mathcal {O}(t^2)\)).

We will assume the message space of Paillier’s cryptosystem as a field as also mentioned in [24].

We refer the reader to [7] for a detailed explanation of the framework.

A support set is a set of pairs (x, y).

Note that this is the linear system that we need to solve in order to perform rational interpolation [28].

The polynomial multiplication can be expressed as matrix multiplication.

In the case that only \(Q(\alpha _i)=0\), use a different tagged pair

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-75248-4_2/515134_1_En_2_IEq191_HTML.gif

, and this can be noticed by the party who owns polynomial Q(x). In our PSI setting, it is party \(\mathsf {P}_1\).

Here, \(\mathcal {F}_\mathsf {SDT}\) has shared functionality \(\mathcal {F}_\mathsf {Gen}\).

From now on, we always assume that PKE and TPKE used in this work fulfill this property, unless stated otherwise.

Badrinarayanan, S., Miao, P., Raghuraman, S., Rindal, P.: Multi-party threshold private set intersection with sublinear communication. In: PKC 2021 (2021)

Berke, A., Bakker, M., Vepakomma, P., Larson, K., Pentland, A.S.: Assessing disease exposure risk with location data: a proposal for cryptographic preservation of privacy (2020). https://arxiv.org/abs/2003.14412

Boneh, D., Boyen, X., Shacham, H.: Short group signatures. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 41–55. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-28628-8_3CrossRef

Boneh, D., Goh, E.-J., Nissim, K.: Evaluating 2-DNF formulas on ciphertexts. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 325–341. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-30576-7_18CrossRef

Bouman, N.J., de Vreede, N.: New protocols for secure linear algebra: pivoting-free elimination and fast block-recursive matrix decomposition. IACR Cryptology ePrint Archive 2018/703 (2018)

Branco, P., Döttling, N., Pu, S.: Multiparty cardinality testing for threshold private set intersection. Cryptology ePrint Archive, Report 2020/1307 (2020). https://eprint.iacr.org/2020/1307

Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: 42nd Annual Symposium on Foundations of Computer Science, Las Vegas, NV, USA, 14–17 October 2001, pp. 136–145. IEEE Computer Society Press. https://doi.org/10.1109/SFCS.2001.959888

Canetti, R., Dodis, Y., Pass, R., Walfish, S.: Universally composable security with global setup. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 61–85. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-70936-7_4CrossRef

Cramer, R., Damgård, I.: Secure distributed linear algebra in a constant number of rounds. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 119–136. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44647-8_7CrossRefMATH

10.

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

11.

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

12.

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). https://doi.org/10.1007/978-3-642-17373-8_13CrossRefMATH

13.

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: 20th Conference on Computer and Communications Security, Berlin, Germany, 4–8 November 2013, pp. 789–800. ACM Press (2013). https://doi.org/10.1145/2508859.2516701

14.

Elgamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory 31(4), 469–472 (1985)MathSciNetCrossRef

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_1CrossRef

16.

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

17.

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

18.

Ghosh, S., Simkin, M.: The communication complexity of threshold private set intersection. Cryptology ePrint Archive, Report 2019/175 (2019). https://eprint.iacr.org/2019/175

19.

Grigorescu, E., Jung, K., Rubinfeld, R.: A local decision test for sparse polynomials. Inf. Process. Lett. 110(20), 898–901 (2010). https://doi.org/10.1016/j.ipl.2010.07.012MathSciNetCrossRefMATH

20.

Hallgren, P., Orlandi, C., Sabelfeld, A.: Privatepool: privacy-preserving ridesharing. In: 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pp. 276–291 (2017)

21.

Hazay, C., Venkitasubramaniam, M.: Scalable multi-party private set-intersection. In: Fehr, S. (ed.) PKC 2017, Part I. LNCS, vol. 10174, pp. 175–203. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-662-54365-8_8CrossRef

22.

Ion, M., Kreuter, B., Nergiz, E., Patel, S., Saxena, S., Seth, K., Shanahan, D., Yung, M.: Private intersection-sum protocol with applications to attributing aggregate ad conversions. Cryptology ePrint Archive, Report 2017/738 (2017). http://eprint.iacr.org/2017/738

23.

Kaltofen, E., David Saunders, B.: On Wiedemann’s method of solving sparse linear systems. In: Mattson, H.F., Mora, T., Rao, T.R.N. (eds.) AAECC 1991. LNCS, vol. 539, pp. 29–38. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-54522-0_93CrossRef

24.

Kiltz, E., Mohassel, P., Weinreb, E., Franklin, M.: Secure linear algebra using linearly recurrent sequences. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 291–310. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-70936-7_16CrossRef

25.

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

26.

Kolesnikov, V., Kumaresan, R., Rosulek, M., Trieu, N.: Efficient batched oblivious PRF with applications to private set intersection. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 2016: 23rd Conference on Computer and Communications Security, Vienna, Austria, 24–28 October 2016, pp. 818–829. ACM Press (2016). https://doi.org/10.1145/2976749.2978381

27.

Meadows, C.: A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party. In: 1986 IEEE Symposium on Security and Privacy, pp. 134–134 (1986)

28.

Minsky, Y., Trachtenberg, A., Zippel, R.: Set reconciliation with nearly optimal communication complexity. IEEE Trans. Inf. Theory 49(9), 2213–2218 (2003). https://doi.org/10.1109/TIT.2003.815784

29.

Nissim, K., Weinreb, E.: Communication efficient secure linear algebra. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 522–541. Springer, Heidelberg (2006). https://doi.org/10.1007/11681878_27CrossRef

30.

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

31.

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, Part III. LNCS, vol. 11694, pp. 401–431. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26954-8_13CrossRef

32.

Pinkas, B., Schneider, T., Segev, G., Zohner, M.: Phasing: private set intersection using permutation-based hashing. In: Jung, J., Holz, T. (eds.) USENIX Security 2015: 24th USENIX Security Symposium, Washington, DC, USA, 12–14 August 2015, pp. 515–530. USENIX Association (2015)

33.

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

34.

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

35.

Rindal, P., Rosulek, M.: Improved private set intersection against malicious adversaries. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017, Part I. LNCS, vol. 10210, pp. 235–259. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56620-7_9CrossRef

36.

Rindal, P., Rosulek, M.: Malicious-secure private set intersection via dual execution. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017: 24th Conference on Computer and Communications Security, Dallas, TX, USA, 31 October–2 November 2017, pp. 1229–1242. ACM Press (2017). https://doi.org/10.1145/3133956.3134044

37.

Schoenmakers, B., Tuyls, P.: Efficient binary conversion for Paillier encrypted values. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 522–537. Springer, Heidelberg (2006). https://doi.org/10.1007/11761679_31CrossRef

Titel: Multiparty Cardinality Testing for Threshold Private Intersection
verfasst von: Pedro Branco
Nico Döttling
Sihang Pu
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_2

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"