Skip to main content

2018 | OriginalPaper | Buchkapitel

Efficient Circuit-Based PSI via Cuckoo Hashing

verfasst von : Benny Pinkas, Thomas Schneider, Christian Weinert, Udi Wieder

Erschienen in: Advances in Cryptology – EUROCRYPT 2018

Verlag: Springer International Publishing

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

search-config
loading …

Abstract

While there has been a lot of progress in designing efficient custom protocols for computing Private Set Intersection (PSI), there has been less research on using generic Multi-Party Computation (MPC) protocols for this task. However, there are many variants of the set intersection functionality that are not addressed by the existing custom PSI solutions and are easy to compute with generic MPC protocols (e.g., comparing the cardinality of the intersection with a threshold or measuring ad conversion rates).
Generic PSI protocols work over circuits that compute the intersection. For sets of size n, the best known circuit constructions conduct \(O(n \log n)\) or \(O(n \log n / \log \log n)\) comparisons (Huang et al., NDSS’12 and Pinkas et al., USENIX Security’15). In this work, we propose new circuit-based protocols for computing variants of the intersection with an almost linear number of comparisons. Our constructions are based on new variants of Cuckoo hashing in two dimensions.
We present an asymptotically efficient protocol as well as a protocol with better concrete efficiency. For the latter protocol, we determine the required sizes of tables and circuits experimentally, and show that the run-time is concretely better than that of existing constructions.
The protocol can be extended to a larger number of parties. The proof technique presented in the full version for analyzing Cuckoo hashing in two dimensions is new and can be generalized to analyzing standard Cuckoo hashing as well as other new variants of it.

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!

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!

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!

Fußnoten
1
Facebook is running a computation of this type with companies that have transaction records for a large part of loyalty card holders in the US. According to the report in https://​www.​eff.​org/​deeplinks/​2012/​09/​deep-dive-facebook-and-datalogix-whats-actually-getting-shared-and-how-you-can-opt, the computation is done using an insecure PSI variant based on creating pseudonyms using naive hashing of the items.
 
2
We note though that many probabilistic constructions are analyzed in the algorithms research literature to have a failure probability of o(1), which is fine for many applications, but is typically insufficient for cryptographic applications.
 
4
Unfortunately, the LUT-based implementation of [14] was not capable of evaluating the PSI circuits for \(n = 2^{20}\) elements.
 
5
We do not provide benchmarks with multiple threads for the DH/ECC PSI-CA protocol since the implementation of [39] does not support multi-threading.
 
