Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Journal of Cryptology
Erschienen in: Journal of Cryptology 1/2016

01.01.2016

Efficient Set Intersection with Simulation-Based Security

verfasst von: Michael J. Freedman, Carmit Hazay, Kobbi Nissim, Benny Pinkas

Erschienen in: Journal of Cryptology | Ausgabe 1/2016

Einloggen

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

search-config
loading …

Abstract

We consider the problem of computing the intersection of private datasets of two parties, where the datasets contain lists of elements taken from a large domain. This problem has many applications for online collaboration. In this work, we present protocols based on the use of homomorphic encryption and different hashing schemes for both the semi-honest and malicious environments. The protocol for the semi-honest environment is secure in the standard model, while the protocol for the malicious environment is secure in the random oracle model. Our protocols obtain linear communication and computation overhead. We further implement different variants of our semi-honest protocol. Our experiments show that the asymptotic overhead of the protocol is affected by different constants. (In particular, the degree of the polynomials evaluated by the protocol matters less than the number of polynomials that are evaluated.) As a result, the protocol variant with the best asymptotic overhead is not necessarily preferable for inputs of reasonable size.
Vorheriger Artikel How to Build an Ideal Cipher: The Indifferentiability of the Feistel Construction
Nächster Artikel Concurrent Knowledge Extraction in Public-Key Models

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
Fußnoten
1
The reduction is to a domain of size \(3n\) in order to ensure that the inputs to the set intersection problem are always of size \(\Theta (n)\). This simplifies the description of the result that is proved by the reduction.
 
2
The plaintext and ciphertext spaces may depend on \(pk\); we leave this implicit.
 
3
W.l.o.g., we assume \(X,Y \subseteq \{0,1\}^{p(k)}\) for some polynomial \(p(\cdot )\) such that \(2^{p(k)}\) is super-polynomial in \(k\).
 
4
This construction can be considered a generalization of the oblivious transfer protocols of [5, 47, 54]. In those, a chooser retrieving item \(i\) sends to the sender a predicate which is 0 if and only if \(i=j\), where \(j \in [N]\).
 
5
By setting \(B=m_1\log \log m_1 / \log m_1\), we can make the error probability negligible in \(m_1\). However, any actual implementation will have to examine the exact value of \(B\) which results in a sufficiently small error probability for the input sizes that are expected. As for theoretical analysis, the subsequent construction, based on balanced allocation hashing, presents a negligible error probability.
 
6
A constant factor improvement is achieved using the Always Go Left scheme in [62] where \(h_0:\{0,1\}^{*} \rightarrow [1,\ldots ,\frac{B}{2}], h_1:\{0,1\}^{*} \rightarrow [\frac{B}{2}+1,\ldots ,B]\). In that scheme, an element \(x\) is inserted into the less occupied bin from \(\{h_0(x),h_1(x)\}\); in case of a tie, \(x\) is inserted into \(h_0(x)\).
 
7
Any implementation of a hashing scheme must replace the idealized random hash function (that is used for the analysis) with an actual construction of a hash function that works well in practice. See, e.g., [59] and related work.
 
8
We consider an extension of the semantic security game (cf. Definition 2.6), where a distinguisher \(D_\mathrm{E}\) is given a public key \(pk\), outputs two vectors of plaintexts \(\overline{m}_0,\overline{m}_1\), and receives back a vector of ciphertexts \(\overline{c}\) comprised of the encryptions of \(\overline{m}_b\) under \(E_{pk}\), where \(b\leftarrow _R\{0,1\}\). \(D_\mathrm{E}\) then outputs a bit \(b'\), and we say that it distinguishes successfully in this game if \(b'=b\).
 
9
Learning \(sk\) allows \(P_1\) to efficiently decrypt messages it receives from \(P_2\). Otherwise, \(P_1\) and \(P_2\) would have to engage in a protocol for a joint decryption.
 
10
The original construction of [20] is presented in the honest verifier setting. Deriving a statistical zero-knowledge proof can be achieved by instantiating Pedersen’s commitment scheme [56] with the technique of Goldreich and Kahan [30]. The analysis of \(15\) exponentiations already takes into account this adjustment.
 
11
See previous footnote.
 
