Abstract
Private Set Intersection Cardinality (PSI-CA) and Private Set Union Cardinality (PSU-CA) are cryptographic tasks whose goals are to compute the cardinalities of the intersection and the union of two private sets, respectively. There are lots of important and practical applications of PSI-CA and PSU-CA, such as privacy-preserving data mining and data analysis. The existing classical PSI-CA and PSU-CA protocols could not resist the attacks of quantum computers. In this article, we present a novel quantum approach to solve the PSI-CA and PSU-CA problems based on the principle of quantum mechanics, which can resist well-known quantum attacks. The proposed protocols take Bell states as quantum resources and only need to apply simple single-particle operators and Bell-based measurements. Therefore, it is feasible to implement these protocols with the present technology.
Graphical abstract
Similar content being viewed by others
References
R.H. Shi, Y. Mu, H. Zhong, S. Zhang, J. Cui, Inform. Sci. 370–371, 147 (2016)
M.E. Wu, S.Y. Chang, C.J. Lu, H.M. Sun, Inform. Sci. 275, 348 (2014)
M.J. Freedman, K. Nissim, B. Pinkas, Efficient private matching and set intersection, in Advances in Cryptology: EUROCRYPT 2004, LNCS 3027 (Springer, Berlin, 2004), pp. 1–19
E.D. Cristofaro, P. Gasti, G. Tsudik, Fast and private computation of cardinality of set intersection and union, in Proceedings of the Cryptology and Network Security (CANC 2010), LNCS 7712 (Springer, Berlin, 2012), pp. 218–231
L. Kissner, D. Song, Privacy-preserving set operations, in Advances in Cryptology: Crypto 2005, LNCS 3621 (Springer, Berlin, 2005), pp. 241–257
J. Vaidya, C. Clifton, J. Comput. Secur. 13, 593 2005
S. Zander, L.L.H. Andrew, G. Armitage, Scalable Private Set Intersection Cardinality for Capture-Recapture with Multiple Private Datasets, 2013, https://doi.org/caia.swin.edu.au/reports/130930A /CAIA-TR-130930A.pdf
S.K. Debnath, R. Dutta, Secure and efficient private set intersection cardinality using bloom filter, in Proceedings of the Information Security (ISC 2015), LNCS 9290 (Springer, Berlin, 2015), pp. 209–226
P.W. Shor, Algorithms for quantum computation: discrete logarithms and factoring, in Proceedings of the 35th Annual Symposium on the Foundations of Computer Science (IEEE, Piscataway, NJ, 1994), pp. 124–134
L.K. Grover, A fast quantum mechanical algorithm for database search, in Proceedings of the 28th Annual ACM Symposium on Theory of Computing (ACM, New York, 1996), pp. 212–219
H.K. Lo, Phys. Rev. A 56, 1154 (1997)
R. Colbeck, Phys. Rev. A 76, 062308 (2007)
H. Buhrman, M. Christandl, C. Schaffner, Phys. Rev. Lett. 109, 160501 (2012)
R.H. Shi, Int. J. Theor. Phys. 56, 1208 (2017)
C.H. Bennett, G. Brassard, Quantum cryptography: public key distribution and coin tossing, in Proceedings of the IEEE International Conference on Computers, Systems, and Signal Processing (IEEE, New York, 1984), pp. 175–179
R.H. Shi, Y. Mu, H. Zhong et al. Phys. Rev. A 94, 066301 (2016)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Shi, Rh. Quantum private computation of cardinality of set intersection and union. Eur. Phys. J. D 72, 221 (2018). https://doi.org/10.1140/epjd/e2018-90380-7
Received:
Published:
DOI: https://doi.org/10.1140/epjd/e2018-90380-7