×

Privately computing set-union and set-intersection cardinality via Bloom filters. (English) Zbl 1391.94747

Foo, Ernest (ed.) et al., Information security and privacy. 20th Australasian conference, ACISP 2015, Brisbane, QLD, Australia, June 29 – July 1, 2015. Proceedings. Cham: Springer (ISBN 978-3-319-19961-0/pbk; 978-3-319-19962-7/ebook). Lecture Notes in Computer Science 9144, 413-430 (2015).
Summary: In this paper we propose a new approach to privately compute the set-union cardinality and the set-intersection cardinality among multiple honest-but-curious parties. Our approach is inspired by a proposal of Ashok and Mukkamala (DBSec’14) which deploys Bloom filters to approximate the size tightly. One advantage of their solution is that it avoids ample public-key cryptography. Unfortunately, we show here that their protocol is vulnerable to actual attacks. We therefore propose a new Bloom filter based protocol, also forgoing heavy cryptography, and prove its security.
For the entire collection see [Zbl 1314.94007].

MSC:

94A60 Cryptography
68M10 Network design and communication in computer systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ashok, VG; Mukkamala, R.; Atluri, V.; Pernul, G., A scalable and efficient privacy preserving global itemset support approximation using bloom filters, Data and Applications Security and Privacy XXVIII, 382-389 (2014), Heidelberg: Springer, Heidelberg · Zbl 1391.94725
[2] Blanton, M., Aguiar, E.: Private and oblivious set and multiset operations. In: Youm, H.Y., Won, Y. (eds.) ASIACCS 2012, pp. 40-41. ACM Press, May 2012
[3] Bloom, BH, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, 13, 7, 422-426 (1970) · Zbl 0195.47003 · doi:10.1145/362686.362692
[4] De Cristofaro, E.; Gasti, P.; Tsudik, G.; Pieprzyk, J.; Sadeghi, A-R; Manulis, M., Fast and private computation of cardinality of set intersection and union, Cryptology and Network Security, 218-231 (2012), Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-642-35404-5_17
[5] Dachman-Soled, D.; Malkin, T.; Raykova, M.; Yung, M.; Abdalla, M.; Pointcheval, D.; Fouque, P-A; Vergnaud, D., Efficient robust private set intersection, Applied Cryptography and Network Security, 125-142 (2009), Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-642-01957-9_8
[6] De Cristofaro, E.; Kim, J.; Tsudik, G.; Abe, M., Linear-complexity private set intersection protocols secure in malicious model, Advances in Cryptology - ASIACRYPT 2010, 213-231 (2010), Heidelberg: Springer, Heidelberg · Zbl 1253.94044 · doi:10.1007/978-3-642-17373-8_13
[7] De Cristofaro, E.; Tsudik, G.; Sion, R., Practical private set intersection protocols with linear complexity, Financial Cryptography and Data Security, 143-159 (2010), Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-642-14577-3_13
[8] Dong, C., Chen, L., Wen, Z.: When private set intersection meets big data: an efficient and scalable protocol. In: Sadeghi, A.R., Gligor, V.D., Yung, M. (eds.) ACM CCS 2013, pp. 789-800. ACM Press, November 2013
[9] Fischlin, M.; Pinkas, B.; Sadeghi, A-R; Schneider, T.; Visconti, I.; Kiayias, A., Secure set intersection with untrusted hardware tokens, Topics in Cryptology - CT-RSA 2011, 1-16 (2011), Heidelberg: Springer, Heidelberg · Zbl 1285.68009 · doi:10.1007/978-3-642-19074-2_1
[10] Freedman, MJ; Ishai, Y.; Pinkas, B.; Reingold, O.; Kilian, J., Keyword search and oblivious pseudorandom functions, Theory of Cryptography, 303-324 (2005), Heidelberg: Springer, Heidelberg · Zbl 1079.94546 · doi:10.1007/978-3-540-30576-7_17
[11] Freedman, MJ; Nissim, K.; Pinkas, B.; Cachin, C.; Camenisch, JL, Efficient private matching and set intersection, Advances in Cryptology - EUROCRYPT 2004, 1-19 (2004), Heidelberg: Springer, Heidelberg · Zbl 1122.94416 · doi:10.1007/978-3-540-24676-3_1
[12] Frikken, KB; Katz, J.; Yung, M., Privacy-preserving set union, Applied Cryptography and Network Security, 237-252 (2007), Heidelberg: Springer, Heidelberg · Zbl 1214.94044 · doi:10.1007/978-3-540-72738-5_16
[13] Goldreich, O.: The Foundations of Cryptography, vol. 2. Cambridge University Press (2004) · Zbl 1068.94011
[14] Hazay, C.; Dodis, Y.; Nielsen, JB, Oblivious polynomial evaluation and secure set-intersection from algebraic PRFs, Theory of Cryptography, 90-120 (2015), Heidelberg: Springer, Heidelberg · Zbl 1379.94041
[15] Hazay, C., Lindell, Y.: Constructions of truly practical secure protocols using standardsmartcards. In: Ning, P., Syverson, P.F., Jha, S. (eds.) ACM CCS 2008, pp. 491-500. ACM Press, October 2008
[16] Hazay, C.; Lindell, Y., Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries, Journal of Cryptology, 23, 3, 422-456 (2010) · Zbl 1195.94058 · doi:10.1007/s00145-008-9034-x
[17] Hazay, C.; Nissim, K., Efficient set operations in the presence of malicious adversaries, Journal of Cryptology, 25, 3, 383-433 (2012) · Zbl 1272.94034 · doi:10.1007/s00145-011-9098-x
[18] Hohenberger, S.; Weis, SA; Danezis, G.; Golle, P., Honest-verifier private disjointness testing without random oracles, Privacy Enhancing Technologies, 277-294 (2006), Heidelberg: Springer, Heidelberg · doi:10.1007/11957454_16
[19] Jarecki, S.; Liu, X.; Reingold, O., Efficient oblivious pseudorandom function with applications to adaptive OT and secure computation of set intersection, Theory of Cryptography, 577-594 (2009), Heidelberg: Springer, Heidelberg · Zbl 1213.94113 · doi:10.1007/978-3-642-00457-5_34
[20] Jarecki, S.; Liu, X.; Garay, JA; De Prisco, R., Fast secure computation of set intersection, Security and Cryptography for Networks, 418-435 (2010), Heidelberg: Springer, Heidelberg · Zbl 1291.94105 · doi:10.1007/978-3-642-15317-4_26
[21] Kamara, S.; Mohassel, P.; Raykova, M.; Sadeghian, S.; Christin, N.; Safavi-Naini, R., Scaling private set intersection to billion-element sets, Financial Cryptography and Data Security, 195-215 (2014), Heidelberg: Springer, Heidelberg
[22] Kerschbaum, F.; Li, Y., Public-key encrypted bloom filters with applications to supply chain integrity, Data and Applications Security and Privacy XXV, 60-75 (2011), Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-642-22348-8_7
[23] Kerschbaum, F.: Outsourced private set intersection using homomorphic encryption. In: Youm, H.Y., Won, Y. (eds.) ASIACCS 2012, pp. 85-86. ACM Press, May 2012
[24] Kiayias, A.; Mitrofanova, A.; S. Patrick, A.; Yung, M., Testing disjointness of private datasets, Financial Cryptography and Data Security, 109-124 (2005), Heidelberg: Springer, Heidelberg · Zbl 1120.94326 · doi:10.1007/11507840_13
[25] Kissner, L.; Song, D.; Shoup, V., Privacy-preserving set operations, Advances in Cryptology - CRYPTO 2005, 241-257 (2005), Heidelberg: Springer, Heidelberg · Zbl 1145.94471 · doi:10.1007/11535218_15
[26] Many, D., Burkhart, M., Dimitropoulos, X.: Tech. Rep. TIK report no. 345, ETH Zurich, Switzerland (2012)
[27] Papapetrou, O.; Siberski, W.; Nejdl, W., Cardinality estimation and dynamic length adaptation for bloom filters, Distributed and Parallel Databases, 28, 2-3, 119-156 (2010) · doi:10.1007/s10619-010-7067-2
[28] Pinkas, B., Schneider, T., Zohner, M.: Faster private set intersection based on OT extension. In: Proceedings of the 23rd USENIX Security Symposium, San Diego, CA, USA, August 20-22, pp. 797-812. USENIX Association (2014)
[29] Tarkoma, S.; Rothenberg, CE; Lagerspetz, E., Theory and practice of bloom filters for distributed systems, IEEE Communications Surveys and Tutorials, 14, 1, 131-155 (2012) · doi:10.1109/SURV.2011.031611.00024
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.