12
We will use the convention that the degree of a polynomial \(Q_i(\cdot )\) can be chosen to be any integer \(j'\) such that \(Q_{i,j}=0\) for all \(j\ge j'\); hence, equality with \(m\) can always be achieved.
 
13
The proof can be easily computed since both parties can compute an encryption \(z'\) of \(1-Z_{i,j}\), where \(P\) can recover randomness \(\tilde{r}'_{i,j}\) that is consistent with this encryption. We also assume that \(P\) and \(V\) agree on an encryption of 1, for which both know the randomness.
 
Literatur
1.
Yossi Azar, Andrei Z. Broder, Anna R. Karlin, and Eli Upfal.Balanced allocations. SIAM Journal on Computing, 29(1):180–200, 1999.
2.
Proc. Twentieth Annual ACM Symposium on Theory of Computing, Chicago, Illinois, 2–4 May 1988.
3.
Giuseppe Ateniese, Emiliano De Cristofaro, and Gene Tsudik. (if) size matters: Size-hiding private set intersection. In Dario Catalano, Nelly Fazio, Rosario Gennaro, and Antonio Nicolosi, editors, Public Key Cryptography, volume 6571 of Lecture Notes in Computer Science, pages 156–173. Springer, 2011.
4.
Martin Aumller, Martin Dietzfelbinger, and Philipp Woelfel. Explicit and efficient hash families suffice for cuckoo hashing with a stash. 2012.
5.
Bill Aiello, Yuval Ishai, and Omer Reingold. Priced oblivious transfer: How to sell digital goods. In Advances in Cryptology–EUROCRYPT 2001, Innsbruck, Austria, May 2001.
6.
Miklós Ajtai, János Kolmós, and Endre Szemerédi. An \(O(n \log n)\) sorting network. In STOC, pages 1–9, 1983.
7.
Yonatan Aumann and Yehuda Lindell. Security against covert adversaries: Efficient protocols for realistic adversaries. In Salil P. Vadhan, editor, TCC, volume 4392 of Lecture Notes in Computer Science, pages 137–156. Springer, 2007.
8.
Kenneth E. Batcher. Sorting networks and their applications. In AFIPS Spring Joint Computing Conference, pages 307–314, 32(1968).
9.
Donald Beaver. Foundations of secure interactive computing. CRYPTO, 576:377–391, 1991.
10.
11.
Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In ACM [2], pages 1–10.
12.
Andrei Z. Broder and Michael Mitzenmacher. Using multiple hash functions to improve ip lookups. In IEEE INFOCOM 2001. 20th Ann. Joint Conference of the IEEE Computer and Communications Societies. Proceedings, 2001.
13.
Fabrice Boudot, Berry Schoenmakers, and Jacques Traore. A fair and efficient solution to the socialist millionaires’ problem. Discrete Applied Mathematics, 111(1-2):23–036, 2001.MATHMathSciNetCrossRef
14.
15.
David Chaum, Claude Crépeau, and Ivan Damgård. Multiparty unconditionally secure protocols (extended abstract). In ACM [2], pages 11–19.
16.
Jung Hee Cheon, Stanislaw Jarecki, and Jae Hong Seo. Multi-party privacy-preserving set intersection with quasi-linear complexity. Cryptology ePrint Archive, Report 2010/512, 2010.
17.
David Chaum and Torben P. Pedersen. Wallet databases with observers. In CRYPTO, pages 89–105, 1992.
18.
Jan Camenisch and Gregory M. Zaverucha. Private intersection of certified sets. In Roger Dingledine and Philippe Golle, editors, Financial Cryptography, volume 5628 of Lecture Notes in Computer Science, pages 108–127. Springer, 2009.
19.
Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644–654, November 1976.MATHMathSciNetCrossRef
20.
Ivan Damgård and Mads Jurik. A generalisation, a simplification and some applications of Paillier’s probabilistic public-key system. In 4th International Workshop on Practice and Theory in Public Key Cryptosystems (PKC 2001), pages 13–15, Cheju Island, Korea, February 2001.
21.
Ivan Damgård, Valerio Pastro, Nigel P. Smart, and Sarah Zakarias. Multiparty computation from somewhat homomorphic encryption. In CRYPTO, pages 643–662, 2012.
22.
Dana Dachman-Soled, Tal Malkin, Mariana Raykova, and Moti Yung. Efficient robust private set intersection. In Michel Abdalla, David Pointcheval, Pierre-Alain Fouque, and Damien Vergnaud, editors, ACNS, volume 5536 of Lecture Notes in Computer Science, pages 125–142, 2009.
23.
Martin Dietzfelbinger and Philipp Woelfel. Almost random graphs with simple hash functions. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pages 629–638, 2003.
24.
Ivan Damgård and Sarah Zakarias. Constant-overhead secure computation of boolean circuits using preprocessing. In TCC, pages 621–641, 2013.
25.
Alexandre Evfimievski, Johannes Gehrke, and Ramakrishnan Srikant. Limiting privacy breaches in privacy preserving data mining. In Proc. 22nd ACM Symposium on Principles of Database Systems (PODS 2003), pages 211–222, San Diego, CA, June 2003.
26.
Taher ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 31(4):469–472, 1985.MATHMathSciNetCrossRef
27.
Michael J. Freedman, Yuval Ishai, Benny Pinkas, and Omer Reingold. Keyword search and oblivious pseudorandom functions. In Joe Kilian, editor, TCC, volume 3378 of Lecture Notes in Computer Science, pages 303–324. Springer, 2005.
28.
Michael J. Freedman, Kobbi Nissim, and Benny Pinkas. Efficient private matching and set intersection. In Christian Cachin and Jan Camenisch, editors, Advances in Cryptology–EUROCRYPT 2004, volume 3027 of LNCS, pages 1–19. Springer-Verlag, 2–6 May 2004.
29.
Ronald Fagin, Moni Naor, and Peter Winkler. Comparing information without leaking it. Communications of the ACM, 39(5):77–85, 1996.CrossRef
30.
Oded Goldreich and Ariel Kahan. How to construct constant-round zero-knowledge proof systems for NP. Journal of Cryptology, 9(3):167–189, 1996.MATHMathSciNetCrossRef
31.
Shafi Goldwasser and Leonid A. Levin. Fair computation of general functions in presence of immoral majority. CRYPTO, 537:77–93, 1990.
32.
GMP. GNU Multiple Precision Arithmetic Library. gmplib.org, 2009.
33.
Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game or a completeness theorem for protocols with honest majority. In Proc. Nineteenth Annual ACM Symposium on Theory of Computing, pages 218–229, New York City, 25–27 May 1987.
34.
Oded Goldreich. Foundations of cryptography: Basic applications. Cambridge Univ Pr, 2004.
35.
Bernardo A. Huberman, Matt Franklin, and Tad Hogg. Enhancing privacy and trust in electronic communities. In Proc. ACM Conference on Electronic Commerce, pages 78–86, Denver, Colorado, November 1999.
36.
Carmit Hazay and Yehuda Lindell. Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries. In TCC, pages 155–175, 2008.
37.
Carmit Hazay, Gert Læssøe Mikkelsen, Tal Rabin, and Tomas Toft. Efficient rsa key generation and threshold paillier in the two-party setting. In CT-RSA, pages 313–331, 2012.
38.
Carmit Hazay and Kobbi Nissim. Efficient set operations in the presence of malicious adversaries. In Public Key Cryptography, pages 312–331, 2010.
39.
Russell Impagliazzo and Steven Rudich. Limits on the provable consequences of one-way permutations. In Proc. 21st Annual ACM Symposium on Theory of Computing, pages 44–61, Seattle, Washington, May 1989.
40.
Stanislaw Jarecki and Xiaomin Liu. Efficient oblivious pseudorandom function with applications to adaptive ot and secure computation of set intersection. TCC, 5444:577–594, 2009.MathSciNet
41.
Stanislaw Jarecki and Xiaomin Liu. Fast secure computation of set intersection. SCN, 6280:418–435, 2010.
42.
Stanislaw Jarecki and Vitaly Shmatikov. Efficient two-party secure computation on committed inputs. EUROCRYPT, 4515:97–114, 2007.MathSciNet
43.
Adam Kirsch, Michael Mitzenmacher, and Udi Wieder. More robust hashing: Cuckoo hashing with a stash. In Proceedings of the 16th annual European symposium on Algorithms, pages 611–622. Springer, 2008.
44.
Efficient password-authenticated key exchange using human-memorable passwords. In Advances in Cryptology - EUROCRYPT 2001, Innsbruck, Austria, May 6–10, 2001, pages 475–494, 2001.
45.
Bala Kalyanasundaram and Georg Schnitger. The probabilistic communication complexity of set intersection. SIAM J. Discrete Mathematics, 5(4):545–557, 1992.MATHMathSciNetCrossRef
46.
Lea Kissner and Dawn Song. Private and threshold set-intersection. In Proceedings of CRYPTO ’05, August 2005.
47.
Helger Lipmaa. Verifiable homomorphic oblivious transfer and private equality test. In Advances in Cryptology–ASIACRYPT 2003, pages 416–433, Taipei, Taiwan, November 2003.
48.
Sven Laur and Helger Lipmaa. A new protocol for conditional disclosure of secrets and its applications. In ACNS, pages 207–225, 2007.
49.
Yehuda Lindell and Benny Pinkas. A proof of security of yaos protocol for two-party computation. Journal of Cryptology, 22(2):161–188, 2009.MATHMathSciNetCrossRef
50.
Yehuda Lindell and Benny Pinkas. Secure two-party computation via cut-and-choose oblivious transfer. J. Cryptology, 25(4):680–722, 2012.MATHMathSciNetCrossRef
51.
David Mazières. A toolkit for user-level file systems. In USENIX Technical Conference, June 2001.
52.
Silvio Micali and Phillip Rogaway. Privacy preserving data mining. Unpublished manuscript, 576:392–404, 1991.
53.
Moni Naor and Benny Pinkas. Oblivious transfer and polynomial evaluation. In Proc. 31st Annual ACM Symposium on Theory of Computing, pages 245–254, Atlanta, Georgia, May 1999.
54.
Moni Naor and Benny Pinkas. Efficient oblivious transfer protocols. In SIAM Symposium on Discrete Algorithms (SODA), pages 448–457, Washington, D.C., January 2001.
55.
Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. In Advances in Cryptology–EUROCRYPT ’99, pages 223–238, Prague, Czech Republic, May 1999.
56.
Torben Pryds Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. In J. Feigenbaum, editor, Advances in Cryptology–CRYPTO ’91, volume 576 of LNCS, pages 129–140. Springer-Verlag, 1992, 11–15 August 1991.
57.
58.
59.
60.
Alexander A. Razborov. Application of matrix methods to the theory of lower bounds in computational complexity. Combinatorica, 10(1):81–93, 1990.MATHMathSciNetCrossRef
61.
Martin Raab and Angelika Steger. Balls into Bins - A Simple and Tight Analysis. Randomization and Approximation Techniques in Computer Science, pages 159–170, 1998.
62.
Berthold Vöcking. How asymmetry helps load balancing. Journal of the ACM (JACM), 50:568–589, July 2003.CrossRef
63.
Udi Wieder. Balanced allocations with heterogenous bins. In Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, page 193. ACM, 2007.
64.
Philipp Woelfel. Asymmetric balanced allocation with simple hash functions. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, SODA ’06, pages 424–433, 2006.
65.
Andrew C. Yao. Protocols for secure computations. In 23rd Annual Symposium on Foundations of Computer Science, pages 160–164, Chicago, Illinois, 3–5 November 1982. IEEE.
Metadaten
Titel
Efficient Set Intersection with Simulation-Based Security
verfasst von
Michael J. Freedman
Carmit Hazay
Kobbi Nissim
Benny Pinkas
Publikationsdatum
01.01.2016
Verlag
Springer US
Erschienen in
Journal of Cryptology / Ausgabe 1/2016
Print ISSN: 0933-2790
Elektronische ISSN: 1432-1378
DOI
https://doi.org/10.1007/s00145-014-9190-0

Weitere Artikel der Ausgabe 1/2016

Journal of Cryptology 1/2016 Zur Ausgabe

OriginalPaper

Fast Cryptography in Genus 2

OriginalPaper

Breaking RSA May Be As Difficult As Factoring

OriginalPaper

Enhanced Public Key Security for the McEliece Cryptosystem

OriginalPaper

Concurrent Knowledge Extraction in Public-Key Models

OriginalPaper

How to Build an Ideal Cipher: The Indifferentiability of the Feistel Construction