Skip to main content

2014 | OriginalPaper | Buchkapitel

Scaling Private Set Intersection to Billion-Element Sets

verfasst von : Seny Kamara, Payman Mohassel, Mariana Raykova, Saeed Sadeghian

Erschienen in: Financial Cryptography and Data Security

Verlag: Springer Berlin Heidelberg

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

search-config
loading …

Abstract

We examine the feasibility of private set intersection (PSI) over massive datasets. PSI, which allows two parties to find the intersection of their sets without revealing them to each other, has numerous applications including to privacy-preserving data mining, location-based services and genomic computations. Unfortunately, the most efficient constructions only scale to sets containing a few thousand elements—even in the semi-honest model and over a LAN.
In this work, we design PSI protocols in the server-aided setting, where the parties have access to a single untrusted server that makes its computational resources available as a service. We show that by exploiting the server-aided model and by carefully optimizing and parallelizing our implementations, PSI is feasible for billion-element sets even while communicating over the Internet. As far as we know, ours is the first attempt to scale PSI to billion-element sets which represents an increase of five orders of magnitude over previous work.
Our protocols are secure in several adversarial models including against a semi-honest, covert and malicious server; and address a range of security and privacy concerns including fairness and the leakage of the intersection size. Our protocols also yield efficient server-aided private equality-testing (PET) with stronger security guarantees than prior work.

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
An alternative approach considered in the PSI literature is the use of tamper-proof hardware in the design of private set intersection [30, 38]. This approach allows for better efficiency and hence more scalable protocols. Token-based PSI makes different and incomparable trust assumptions compared to server-aided MPC, and does not seem suitable for settings that involve a cloud service.
 
2
Due to space limitations we had to omit our security definitions and proofs. The full version of this work with definitions and proofs is available on request.
 
3
The full version is available upon request.
 
4
We note that, this is different from what is know in the literature as size-hiding PSI where the goal is the hide the size of input sets. Here, we only intend to hide the size of the intersection from the server who does not have any inputs or outputs.
 
