×
Wang, Cheng; Zhou, Ri-Gui

Secure multi-party convex hull protocol based on quantum homomorphic encryption. (English) Zbl 1508.81757

Quantum Inf. Process. 22, No. 1, Paper No. 24, 12 p. (2023).
Summary: Secure multi-party computational geometry (SMCG) is a branch of secure multi-party computing (SMC). The protocol is designed for secure multi-party convex hull computation in SMCG. Firstly, a secure two-party value comparison protocol based on quantum homomorphic encryption is proposed. Due to the nature of quantum homomorphic encryption, the protocol can well protect the security of data in the execution of quantum circuits and the interaction between parties. The result is announced by a semi-trusted third party. Using the value comparison protocol designed above, a secure multi-party convex hull protocol is proposed, which can safely solve the common convex hull of multiple user point sets. Then the correctness and security analysis are carried out, which proves that the protocol is safe and reliable.

Cited in 2 Documents

MSC:

81P94 Quantum cryptography (quantum-theoretic aspects)

Keywords:

secure multi-party computing; computational geometry; convex hull; quantum homomorphic encryption

Software:

polymake
Cite Review PDF
Full Text: DOI

References:

[1] Yao, AC, Protocols for secure computations, Annu. Symp. Found. Comput. Sci. Proc. (1982) · doi:10.1109/sfcs.1982.38
[2] Atallah, MJ; Du, W.; Dehne, F.; Sack, J-R; Tamassia, R., Secure multi-party computational geometry, Algorithms and data structures, 165-179 (2001), Berlin: Springer, Berlin · Zbl 0997.68537 · doi:10.1007/3-540-44634-6_16
[3] Troncoso-Pastoriza, JR; Katzenbeisser, S.; Celik, M.; Lemma, A., A secure multidimensional point inclusion protocol, MM Sec’07 Proc. Multimed. Secur. Work. (2007) · doi:10.1145/1288869.1288884
[4] Luo, Y-L; Huang, L-S; Zhong, H., Secure two-party point-circle inclusion problem, J. Comput. Sci. Technol., 22, 88-91 (2007) · doi:10.1007/s11390-007-9011-0
[5] Pawlik, A.; Kozik, J.; Krawczyk, T.; Lasoń, M.; Micek, P.; Trotter, WT; Walczak, B., Triangle-free geometric intersection graphs with large chromatic number, Discret. Comput. Geom., 50, 714-726 (2013) · Zbl 1275.05038 · doi:10.1007/s00454-013-9534-9
[6] Boneh, D.A.N., Franklin, M.: Polynomial-time approximation schemes for geometric intersection graphs. 32, 586-615 (2003) · Zbl 1046.94008
[7] Tao, Y.; Yi, K.; Sheng, C.; Kalnis, P., Efficient and accurate nearest neighbor and closest pair search in high-dimensional space, ACM Trans. Database Syst. (2010) · doi:10.1145/1806907.1806912
[8] Li, C.; Ni, R., Derivatives of generalized distance functions and existence of generalized nearest points, J. Approx. Theory., 115, 44-55 (2002) · Zbl 1006.46015 · doi:10.1006/jath.2001.3651
[9] Qi, W.; Yonglong, L.; Liusheng, H., Privacy-preserving protocols for finding the convex hulls, ARES 2008-3rd Int. Conf. Availab. Secur. Reliab. Proc. (2008) · doi:10.1109/ARES.2008.11
[10] Assarf, B.; Gawrilow, E.; Herr, K.; Joswig, M.; Lorenz, B.; Paffenholz, A.; Rehn, T., Computing convex hulls and counting integer points with polymake, Math. Program. Comput., 9, 1-38 (2017) · Zbl 1370.90009 · doi:10.1007/s12532-016-0104-z
[11] Löffler, M.; Van Kreveld, M., Largest and smallest convex hulls for imprecise points, Algorithmica (New York)., 56, 235-269 (2010) · Zbl 1185.65036 · doi:10.1007/s00453-008-9174-2
[12] Park, CS; Park, R.; Krishna, G., Constitutive expression and structural diversity of inducible isoform of nitric oxide synthase in human tissues, Life Sci., 59, 219-225 (1996) · doi:10.1016/0024-3205(96)00287-1
[13] Demartin, F.; Maltoni, F.; Mawatari, K.; Zaro, M., Higgs production in association with a single top quark at the LHC, Eur. Phys. J. C., 75, 212-219 (2015) · doi:10.1140/epjc/s10052-015-3475-9
[14] Shi, R.; Mu, Y.; Zhong, H.; Cui, J.; Zhang, S., Privacy-preserving point-inclusion protocol for an arbitrary area based on phase-encoded quantum private query, Quantum Inf. Process. (2017) · Zbl 1398.81075 · doi:10.1007/s11128-016-1476-8
[15] wan Peng, Z.; Shi, R.; Zhong, H.; Cui, J.; Zhang, S., A novel quantum scheme for secure two-party distance computation, Quantum Inf. Process., 16, 1-12 (2017) · Zbl 1382.81052 · doi:10.1007/s11128-017-1766-9
[16] Chen, B.; Yang, W.; Huang, L., Cryptanalysis and improvement of the novel quantum scheme for secure two-party distance computation, Quantum Inf. Process., 18, 1-14 (2019) · Zbl 1417.81079 · doi:10.1007/s11128-018-2148-7
[17] Peng, Z.; Shi, R.; Wang, P.; Zhang, S., A novel quantum solution to secure two-party distance computation, Quantum Inf. Process., 17, 1-12 (2018) · Zbl 1448.81289 · doi:10.1007/s11128-018-1911-0
[18] Liu, W.; Xu, Y.; Yang, JCN; Yu, W.; Chi, L., Privacy-preserving quantum two-party geometric intersection, Comput Mater Contin., 60, 1237-1250 (2019)
[19] Liang, M., Quantum fully homomorphic encryption scheme based on universal quantum circuit, Quantum Inf. Process., 14, 2749-2759 (2015) · Zbl 1327.81163 · doi:10.1007/s11128-015-1034-9
[20] Boykin, PO; Roychowdhury, V., Optimal encryption of quantum bits, Phys. Rev. A At. Mol. Opt. Phys. (2003) · doi:10.1103/PhysRevA.67.042317
[21] Nielsen, MA; Chuang, I.; Grover, LK, Quantum computation and quantum information, Am. J. Phys., 70, 5, 558-559 (2002) · doi:10.1119/1.1463744
[22] Yuan, S.; Gao, S.; Wen, C.; Wang, Y.; Qu, H.; Wang, Y., A novel fault-tolerant quantum divider and its simulation, Quantum Inf. Process., 2, 1-15 (2022) · Zbl 1508.81566 · doi:10.1007/s11128-022-03523-8
[23] Xu, G.; Yun, F.; Chen, XB; Xu, S.; Wang, J.; Shang, T.; Chang, Y.; Dong, M., Secure multi-party quantum summation based on quantum homomorphic encryption, Intell. Autom. Soft Comput., 34, 531-541 (2022) · doi:10.32604/iasc.2022.028264
[24] Gong, C.; Du, J.; Dong, Z.; Guo, Z.; Gani, A.; Zhao, L.; Qi, H., Grover algorithm-based quantum homomorphic encryption ciphertext retrieval scheme in quantum cloud computing, Quantum Inf. Process., 19, 105 (2020) · doi:10.1007/s11128-020-2603-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.