Literatur
1.
Zurück zum Zitat Amossen, R.R., Pagh, R.: A new data layout for set intersection on GPUs. In: International Symposium on Parallel and Distributed Processing (IPDPS) (2011) Amossen, R.R., Pagh, R.: A new data layout for set intersection on GPUs. In: International Symposium on Parallel and Distributed Processing (IPDPS) (2011)
2.
Zurück zum Zitat Arbitman, Y., Naor, M., Segev, G.: Backyard cuckoo hashing: constant worst-case operations with a succinct representation. In: FOCS (2010) Arbitman, Y., Naor, M., Segev, G.: Backyard cuckoo hashing: constant worst-case operations with a succinct representation. In: FOCS (2010)
3.
Zurück zum Zitat Asharov, G., Lindell, Y., Schneider, T., Zohner, M.: More efficient oblivious transfer and extensions for faster secure computation. In: CCS (2013) Asharov, G., Lindell, Y., Schneider, T., Zohner, M.: More efficient oblivious transfer and extensions for faster secure computation. In: CCS (2013)
4.
Zurück zum Zitat Asokan, N., Dmitrienko, A., Nagy, M., Reshetova, E., Sadeghi, A.-R., Schneider, T., Stelle, S.: CrowdShare: secure mobile resource sharing. In: Jacobson, M., Locasto, M., Mohassel, P., Safavi-Naini, R. (eds.) ACNS 2013. LNCS, vol. 7954, pp. 432–440. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38980-1_27CrossRef Asokan, N., Dmitrienko, A., Nagy, M., Reshetova, E., Sadeghi, A.-R., Schneider, T., Stelle, S.: CrowdShare: secure mobile resource sharing. In: Jacobson, M., Locasto, M., Mohassel, P., Safavi-Naini, R. (eds.) ACNS 2013. LNCS, vol. 7954, pp. 432–440. Springer, Heidelberg (2013). https://​doi.​org/​10.​1007/​978-3-642-38980-1_​27CrossRef
6.
Zurück zum Zitat Chen, H., Laine, K., Rindal, P.: Fast private set intersection from homomorphic encryption. In: CCS (2017) Chen, H., Laine, K., Rindal, P.: Fast private set intersection from homomorphic encryption. In: CCS (2017)
13.
Zurück zum Zitat Demmler, D., Schneider, T., Zohner, M.: ABY – a framework for efficient mixed-protocol secure two-party computation. In: NDSS (2015) Demmler, D., Schneider, T., Zohner, M.: ABY – a framework for efficient mixed-protocol secure two-party computation. In: NDSS (2015)
14.
Zurück zum Zitat Dessouky, G., Koushanfar, F., Sadeghi, A.-R., Schneider, T., Zeitouni, S., Zohner, M.: Pushing the communication barrier in secure computation using lookup tables. In: NDSS (2017) Dessouky, G., Koushanfar, F., Sadeghi, A.-R., Schneider, T., Zeitouni, S., Zohner, M.: Pushing the communication barrier in secure computation using lookup tables. In: NDSS (2017)
15.
Zurück zum Zitat Dietzfelbinger, M., Weidling, C.: Balanced allocation and dictionaries with tightly packed constant size bins. Theoret. Comput. Sci. 380(1–2), 47–68 (2007)MathSciNetCrossRefMATH Dietzfelbinger, M., Weidling, C.: Balanced allocation and dictionaries with tightly packed constant size bins. Theoret. Comput. Sci. 380(1–2), 47–68 (2007)MathSciNetCrossRefMATH
16.
Zurück zum Zitat Dong, C., Chen, L., Wen, Z.: When private set intersection meets big data: an efficient and scalable protocol. In: CCS (2013) Dong, C., Chen, L., Wen, Z.: When private set intersection meets big data: an efficient and scalable protocol. In: CCS (2013)
18.
Zurück zum Zitat Eppstein, D., Goodrich, M., Mitzenmacher, M., Torres, M.: 2–3 cuckoo filters for faster triangle listing and set intersection. In: Symposium on Principles of Database Systems (PODS) (2017) Eppstein, D., Goodrich, M., Mitzenmacher, M., Torres, M.: 2–3 cuckoo filters for faster triangle listing and set intersection. In: Symposium on Principles of Database Systems (PODS) (2017)
19.
Zurück zum Zitat Freedman, M.J., Hazay, C., Nissim, K., Pinkas, B.: Efficient set intersection with simulation-based security. J. Cryptol. 29(1), 115–155 (2016)MathSciNetCrossRefMATH Freedman, M.J., Hazay, C., Nissim, K., Pinkas, B.: Efficient set intersection with simulation-based security. J. Cryptol. 29(1), 115–155 (2016)MathSciNetCrossRefMATH
21.
Zurück zum Zitat Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: STOC (1987) Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: STOC (1987)
22.
23.
Zurück zum Zitat Hallgren, P., Orlandi, C., Sabelfeld, A.: PrivatePool: privacy-preserving ridesharing. In: Computer Security Foundations Symposium (CSF) (2017) Hallgren, P., Orlandi, C., Sabelfeld, A.: PrivatePool: privacy-preserving ridesharing. In: Computer Security Foundations Symposium (CSF) (2017)
25.
Zurück zum Zitat Huang, Y., Chapman, P., Evans, D.: Privacy-preserving applications on smartphones. In: Hot Topics in Security (HotSec) (2011) Huang, Y., Chapman, P., Evans, D.: Privacy-preserving applications on smartphones. In: Hot Topics in Security (HotSec) (2011)
26.
Zurück zum Zitat Huang, Y., Evans, D., Katz, J.: Private set intersection: Are garbled circuits better than custom protocols? In: NDSS (2012) Huang, Y., Evans, D., Katz, J.: Private set intersection: Are garbled circuits better than custom protocols? In: NDSS (2012)
27.
Zurück zum Zitat Huang, Y., Evans, D., Katz, J., Malka, L.: Faster secure two-party computation using garbled circuits. In: USENIX Security (2011) Huang, Y., Evans, D., Katz, J., Malka, L.: Faster secure two-party computation using garbled circuits. In: USENIX Security (2011)
28.
Zurück zum Zitat 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) 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)
29.
Zurück zum Zitat Kirsch, A., Mitzenmacher, M., Wieder, U.: More robust hashing: cuckoo hashing with a stash. SIAM J. Comput. 39(4), 1543–1561 (2009)MathSciNetCrossRefMATH Kirsch, A., Mitzenmacher, M., Wieder, U.: More robust hashing: cuckoo hashing with a stash. SIAM J. Comput. 39(4), 1543–1561 (2009)MathSciNetCrossRefMATH
30.
Zurück zum Zitat Kiss, Á., Liu, J., Schneider, T., Asokan, N., Pinkas, B.: Private set intersection for unequal set sizes with mobile applications. In: PoPETs, vol. 2017(4) (2017) Kiss, Á., Liu, J., Schneider, T., Asokan, N., Pinkas, B.: Private set intersection for unequal set sizes with mobile applications. In: PoPETs, vol. 2017(4) (2017)
31.
Zurück zum Zitat Kolesnikov, V., Kumaresan, R., Rosulek, M., Trieu, N.: Efficient batched oblivious PRF with applications to private set intersection. In: CCS (2016) Kolesnikov, V., Kumaresan, R., Rosulek, M., Trieu, N.: Efficient batched oblivious PRF with applications to private set intersection. In: CCS (2016)
32.
Zurück zum Zitat Kolesnikov, V., Matania, N., Pinkas, B., Rosulek, M., Trieu, N.: Practical multi-party private set intersection from symmetric-key techniques. In: CCS (2017) Kolesnikov, V., Matania, N., Pinkas, B., Rosulek, M., Trieu, N.: Practical multi-party private set intersection from symmetric-key techniques. In: CCS (2017)
33.
34.
Zurück zum Zitat Kreuter, B.: Secure multiparty computation at Google. In: Real World Crypto Conference (RWC) (2017) Kreuter, B.: Secure multiparty computation at Google. In: Real World Crypto Conference (RWC) (2017)
35.
Zurück zum Zitat Meadows, C.: A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party. In: S&P (1986) Meadows, C.: A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party. In: S&P (1986)
36.
Zurück zum Zitat Pagh, R., Rodler, F.F.: Cuckoo hashing. In: European Symposium on Algorithms (ESA) (2001) Pagh, R., Rodler, F.F.: Cuckoo hashing. In: European Symposium on Algorithms (ESA) (2001)
37.
Zurück zum Zitat Panigrahy, R.: Efficient hashing with lookups in two memory accesses. In: ACM-SIAM Symposium on Discrete Algorithms (SODA) (2005) Panigrahy, R.: Efficient hashing with lookups in two memory accesses. In: ACM-SIAM Symposium on Discrete Algorithms (SODA) (2005)
38.
Zurück zum Zitat Pettai, M., Laud, P.: Combining differential privacy and secure multiparty computation. In: ACSAC (2015) Pettai, M., Laud, P.: Combining differential privacy and secure multiparty computation. In: ACSAC (2015)
39.
Zurück zum Zitat Pinkas, B., Schneider, T., Segev, G., Zohner, M.: Phasing: private set intersection using permutation-based hashing. In: USENIX Security (2015) Pinkas, B., Schneider, T., Segev, G., Zohner, M.: Phasing: private set intersection using permutation-based hashing. In: USENIX Security (2015)
40.
Zurück zum Zitat Pinkas, B., Schneider, T., Weinert, C., Wieder, U.: Efficient circuit-based PSI via cuckoo hashing. In: Cryptology ePrint Archive, Report 2018/120 (2018) Pinkas, B., Schneider, T., Weinert, C., Wieder, U.: Efficient circuit-based PSI via cuckoo hashing. In: Cryptology ePrint Archive, Report 2018/120 (2018)
41.
Zurück zum Zitat Pinkas, B., Schneider, T., Zohner, M.: Faster private set intersection based on OT extension. In: USENIX Security (2014) Pinkas, B., Schneider, T., Zohner, M.: Faster private set intersection based on OT extension. In: USENIX Security (2014)
42.
Zurück zum Zitat Pinkas, B., Schneider, T., Zohner, M.: Scalable private set intersection based on OT extension. ACM Trans. Priv. Secur. (TOPS) 21(2) (2018) Pinkas, B., Schneider, T., Zohner, M.: Scalable private set intersection based on OT extension. ACM Trans. Priv. Secur. (TOPS) 21(2) (2018)
44.
Zurück zum Zitat Rindal, P., Rosulek, M.: Malicious-secure private set intersection via dual execution. In: CCS (2017) Rindal, P., Rosulek, M.: Malicious-secure private set intersection via dual execution. In: CCS (2017)
47.
48.
Zurück zum Zitat Yao, A.C.: How to generate and exchange secrets. In: FOCS (1986) Yao, A.C.: How to generate and exchange secrets. In: FOCS (1986)
49.
Zurück zum Zitat Yung, M.: From mental poker to core business: why and how to deploy secure computation protocols? In: CCS (2015) Yung, M.: From mental poker to core business: why and how to deploy secure computation protocols? In: CCS (2015)
50.
Metadaten
Titel
Efficient Circuit-Based PSI via Cuckoo Hashing
verfasst von
Benny Pinkas
Thomas Schneider
Christian Weinert
Udi Wieder
Copyright-Jahr
2018
DOI
https://doi.org/10.1007/978-3-319-78372-7_5