Literatur
1.
Zurück zum Zitat Aiello, W., Ishai, Y., Reingold, O.: Priced oblivious transfer: How to sell digital goods. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 119–135. Springer, Heidelberg (2001)CrossRef Aiello, W., Ishai, Y., Reingold, O.: Priced oblivious transfer: How to sell digital goods. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 119–135. Springer, Heidelberg (2001)CrossRef
2.
Zurück zum Zitat Asharov, G., Jain, A., López-Alt, A., Tromer, E., Vaikuntanathan, V., Wichs, D.: Multiparty computation with low communication, computation and interaction via threshold FHE. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 483–501. Springer, Heidelberg (2012)CrossRef Asharov, G., Jain, A., López-Alt, A., Tromer, E., Vaikuntanathan, V., Wichs, D.: Multiparty computation with low communication, computation and interaction via threshold FHE. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 483–501. Springer, Heidelberg (2012)CrossRef
3.
Zurück zum Zitat Baldi, P., Baronio, R., De Cristofaro, E., Gasti, P., Tsudik, G.: Countering gattaca: efficient and secure testing of fully-sequenced human genomes. In: CCS, pp. 691–702 (2011) Baldi, P., Baronio, R., De Cristofaro, E., Gasti, P., Tsudik, G.: Countering gattaca: efficient and secure testing of fully-sequenced human genomes. In: CCS, pp. 691–702 (2011)
4.
Zurück zum Zitat Barak, B., Goldreich, O.: Universal arguments and their applications. In: CCC (2002) Barak, B., Goldreich, O.: Universal arguments and their applications. In: CCC (2002)
5.
Zurück zum Zitat Ben-David, A., Nisan, N., Pinkas, B.: Fairplaymp: a system for secure multi-party computation. In: CCS (2008) Ben-David, A., Nisan, N., Pinkas, B.: Fairplaymp: a system for secure multi-party computation. In: CCS (2008)
6.
Zurück zum Zitat Bogdanov, D., Laur, S., Willemson, J.: Sharemind: A framework for fast privacy-preserving computations. In: Jajodia, S., Lopez, J. (eds.) ESORICS 2008. LNCS, vol. 5283, pp. 192–206. Springer, Heidelberg (2008)CrossRef Bogdanov, D., Laur, S., Willemson, J.: Sharemind: A framework for fast privacy-preserving computations. In: Jajodia, S., Lopez, J. (eds.) ESORICS 2008. LNCS, vol. 5283, pp. 192–206. Springer, Heidelberg (2008)CrossRef
7.
Zurück zum Zitat Bogetoft, P., Christensen, D., Damgard, I., Geisler, M., Jakobsen, T., Krøigaard, M., Nielsen, J., Nielsen, J.B., Nielsen, K., Pagter, J., Schwartzbach, M., Toft, T.: Secure multiparty computation goes live. In: FC (2009) Bogetoft, P., Christensen, D., Damgard, I., Geisler, M., Jakobsen, T., Krøigaard, M., Nielsen, J., Nielsen, J.B., Nielsen, K., Pagter, J., Schwartzbach, M., Toft, T.: Secure multiparty computation goes live. In: FC (2009)
8.
Zurück zum Zitat Boudot, F., Schoenmakers, B., Traore, J.: A fair and efficient solution to the socialist millionaires’ problem. Discrete Appl. Math. 111(1), 23–36 (2001)CrossRefMATHMathSciNet Boudot, F., Schoenmakers, B., Traore, J.: A fair and efficient solution to the socialist millionaires’ problem. Discrete Appl. Math. 111(1), 23–36 (2001)CrossRefMATHMathSciNet
9.
Zurück zum Zitat Camenisch, J., Zaverucha, G.: Private intersection of certified sets. In: FC, pp. 108–127 (2009) Camenisch, J., Zaverucha, G.: Private intersection of certified sets. In: FC, pp. 108–127 (2009)
10.
Zurück zum Zitat Cash, D., Jarecki, S., Jutla, C., Krawczyk, H., Roşu, M.-C., Steiner, M.: Highly-scalable searchable symmetric encryption with support for boolean queries. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 353–373. Springer, Heidelberg (2013)CrossRef Cash, D., Jarecki, S., Jutla, C., Krawczyk, H., Roşu, M.-C., Steiner, M.: Highly-scalable searchable symmetric encryption with support for boolean queries. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 353–373. Springer, Heidelberg (2013)CrossRef
11.
Zurück zum Zitat Chang, Y.-C., Mitzenmacher, M.: Privacy preserving keyword searches on remote encrypted data. In: Ioannidis, J., Keromytis, A.D., Yung, M. (eds.) ACNS 2005. LNCS, vol. 3531, pp. 442–455. Springer, Heidelberg (2005)CrossRef Chang, Y.-C., Mitzenmacher, M.: Privacy preserving keyword searches on remote encrypted data. In: Ioannidis, J., Keromytis, A.D., Yung, M. (eds.) ACNS 2005. LNCS, vol. 3531, pp. 442–455. Springer, Heidelberg (2005)CrossRef
12.
Zurück zum Zitat Chase, M., Kamara, S.: Structured encryption and controlled disclosure. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 577–594. Springer, Heidelberg (2010)CrossRef Chase, M., Kamara, S.: Structured encryption and controlled disclosure. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 577–594. Springer, Heidelberg (2010)CrossRef
13.
Zurück zum Zitat Cleve, R.: Limits on the security of coin flips when half the processors are faulty. In: STOC, pp. 364–369 (1986) Cleve, R.: Limits on the security of coin flips when half the processors are faulty. In: STOC, pp. 364–369 (1986)
14.
Zurück zum Zitat De Cristofaro, E., Tsudik, G.: Practical private set intersection protocols with linear complexity. In: Financial Cryptography, pp. 143–159 (2010) De Cristofaro, E., Tsudik, G.: Practical private set intersection protocols with linear complexity. In: Financial Cryptography, pp. 143–159 (2010)
15.
Zurück zum Zitat Curtmola, R., Garay, J., Kamara, S., Ostrovsky, R.: Searchable symmetric encryption: Improved definitions and efficient constructions. In: ACM CCS, pp. 79–88 (2006) Curtmola, R., Garay, J., Kamara, S., Ostrovsky, R.: Searchable symmetric encryption: Improved definitions and efficient constructions. In: ACM CCS, pp. 79–88 (2006)
16.
Zurück zum Zitat 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)CrossRef 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)CrossRef
17.
Zurück zum Zitat Dachman-Soled, D., Malkin, T., Raykova, M., Yung, M.: Secure efficient multiparty computing of multivariate polynomials and applications. In: Lopez, J., Tsudik, G. (eds.) ACNS 2011. LNCS, vol. 6715, pp. 130–146. Springer, Heidelberg (2011)CrossRef Dachman-Soled, D., Malkin, T., Raykova, M., Yung, M.: Secure efficient multiparty computing of multivariate polynomials and applications. In: Lopez, J., Tsudik, G. (eds.) ACNS 2011. LNCS, vol. 6715, pp. 130–146. Springer, Heidelberg (2011)CrossRef
19.
Zurück zum Zitat Damgard, I., Geisler, M., Krøigaard, M., Nielsen, J.-B.: Asynchronous multiparty computation: Theory and implementation. In: PKC (2009) Damgard, I., Geisler, M., Krøigaard, M., Nielsen, J.-B.: Asynchronous multiparty computation: Theory and implementation. In: PKC (2009)
20.
Zurück zum Zitat Damgård, I.B., Ishai, Y.: Constant-Round multiparty computation using a black-box pseudorandom generator. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 378–394. Springer, Heidelberg (2005)CrossRef Damgård, I.B., Ishai, Y.: Constant-Round multiparty computation using a black-box pseudorandom generator. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 378–394. Springer, Heidelberg (2005)CrossRef
21.
Zurück zum Zitat 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)CrossRef 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)CrossRef
22.
Zurück zum Zitat 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)CrossRef 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)CrossRef
23.
Zurück zum Zitat De Cristofaro, E., Tsudik, G.: Experimenting with fast private set intersection. In: Katzenbeisser, S., Weippl, E., Camp, L.J., Volkamer, M., Reiter, M., Zhang, X. (eds.) Trust 2012. LNCS, vol. 7344, pp. 55–73. Springer, Heidelberg (2012)CrossRef De Cristofaro, E., Tsudik, G.: Experimenting with fast private set intersection. In: Katzenbeisser, S., Weippl, E., Camp, L.J., Volkamer, M., Reiter, M., Zhang, X. (eds.) Trust 2012. LNCS, vol. 7344, pp. 55–73. Springer, Heidelberg (2012)CrossRef
24.
Zurück zum Zitat Dong, C., Chen, L., Camenisch, J., Russello, G.: Fair private set intersection with a semi-trusted arbiter. Cryptology ePrint Archive, Report 2012/252 (2012) Dong, C., Chen, L., Camenisch, J., Russello, G.: Fair private set intersection with a semi-trusted arbiter. Cryptology ePrint Archive, Report 2012/252 (2012)
25.
Zurück zum Zitat Dong, C., Chen, L., Wen, Z.: When private set intersection meets big data: An efficient and scalable protocol. In: ACM CCS, pp. 789–800 (2013) Dong, C., Chen, L., Wen, Z.: When private set intersection meets big data: An efficient and scalable protocol. In: ACM CCS, pp. 789–800 (2013)
26.
Zurück zum Zitat Ejgenberg, Y., Farbstein, M., Levy, M., Yehuda, L.: The secure computation application programming interface, SCAPI (2012) Ejgenberg, Y., Farbstein, M., Levy, M., Yehuda, L.: The secure computation application programming interface, SCAPI (2012)
28.
Zurück zum Zitat Fagin, R., Naor, M., Winkler, P.: Comparing information without leaking it. Commun. ACM 39(5), 77–85 (1996)CrossRef Fagin, R., Naor, M., Winkler, P.: Comparing information without leaking it. Commun. ACM 39(5), 77–85 (1996)CrossRef
29.
Zurück zum Zitat Feige, U., Killian, J., Naor, M.: A minimal model for secure computation (extended abstract). In: STOC (1994) Feige, U., Killian, J., Naor, M.: A minimal model for secure computation (extended abstract). In: STOC (1994)
30.
Zurück zum Zitat Fischlin, M., Pinkas, B., Sadeghi, A.-R., Schneider, T., Visconti, I.: Secure set intersection with untrusted hardware tokens. In: Kiayias, A. (ed.) CT-RSA 2011. LNCS, vol. 6558, pp. 1–16. Springer, Heidelberg (2011)CrossRef Fischlin, M., Pinkas, B., Sadeghi, A.-R., Schneider, T., Visconti, I.: Secure set intersection with untrusted hardware tokens. In: Kiayias, A. (ed.) CT-RSA 2011. LNCS, vol. 6558, pp. 1–16. Springer, Heidelberg (2011)CrossRef
31.
Zurück zum Zitat 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)CrossRef 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)CrossRef
32.
Zurück zum Zitat Garay, J.A., MacKenzie, P.D., Prabhakaran, M., Yang, K.: Resource fairness and composability of cryptographic protocols. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 404–428. Springer, Heidelberg (2006)CrossRef Garay, J.A., MacKenzie, P.D., Prabhakaran, M., Yang, K.: Resource fairness and composability of cryptographic protocols. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 404–428. Springer, Heidelberg (2006)CrossRef
33.
Zurück zum Zitat Gelles, R., Ostrovsky, R., Winoto, K.: Multiparty proximity testing with dishonest majority from equality testing. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part II. LNCS, vol. 7392, pp. 537–548. Springer, Heidelberg (2012)CrossRef Gelles, R., Ostrovsky, R., Winoto, K.: Multiparty proximity testing with dishonest majority from equality testing. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part II. LNCS, vol. 7392, pp. 537–548. Springer, Heidelberg (2012)CrossRef
34.
Zurück zum Zitat Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC (2009) Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC (2009)
36.
Zurück zum Zitat Gordon, S.D., Katz, J.: Partial fairness in secure two-party computation. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 157–176. Springer, Heidelberg (2010)CrossRef Gordon, S.D., Katz, J.: Partial fairness in secure two-party computation. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 157–176. Springer, Heidelberg (2010)CrossRef
37.
Zurück zum Zitat Gordon, S.D., Hazay, C., Katz, J., Lindell, Y.: Complete fairness in secure two-party computation. J. ACM 58(6), 24 (2011)CrossRefMathSciNet Gordon, S.D., Hazay, C., Katz, J., Lindell, Y.: Complete fairness in secure two-party computation. J. ACM 58(6), 24 (2011)CrossRefMathSciNet
38.
Zurück zum Zitat Hazay, C., Lindell, Y.: Constructions of truly practical secure protocols using standardsmartcards. In: CCS, pp. 491–500 (2008) Hazay, C., Lindell, Y.: Constructions of truly practical secure protocols using standardsmartcards. In: CCS, pp. 491–500 (2008)
39.
Zurück zum Zitat Hazay, C., Lindell, Y.: Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 155–175. Springer, Heidelberg (2008)CrossRef Hazay, C., Lindell, Y.: Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 155–175. Springer, Heidelberg (2008)CrossRef
40.
Zurück zum Zitat Hazay, C., Nissim, K.: Efficient set operations in the presence of malicious adversaries. Public Key Cryptogr. PKC 2010, 312–331 (2010)MathSciNet Hazay, C., Nissim, K.: Efficient set operations in the presence of malicious adversaries. Public Key Cryptogr. PKC 2010, 312–331 (2010)MathSciNet
41.
Zurück zum Zitat Henecka, W., Kogl, S., Sadeghi, A.-R., Schneider, T., Wehrenberg, I.: TASTY: tool for automating secure two-party computations. In: CCS (2010) Henecka, W., Kogl, S., Sadeghi, A.-R., Schneider, T., Wehrenberg, I.: TASTY: tool for automating secure two-party computations. In: CCS (2010)
42.
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)
43.
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)
44.
Zurück zum Zitat 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)CrossRef 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)CrossRef
45.
Zurück zum Zitat Kamara, S., Mohassel, P., Raykova, M.: Outsourcing multi-party comptuation. Technical Report 2011/272, IACR ePrint Cryptography Archive (2011) Kamara, S., Mohassel, P., Raykova, M.: Outsourcing multi-party comptuation. Technical Report 2011/272, IACR ePrint Cryptography Archive (2011)
46.
Zurück zum Zitat Kamara, S., Papamanthou, C.: Parallel and dynamic searchable symmetric encryption. In: Financial Cryptography and Data Security (FC ’13) (2013) Kamara, S., Papamanthou, C.: Parallel and dynamic searchable symmetric encryption. In: Financial Cryptography and Data Security (FC ’13) (2013)
47.
Zurück zum Zitat Kamara, S., Papamanthou, C., Roeder, T.: Dynamic searchable symmetric encryption. In: ACM Conference on Computer and Communications Security (CCS ’12). ACM Press (2012) Kamara, S., Papamanthou, C., Roeder, T.: Dynamic searchable symmetric encryption. In: ACM Conference on Computer and Communications Security (CCS ’12). ACM Press (2012)
48.
Zurück zum Zitat Kamara, S., Mohassel, P., Riva, B.: Salus: A system for server-aided secure function evaluation. In: CCS, pp. 797–808 (2012) Kamara, S., Mohassel, P., Riva, B.: Salus: A system for server-aided secure function evaluation. In: CCS, pp. 797–808 (2012)
49.
Zurück zum Zitat Katz, J., Ostrovsky, R., Smith, A.: Round efficiency of multi-party computation with a dishonest majority. In: EUROCRYPT (2003) Katz, J., Ostrovsky, R., Smith, A.: Round efficiency of multi-party computation with a dishonest majority. In: EUROCRYPT (2003)
50.
Zurück zum Zitat Kerschbaum, F.: Outsourcing private set intersection using homomorphic encryption. In: Asia CCS ’12 (2012) Kerschbaum, F.: Outsourcing private set intersection using homomorphic encryption. In: Asia CCS ’12 (2012)
51.
Zurück zum Zitat Kissner, L., Song, D.: Privacy-preserving set operations. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 241–257. Springer, Heidelberg (2005)CrossRef Kissner, L., Song, D.: Privacy-preserving set operations. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 241–257. Springer, Heidelberg (2005)CrossRef
52.
Zurück zum Zitat Knuth, D.E.: The Art of Computer Programming: Seminumerical Algorithms, vol. 2, 3rd edn. Addison-Wesley Longman Publishing Co., Inc, Boston (1997) Knuth, D.E.: The Art of Computer Programming: Seminumerical Algorithms, vol. 2, 3rd edn. Addison-Wesley Longman Publishing Co., Inc, Boston (1997)
53.
Zurück zum Zitat Lindell, Y.: Parallel coin-tossing and constant-round secure two-party computation. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, p. 171. Springer, Heidelberg (2001)CrossRef Lindell, Y.: Parallel coin-tossing and constant-round secure two-party computation. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, p. 171. Springer, Heidelberg (2001)CrossRef
54.
Zurück zum Zitat Lipmaa, H.: Verifiable homomorphic oblivious transfer and private equality test. In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 416–433. Springer, Heidelberg (2003)CrossRef Lipmaa, H.: Verifiable homomorphic oblivious transfer and private equality test. In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 416–433. Springer, Heidelberg (2003)CrossRef
55.
Zurück zum Zitat Malka, L.: Vmcrypt: modular software architecture for scalable secure computation. In: CCS (2011) Malka, L.: Vmcrypt: modular software architecture for scalable secure computation. In: CCS (2011)
56.
Zurück zum Zitat Malkhi, D., Nisan, N., Pinkas, B., Sella, Y.: Fairplay–a secure two-party computation system. In: USENIX Security (2004) Malkhi, D., Nisan, N., Pinkas, B., Sella, Y.: Fairplay–a secure two-party computation system. In: USENIX Security (2004)
57.
Zurück zum Zitat Nagaraja, S., Mittal, P., Hong, C.-Y., Caesar, M., Borisov, N.: Botgrep: Finding P2P bots with structured graph analysis. In: USENIX Security (2010) Nagaraja, S., Mittal, P., Hong, C.-Y., Caesar, M., Borisov, N.: Botgrep: Finding P2P bots with structured graph analysis. In: USENIX Security (2010)
58.
Zurück zum Zitat Narayanan, A., Thiagarajan, N., Lakhani, M., Hamburg, M., Dan B.: Location privacy via private proximity testing. In: NDSS (2011) Narayanan, A., Thiagarajan, N., Lakhani, M., Hamburg, M., Dan B.: Location privacy via private proximity testing. In: NDSS (2011)
59.
Zurück zum Zitat Pinkas, B.: Fair secure two-party computation. In: Eurocrypt, pp. 647–647 (2003) Pinkas, B.: Fair secure two-party computation. In: Eurocrypt, pp. 647–647 (2003)
61.
Zurück zum Zitat Saldamli, G., Chow, R., Jin, H., Knijnenburg, B.: Private proximity testing with an untrusted server. In: SIGSAC, pp. 113–118 (2013) Saldamli, G., Chow, R., Jin, H., Knijnenburg, B.: Private proximity testing with an untrusted server. In: SIGSAC, pp. 113–118 (2013)
62.
Zurück zum Zitat Song, D., Wagner, D., Perrig, A.: Practical techniques for searching on encrypted data. In: IEEE S&P, pp. 44–55 (2000) Song, D., Wagner, D., Perrig, A.: Practical techniques for searching on encrypted data. In: IEEE S&P, pp. 44–55 (2000)
64.
Zurück zum Zitat Yao, A.: Protocols for secure computations. In: FOCS (1982) Yao, A.: Protocols for secure computations. In: FOCS (1982)
Metadaten
Titel
Scaling Private Set Intersection to Billion-Element Sets
verfasst von
Seny Kamara
Payman Mohassel
Mariana Raykova
Saeed Sadeghian
Copyright-Jahr
2014
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-662-45472-5_13