Abstract
Both scalability and flexibility become crucial for privacy preserving protocols in the age of Big Data. Private Set Intersection (PSI) is one of important privacy preserving protocols. Usually, PSI is executed by 2-parties, a client and a server, where both a client and a server compute jointly the intersection of their private sets and at the end only the client learns the intersection and the server learns nothing. From the scalable point of view, however, the number of parties are not limited to two. In this paper, we propose a scalable and flexible multiparty PSI (MPSI) for the first time: the data size of each party is independent to each other and the computational complexity is independent to the number of parties. We also propose d-and-over MPSI for the first time.
This study is partly supported by Grant-in-Aid for Scientific Research (C) i15K00183) and (15K00189).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Azar, Y., et al.: Balanced allocations. SIAM journal on computing 29(1), 180–200 (1999)
Bloom, B.H.: Space/time trade-offs in hash coding with allowable errors. Communications of the ACM 13(7), 422–426 (1970)
Broder, A., Mitzenmacher, M.: Network applications of bloom filters: A survey. Internet mathematics 1(4), 485–509 (2004)
Cramer, R., et al.: A secure and optimally efficient multi-authority election scheme. European transactions on Telecommunications 8(5), 481–490 (1997)
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)
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)
Dong, C., et al.: When private set intersection meets big data: an efficient and scalable protocol. In: ACMCCS 2013, pp. 789–800. ACM (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, Heidelberg (2015)
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)
Goldreich, O.: Secure multi-party computation. Manuscript, Preliminary version (1998)
Goldwasser, S., Micali, S.: Probabilistic encryption. Journal of computer and system sciences 28(2), 270–299 (1984)
Ishai, Y., Kilian, J., Nissim, K., Petrank, E.: Extending oblivious transfers efficiently. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 145–161. Springer, Heidelberg (2003)
Kerschbaum, F.: Outsourced private set intersection using homomorphic encryption. In: ACMCCS 2012, pp. 85–86. ACM (2012)
Kissner, L., Song, D.: Privacy-preserving set operations. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 241–257. Springer, Heidelberg (2005)
Many, D., et al.: Fast private set operations with sepia. Technical Report 345 (2012)
Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, p. 223. Springer, Heidelberg (1999)
Rabin, M.O.: How to exchange secrets with oblivious transfer. Tech. Memo, TR-81 (1981)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Miyaji, A., Nishida, S. (2015). A Scalable Multiparty Private Set Intersection. In: Qiu, M., Xu, S., Yung, M., Zhang, H. (eds) Network and System Security. NSS 2015. Lecture Notes in Computer Science(), vol 9408. Springer, Cham. https://doi.org/10.1007/978-3-319-25645-0_26
Download citation
DOI: https://doi.org/10.1007/978-3-319-25645-0_26
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-25644-3
Online ISBN: 978-3-319-25645-0
eBook Packages: Computer ScienceComputer Science (R0)