Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Revisiting Lattice Attacks on Overstretched NTRU Parameters Read chapter Read first chapter

2017 | OriginalPaper | Chapter

Improved Private Set Intersection Against Malicious Adversaries

Authors : Peter Rindal, Mike Rosulek

Published in: Advances in Cryptology – EUROCRYPT 2017

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Private set intersection (PSI) refers to a special case of secure two-party computation in which the parties each have a set of items and compute the intersection of these sets without revealing any additional information. In this paper we present improvements to practical PSI providing security in the presence of malicious adversaries.
Our starting point is the protocol of Dong, Chen & Wen (CCS 2013) that is based on Bloom filters. We identify a bug in their malicious-secure variant and show how to fix it using a cut-and-choose approach that has low overhead while simultaneously avoiding one the main computational bottleneck in their original protocol. We also point out some subtleties that arise when using Bloom filters in malicious-secure cryptographic protocols.
We have implemented our PSI protocols and report on its performance. Our improvements reduce the cost of Dong et al.’s protocol by a factor of \(14-110{\times }\) on a single thread. When compared to the previous fastest protocol of De Cristofaro et al., we improve the running time by \(8-24{\times }\). For instance, our protocol has an online time of 14 s and an overall time of 2.1 min to securely compute the intersection of two sets of 1 million items each.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter A Kilobit Hidden SNFS Discrete Logarithm Computation
next chapter Formal Abstractions for Attested Execution Secure Processors
Footnotes
1
We contacted the authors of [8], who confirmed that our attack violates malicious security.
 
2
This committing property of an OT choice bit was pointed out by Rivest [24].
 
3
Additionally, if one strictly follows the DCW pseudocode then correctness may be violated in the event of a collision \(h_i(x) = h_{i'}(x)\). If \(h_i(x)\) is the first “free” GBF location then \(G[h_i(x)]\) gets set to a value and then erroneously overwritten later.
 
4
In practice H is instantiated with a SHA-family hash function. The xor expression and x itself are each 128 bits, so both fit in a single SHA block.
 
5
The simulator does not, however, require the ability to program the random oracle.
 
6
nk ones is an upper bound on the number of ones required. A tighter analysis could be obtained if collisions were accounted for.
 
7
This is part of the proof that breaks down if we compute a summary value using \(\bigoplus _i m_{\pi (h_i(x)),1}\) instead of \(\bigoplus _{j\in h_*(x)} m_{\pi (j),1}\). In the first expression, it may be that \(h_{i'}(x) = h_i(x)\) for some \(i' \ne i\) so that the randomizing term \(m_{\pi (h_i(x)),1}\) cancels out in the sum.
 
8
Note that if we model SHA1 as having its queries observable to the simulator, then this property is inherited also when expanding the SHA1 output with a PRG.
 
Literature
1.
Asharov, G., Lindell, Y., Schneider, T., Zohner, M.: More efficient oblivious transfer and extensions for faster secure computation. In: Sadeghi et al. [25], pp. 535–548
2.
Asharov, G., Lindell, Y., Schneider, T., Zohner, M.: More efficient oblivious transfer extensions with security for malicious adversaries. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 673–701. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-46800-5_​26
3.
Beaver, D.: Correlated pseudorandomness and the complexity of private computations. In: 28th ACM STOC, pp. 479–488. ACM Press, May 1996
4.
Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: 42nd FOCS, pp. 136–145. IEEE Computer Society Press, October 2001
5.
Canetti, R., Jain, A., Scafuro, A.: Practical UC security with a global random oracle. In: Ahn, G.-J., Yung, M., Li, N. (eds.) ACM CCS 14, pp. 597–608. ACM Press, New York (2014)
6.
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). doi:10.​1007/​978-3-642-01957-9_​8 CrossRef
7.
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). doi:10.​1007/​978-3-642-17373-8_​13 CrossRef
8.
Dong, C., Chen, L., Wen, Z.: When private set intersection meets big data: an efficient and scalable protocol. In: Sadeghi et al. [25], pp. 789–800
9.
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). doi:10.​1007/​978-3-540-24676-3_​1 CrossRef
10.
Goodrich, M.T., Mitzenmacher, M.: Invertible bloom lookup tables. In: 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011, Allerton Park & Retreat Center, Monticello, IL, USA, 28–30 September 2011, pp. 792–799. IEEE (2011)
11.
Huang, Y., Evans, D., Katz, J.: Private set intersection: are garbled circuits better than custom protocols? In: NDSS 2012. The Internet Society, Feburary 2012
12.
Huberman, B.A., Franklin, M.K., Hogg, T.: Enhancing privacy and trust in electronic communities. In: EC, pp. 78–86 (1999)
13.
14.
Kamara, S., Mohassel, P., Raykova, M., Sadeghian, S.: Scaling private set intersection to billion-element sets. In: Christin, N., Safavi-Naini, R. (eds.) FC 2014. LNCS, vol. 8437, pp. 195–215. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-45472-5_​13
15.
16.
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 16, pp. 818–829. ACM Press, New York (2016)CrossRef
17.
18.
19.
20.
Naor, M., Pinkas, B.: Efficient oblivious transfer protocols. In: Kosaraju, S.R. (ed.) 12th SODA, pp. 448–457. ACM-SIAM, New York (2001)
21.
Orrù, M., Orsini, E., Scholl, P.: Actively secure 1-out-of-N OT extension with application to private set intersection. In: Handschuh, H. (ed.) CT-RSA 2017. LNCS, vol. 10159, pp. 381–396. Springer, Cham (2017). doi:10.​1007/​978-3-319-52153-4_​22 CrossRef
22.
Pinkas, B., Schneider, T., Segev, G., Zohner, M.: Phasing: private set intersection using permutation-based hashing. In: Jung, J., Holz, T. (eds.) 24th USENIX Security Symposium, USENIX Security 15, pp. 515–530. USENIX Association, Berkeley (2015)
23.
Pinkas, B., Schneider, T., Zohner, M.: Faster private set intersection based on OT extension. In: Fu, K., Jung, J. (eds.) 23rd USENIX Security Symposium, USENIX Security 14, pp. 797–812. USENIX Association, Berkeley (2014)
24.
25.
Sadeghi, A.-R., Gligor, V.D., Yung, M. (eds.): ACM CCS 13. ACM Press, New York (2013)
Metadata
Title
Improved Private Set Intersection Against Malicious Adversaries
Authors
Peter Rindal
Mike Rosulek
Copyright Year
2017
Book
Advances in Cryptology – EUROCRYPT 2017

Print ISBN: 978-3-319-56619-1

Electronic ISBN: 978-3-319-56620-7

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-56620-7_9

Premium Partner

    Image Credits