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
Erschienen in:
A Tag Based Encoding: An Efficient Encoding for Predicate Encryption in Prime Order Groups Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Bounded Size-Hiding Private Set Intersection

verfasst von : Tatiana Bradley, Sky Faber, Gene Tsudik

Erschienen in: Security and Cryptography for Networks

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Private Set Intersection (PSI) and other private set operations have many current and emerging applications. Numerous PSI techniques have been proposed that vary widely in terms of underlying cryptographic primitives, security assumptions as well as complexity. One recent strand of PSI-related research focused on an additional privacy property of hiding participants’ input sizes. Despite some interesting results, only one practical size-hiding PSI (SH-PSI) has been demonstrated thus far [1].
One legitimate general criticism of size-hiding private set intersection is that the party that hides its input size can attempt to enumerate the entire (and possibly limited) domain of set elements, thus learning the other party’s entire input set. Although this “attack” goes beyond the honest-but-curious model, it motivates investigation of techniques that simultaneously hide and limit a participant’s input size. To this end, this paper explores the design of bounded size-hiding PSI techniques that allow one party to hide the size of its input while allowing the other party to limit that size. Its main contribution is a reasonably efficient (quasi-quadratic in input size) \(b{\textsf {SH}\text {-}\textsf {PSI}}\) protocol based on bounded keyed accumulators. This paper also studies the relationships between several flavors of the “Strong Diffie-Hellman” (SDH) problem.

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 Pen and Paper Arguments for SIMON and SIMON-like Designs
Nächstes Kapitel On Garbling Schemes with and Without Privacy
Fußnoten
1
For example: age, blood type, birthday, country, zip code, etc.
 
2
In contrast, \(b{\textsf {SH}\text {-}\textsf {PSI}}\) incurs only O(|C|) costs, since client can download server’s public key only once, ahead of time, i.e., off-line.
 
3
As discussed later, although the proposed \(b{\textsf {SH}\text {-}\textsf {PSI}}\) has the same issue, it discourages client’s cheating by imposing a relatively high client computational cost for each additional element in the accumulator, up to the bound.
 
4
The term “efficient” is used in the standard sense, i.e., efficient in the context of most cryptographic literature.
 
5
Being simulatable means that \(C^*\) can output a computationally indistinguishable transcript.
 
6
Note that because the adversarial client has more power in the HbC* model than in plain HbC, security also holds in HbC.
 
7
A practical example is SHA-256 for \(\omega =256\).
 
8
This probability is taken over the input space. Given non-degenerate inputs, these views are perfectly indistinguishable.
 
9
Strictly speaking, a new \(z\) is not needed. Instead, server can generate a new base \(\hat{g}\), compute the new \([\hat{g},\hat{g}^z,\ldots ,\hat{g}^{ (z^{t}) } ] \) and keep the same \(z\).
 
