Top

Published in:

2016 | OriginalPaper | Chapter

Bounded Size-Hiding Private Set Intersection

Authors : Tatiana Bradley, Sky Faber, Gene Tsudik

Published in: Security and Cryptography for Networks

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

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.

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 Pen and Paper Arguments for SIMON and SIMON-like Designs

next chapter On Garbling Schemes with and Without Privacy

For example: age, blood type, birthday, country, zip code, etc.

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.

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.

The term “efficient” is used in the standard sense, i.e., efficient in the context of most cryptographic literature.

Being simulatable means that \(C^*\) can output a computationally indistinguishable transcript.

Note that because the adversarial client has more power in the HbC* model than in plain HbC, security also holds in HbC.

A practical example is SHA-256 for \(\omega =256\).

This probability is taken over the input space. Given non-degenerate inputs, these views are perfectly indistinguishable.

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\).

Client need only verify \(g^A\) is a generator by computing \((g^A)^{p'}\) before exponentiating with r.

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

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)

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

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

Bradley, T., Faber, S., Tsudik, G.: Bounded size-hiding private set intersection. IACR Cryptology ePrint Archive, Report 2016/657 (2016). http://eprint.iacr.org/2016/657

Caelli, W.J., Dawson, E.P., Rea, S.A.: Pki, elliptic curve cryptography, and digital signatures. Comput. Secur. 18(1), 47–66 (1999)CrossRef

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)

Dachman-Soled, D., Malkin, T., Raykova, M., Yung, M.: Efficient robust private set intersection. Int. J. Appl. Cryptogr. 2(4), 289–303 (2012)MathSciNetCrossRefMATH

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.

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.

Goldwasser, S., Micali, S.: Probabilistic encryption. J. Comput. Syst. Sci. 28(2), 270–299 (1984)MathSciNetCrossRefMATH

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.

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)

Title: Bounded Size-Hiding Private Set Intersection
Authors: Tatiana Bradley
Sky Faber
Gene Tsudik
Publisher: Springer International Publishing
Book: Security and Cryptography for Networks
Print ISBN: 978-3-319-44617-2

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

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

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner