Secure two-party integer comparison protocol without any third party. (English) Zbl 1508.81531
Summary: Secure two-party integer comparison is a primitive problem of secure multiparty computations that enables two parties to decide whether \(x>y\) without disclosing anything about \(x\) and \(y\), where \(x\) and \(y\) are two integers held privately by two parties, respectively. This paper presents a novel and efficient quantum protocol for secure two-party integer comparison without any third party. This protocol tactfully adopts the ideas of quantum private query so that it achieves an exponential reduction in communication complexity because it only requires \(O(1)\) communication cost.
Keywords:
quantum computing; secure multiparty computation; private comparison; information-sharing; privacy-preservingReferences:
| [1] | Yao, A.: Protocols for secure computations. In: Proceedings of 23th Annual Symposium on Foundations of Computer Science (FOCS ’82), Chicago, USA, pp. 160-164. IEEE Computer Society Press, New York (1982) |
| [2] | Garay, J., Schoenmakers, B., Villagas, J.: Practical and secure solutions for integer comparison. In: Proceedings of 10th International Conference on Practice and Theory in Public-Key Cryptography, Beijing, China, LNCS, vol. 4450, pp. 330-342. Springer, Berlin (2007) · Zbl 1161.94399 |
| [3] | Damgard, I.; Geisler, M.; Kroigard, M., Homomorphic encryption and secure comparison, Int. J. Appl. Cryptogr., 1, 1, 22-31 (2008) · Zbl 1178.94185 · doi:10.1504/IJACT.2008.017048 |
| [4] | Damgard, I.; Geisler, M.; Kroigard, M., A correction to ‘efficient and secure comparison for on-line auctions’, Int. J. Appl. Cryptogr., 1, 4, 323-324 (2009) · Zbl 1171.94343 · doi:10.1504/IJACT.2009.028031 |
| [5] | Katti, R.S., Abaei, C.: Secure comparison without explicit XOR (2012). arXiv:1204.2854 |
| [6] | Shor, P.W.: Algorithms for quantum computation: discrete Logarithms and factoring. In: Proceedings of 35th Annual Symposium on the Foundations of Computer Science, Santa Fe, New Mexico, pp. 124-134. IEEE, New York (1994) |
| [7] | Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of 28th Annual ACM Symposium on Theory of Computing, Coimbra, Portugal, pp. 212-219. ACM, New York (1996) · Zbl 0922.68044 |
| [8] | Bennett, C.H., Brassard, G.: Quantum cryptography public-key distribution and tossing. In: Proceedings of IEEE International Conference on Computers, Systems, and Signal Processing, Bangalore, India, pp. 175-179. IEEE, New York (1984) · Zbl 1306.81030 |
| [9] | Lo, HK, Insecurity of quantum secure computations, Phys. Rev. A, 56, 1154-1162 (1997) · doi:10.1103/PhysRevA.56.1154 |
| [10] | Colbeck, R., Impossibility of secure two-party classical computation, Phys. Rev. A, 76, 062308 (2007) · doi:10.1103/PhysRevA.76.062308 |
| [11] | Buhrman, H.; Christandl, M.; Schaffner, C., Complete insecurity of quantum protocols for classical two-party computation, Phys. Rev. Lett., 109, 160501 (2012) · doi:10.1103/PhysRevLett.109.160501 |
| [12] | Crepeau, C., Gottesman, D., Smith, A.: Secure multi-party quantum computing. In: Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing (STOC’02), Montreal, QC, Canada, pp. 643-652. ACM, New York (2002) · Zbl 1192.94115 |
| [13] | Ben-or, M., Crepeau, C., Gottesman, D., Hassidim, A., Smith, A.: Secure multiparty quantum computation with (only) a strict honest majority. In: Proceedings of 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), Washington, DC, USA. IEEE Computer Society, New York, pp. 249-260 (2006) |
| [14] | Unruh, D.: Universally composable quantum multi-party computation. In: Proceedings of Advances in Cryptology—EUROCRYPT 2010, Riviera, French, LNCS, vol. 6110, pp. 486-505. Springer, Berlin (2010) · Zbl 1280.94096 |
| [15] | Kiktenko, EO; Pozhar, NO; Anufriev, MN, Quantum-secured blockchain, Quantum Sci. Technol., 3, 3, 035004 (2018) · doi:10.1088/2058-9565/aabc6b |
| [16] | Shi, RH; Zhang, M., Privacy-preserving quantum sealed-bid auction based on Grover’s search algorithm, Sci. Rep., 9, 7626 (2019) · doi:10.1038/s41598-019-44030-8 |
| [17] | Vaccaro, JA; Spring, J.; Chefles, A., “Quantum protocols for anonymous voting and surveying, Phys. Rev. A, 75, 1, 012333 (2007) · doi:10.1103/PhysRevA.75.012333 |
| [18] | Chen, S.Y., Yoo, S.: Federated quantum machine learning. arXiv:2103.12010 (2021) |
| [19] | Giovannetti, V.; Lloyd, S.; Maccone, L., Quantum private queries, Phys. Rev. Lett., 100, 230502 (2008) · Zbl 1228.81143 · doi:10.1103/PhysRevLett.100.230502 |
| [20] | Olejnik, L., Secure quantum private information retrieval using phase-encoded queries, Phys. Rev. A, 84, 022313 (2011) · doi:10.1103/PhysRevA.84.022313 |
| [21] | Shi, RH; Mu, Y.; Zhong, H.; Zhang, S., Comment on “Secure quantum private information retrieval using phase-encoded queries”, Phys. Rev. A, 94, 6, 066301 (2016) · doi:10.1103/PhysRevA.94.066301 |
| [22] | Brassard, G., Høyer, P., Tapp, A.: Quantum counting. In: Proceedings of International Colloquium on Automata, languages, and Programming (ICALP), Lecture Notes in Computer Science, vol. 1443, pp. 820-831, Springer, Berlin (1998) · Zbl 1508.68118 |
| [23] | Shi, RH; Mu, Y.; Zhong, H., Quantum private set intersection cardinality and its application to anonymous authentication, Inf. Sci., 370-371, 147-158 (2016) · Zbl 1428.81071 · doi:10.1016/j.ins.2016.07.071 |
| [24] | Giovannetti, V.; Lloyd, S.; Maccone, L., Quantum random access memory, Phys. Rev. Lett., 100, 16, 160501 (2008) · Zbl 1228.81125 · doi:10.1103/PhysRevLett.100.160501 |
| [25] | Hong, F.; Xiang, Y.; Zhu, Z., Robust quantum random access memory, Phys. Rev. A, 86, 1, 010306(R) (2012) · doi:10.1103/PhysRevA.86.010306 |
| [26] | Jiang, N.; Pu, Y-F; Chang, W., Experimental realization of 105-qubit random access quantum memory, NPJ Quantum Inf., 2, 28 (2019) · doi:10.1038/s41534-019-0144-0 |
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.
