Abstract
Private set operation (PSO) protocols provide a natural way of securely performing operations on data sets, such that crucial details of the input sets are not revealed. Such protocols have an ever-increasing number of practical applications, particularly when implementing privacy-preserving data mining schemes. Protocols for computing private set operations have been prevalent in multi-party computation literature over the past decade, and in the case of private set intersection (PSI), have become practically feasible to run in real applications. In contrast, other set operations such as union have received less attention from the research community, and the few existing designs are often limited in their feasibility. In this work we aim to fill this gap, and present a new technique using Bloom filter data structures and additive homomorphic encryption to develop the first private set union protocol with both linear computation and communication complexities. Moreover, we show how to adapt this protocol to give novel ways of computing PSI and private set intersection/union cardinality with only minor changes to the protocol computation. Our work resembles therefore a toolkit for scalable private set computation with linear complexities, and we provide a thorough experimental analysis that shows that the online phase of our designs is practical up to large set sizes.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
It is however possible to enforce bilateral output by running the protocol twice and swapping the roles.
- 2.
This can be easily done by padding the smaller of the two sets up to the size of the larger one.
- 3.
- 4.
- 5.
We do not provide estimates for the 2048 bit case since they are derivable by doubling the 1024 bit estimates.
References
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
Bloom, B.H.: Space/time trade-offs in hash coding with allowable errors. Commun. ACM 13(7), 422–426 (1970)
Bose, P., Guo, H., Kranakis, E., Maheshwari, A., Morin, P., Morrison, J., Smid, M.H.M., Tang, Y.: On the false-positive rate of bloom filters. Inf. Process. Lett. 108(4), 210–213 (2008)
Brickell, J., Shmatikov, V.: Privacy-preserving graph algorithms in the semi-honest model. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 236–252. Springer, Heidelberg (2005). doi:10.1007/11593447_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). doi:10.1007/978-3-642-35404-5_17
Davidson, A., Fenn, G., Cid, C.: A model for secure and mutually beneficial software vulnerability sharing. In: Proceedings of the 2016 ACM on Workshop on Information Sharing and Collaborative Security (WISCS 2016), pp. 3–14, New York, NY, USA. ACM (2016)
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). doi:10.1007/978-3-642-14577-3_13
Debnath, S.K., Dutta, R.: Efficient private set intersection cardinality in the presence of malicious adversaries. In: Au, M.-H., Miyaji, A. (eds.) ProvSec 2015. LNCS, vol. 9451, pp. 326–339. Springer, Cham (2015). doi:10.1007/978-3-319-26059-4_18
Debnath, S.K., Dutta, R.: Secure and efficient private set intersection cardinality using bloom filter. In: Lopez, J., Mitchell, C.J. (eds.) ISC 2015. LNCS, vol. 9290, pp. 209–226. Springer, Cham (2015). doi:10.1007/978-3-319-23318-5_12
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 (2013)
Egert, R., Fischlin, M., Gens, D., Jacob, S., Senker, M., Tillmanns, J.: Privately computing set-union and set-intersection cardinality via bloom filters. In: Foo, E., Stebila, D. (eds.) ACISP 2015. LNCS, vol. 9144, pp. 413–430. Springer, Cham (2015). doi:10.1007/978-3-319-19962-7_24
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
Frikken, K.: Privacy-preserving set union. In: Katz, J., Yung, M. (eds.) ACNS 2007. LNCS, vol. 4521, pp. 237–252. Springer, Heidelberg (2007). doi:10.1007/978-3-540-72738-5_16
Hazay, C., Nissim, K.: Efficient set operations in the presence of malicious adversaries. J. Cryptol. 25(3), 383–433 (2012)
Hormozdiari, F., Joo, J.W.J., Wadia, A., Guan, F., Ostrovsky, R., Sahai, A., Eskin, E.: Privacy preserving protocol for detecting genetic relatives using rare variants. Bioinformatics 30(12), 204–211 (2014)
Huang, Y., Evans, D., Katz, J.: Private set intersection: are garbled circuits better than custom protocols? In: NDSS 2012. The Internet Society, February 2012
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
Kissner, L., Song, D.: Privacy-preserving set operations. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 241–257. Springer, Heidelberg (2005). doi:10.1007/11535218_15
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 2016, pp. 818–829. ACM Press (2016)
Meadows, C.A.: A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party. In: Proceedings of the 1986 IEEE Symposium on Security and Privacy, Oakland, California, USA, April 7–9, 1986, pp. 134–137 (1986)
Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999). doi:10.1007/3-540-48910-X_16
Pinkas, B., Schneider, T., Segev, G., Zohner, M.: Phasing: private set intersection using permutation-based hashing. In: USENIX Security Symposium, pp. 515–530. USENIX Association (2015)
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, 20–22 August, 2014, pp. 797–812 (2014)
Rindal, P., Rosulek, M.: Improved private set intersection against malicious adversaries. Cryptology ePrint Archive, Report 2016/746 (2016). http://eprint.iacr.org/2016/746
Seo, J.H., Cheon, J.H., Katz, J.: Constant-round multi-party private set union using reversed laurent series. In: Fischlin, M., Buchmann, J., Manulis, M. (eds.) PKC 2012. LNCS, vol. 7293, pp. 398–412. Springer, Heidelberg (2012). doi:10.1007/978-3-642-30057-8_24
Acknowledgements
The authors would like to thank Sumit Debnath, Mikkel Lambaek and Claudio Orlandi for their help in establishing problems with previous versions of this work. This work was supported by the EPSRC and the UK Government as part of the Centre for Doctoral Training in Cyber Security at Royal Holloway, University of London (EP/K035584/1).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Davidson, A., Cid, C. (2017). An Efficient Toolkit for Computing Private Set Operations. In: Pieprzyk, J., Suriadi, S. (eds) Information Security and Privacy. ACISP 2017. Lecture Notes in Computer Science(), vol 10343. Springer, Cham. https://doi.org/10.1007/978-3-319-59870-3_15
Download citation
DOI: https://doi.org/10.1007/978-3-319-59870-3_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-59869-7
Online ISBN: 978-3-319-59870-3
eBook Packages: Computer ScienceComputer Science (R0)