10
Client need only verify \(g^A\) is a generator by computing \((g^A)^{p'}\) before exponentiating with r.
 
Literatur
1.
Ateniese, G., De Cristofaro, E., Tsudik, G.: (If) size matters: size-hiding private set intersection. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol. 6571, pp. 156–173. Springer, Heidelberg (2011)CrossRef
2.
Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: ACM Conference on Computer and Communications Security, pp. 62–73. ACM (1993)
3.
Boneh, D., Boyen, X.: Short signatures without random oracles. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 56–73. Springer, Heidelberg (2004)CrossRef
4.
Boneh, D., Di Crescenzo, G., Ostrovsky, R., Persiano, G.: Public key encryption with keyword search. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 506–522. Springer, Heidelberg (2004)CrossRef
5.
6.
Caelli, W.J., Dawson, E.P., Rea, S.A.: Pki, elliptic curve cryptography, and digital signatures. Comput. Secur. 18(1), 47–66 (1999)CrossRef
7.
Chase, M., Ostrovsky, R., Visconti, I.: Executable proofs, input-size hiding secure computation and a new ideal world. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 532–560. Springer, Heidelberg (2015)
8.
Dachman-Soled, D., Malkin, T., Raykova, M., Yung, M.: Efficient robust private set intersection. Int. J. Appl. Cryptogr. 2(4), 289–303 (2012)MathSciNetCrossRefMATH
9.
D’Arco, P., González Vasco, M.I., Pérez del Pozo, A.L., Soriente, C.: Size-hiding in private set intersection: existential results and constructions. In: Mitrokotsa, A., Vaudenay, S. (eds.) AFRICACRYPT 2012. LNCS, vol. 7374, pp. 378–394. Springer, Heidelberg (2012)CrossRef
10.
D’Arco, P., González Vasco, M.I., Pérez del Pozo, A.L., Soriente, C.: Size-hiding in private set intersection: existential results and constructions. In: Mitrokotsa, A., Vaudenay, S. (eds.) AFRICACRYPT 2012. LNCS, vol. 7374, pp. 378–394. Springer, Heidelberg (2012)CrossRef
11.
De Cristofaro, E., Faber, S., Gasti, P., Tsudik, G.: Genodroid: are privacy-preserving genomic tests ready for prime time? In: WPES, pp. 97–108. ACM (2012)
12.
De Cristofaro, E., Faber, S., Tsudik, G.: Secure genomic testing with size- and position-hiding private substring matching. In: WPES, pp. 107–118. ACM (2013)
13.
De Cristofaro, E., Gasti, P., Tsudik, G.: Fast and private computation of cardinality of set intersection and union. In: Pieprzyk, J., Sadeghi, A.-R., Manulis, M. (eds.) CANS 2012. LNCS, vol. 7712, pp. 218–231. Springer, Heidelberg (2012)CrossRef
14.
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
15.
De Cristofaro, E., Tsudik, G.: Practical private set intersection protocols with linear complexity. In: Sion, R. (ed.) FC 2010. LNCS, vol. 6052, pp. 143–159. Springer, Heidelberg (2010)CrossRef
16.
Dong, C., Chen, L., Wen, Z.: When private set intersection meets big data: an efficient and scalable protocol. In: Proceedings of the ACM SIGSAC Conference on Computer & Communications Security, pp. 789–800. ACM (2013)
17.
Faber, S., Petrlic, R., Tsudik, G.: Unlinked: private proximity-based off-line OSN interaction. In: Proceedings of the 14th ACM Workshop on Privacy in the Electronic Society, pp. 121–131. ACM (2015)
18.
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
19.
Goldreich, O.: The Foundations of Cryptography - Volume 2, Basic Applications. Cambridge University Press, Cambridge (2004)CrossRefMATH
20.
21.
Goyal, V., Ostrovsky, R., Scafuro, A., Visconti, I.: Black-box non-black-box zero knowledge. In: STOC, pp. 515–524. ACM (2014)
22.
Hahn, C., Hur, J.: Scalable and secure private set intersection for big data. In: International Conference on Big Data and Smart Computing, BigComp 2016, Hong Kong, China, 18–20 January 2016, pp. 285–288 (2016)
23.
Hazay, C.: Oblivious polynomial evaluation and secure set-intersection from algebraic PRFs. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part II. LNCS, vol. 9015, pp. 90–120. Springer, Heidelberg (2015)CrossRef
24.
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
25.
Huang, Y., Evans, D., Katz, J.: Private set intersection: are garbled circuits better than custom protocols? In: NDSS (2012)
26.
Ishai, Y., Paskin, A.: Evaluating branching programs on encrypted data. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 575–594. Springer, Heidelberg (2007)CrossRef
27.
Kerschbaum, F.: Outsourced private set intersection using homomorphic encryption. In: Proceedings of the 7th ACM Symposium on Information, Computer and Communications Security, pp. 85–86. ACM (2012)
28.
Kissner, L., Song, D.: Private and threshold set-intersection. Technical report, DTIC Document (2004)
29.
Lindell, Y., Nissim, K., Orlandi, C.: Hiding the input-size in secure two-party computation. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part II. LNCS, vol. 8270, pp. 421–440. Springer, Heidelberg (2013)CrossRef
30.
Lindell, Y., Nissim, K., Orlandi, C.: Hiding the input-size in secure two-party computation. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part II. LNCS, vol. 8270, pp. 421–440. Springer, Heidelberg (2013)CrossRef
31.
Micali, S., Rabin, M.O., Kilian, J.: Zero-knowledge sets. In: FOCS, pp. 80–91. IEEE Computer Society (2003)
32.
Nguyen, L.: Accumulators from bilinear pairings and applications. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp. 275–292. Springer, Heidelberg (2005)CrossRef
33.
Pinkas, B., Schneider, T., Zohner, M.: Faster private set intersection based on OT extension. In: 23rd USENIX Security Symposium (USENIX Security 2014), pp. 797–812 (2014)
34.
Tanaka, N., Saito, T.: On the q-strong Diffie-Hellman problem. IACR Cryptology ePrint Archive, 2010:215 (2010)
Metadaten
Titel
Bounded Size-Hiding Private Set Intersection
verfasst von
Tatiana Bradley
Sky Faber
Gene Tsudik
Copyright-Jahr
2016
Buch
Security and Cryptography for Networks

Print ISBN: 978-3-319-44617-2

Electronic ISBN: 978-3-319-44618-9

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-44618-9_24

Premium Partner

    Bildnachweise