1. Introduction
With the innovation and development of new generation information technologies such as the blockchain, big data, and artificial intelligence, data information in various fields of society is constantly enriched and information sharing value is increasing. However, information privacy leakage is getting more and more attention. Secure multi-party computation (MPC) is one of the important tools to protect information data privacy and finish collaborative computing [1,2,3,4,5].
The earliest MPC problem is the Millionaire problem proposed by Professor Yao [6]. Goldreich and other scholars [7,8] are also involved in the research on MPC. There are many aspects of researching MPC, including secure computing applications [9,10], secure data mining [11,12], secure scientific computing [13,14,15,16,17,18], secure multi-party computational geometry problems [19,20], etc. MPC is widely used to solve many practical problems [21,22,23,24]. As tools in cryptography, homomorphic secret sharing (HSS) [25,26], oblivious transfer (OT) [27], and the cut-choose method [28] have become effective tools to combat malicious participants in MPC.
The MPC protocol of Manhattan distance is a typical problem of secure multi-party computational geometry problems [19,20,29,30,31]. In machine learning, Manhattan distance is often necessary to compute a similarity measure across different samples when making a classification, which requires computing the “distance” across samples, and it is a practical method for distance calculation. In early computer graphics, screens were constructed from pixel dots whose coordinates were generally integers and it was costly to carry out float operations, but using Manhattan distance, which requires only addition and subtraction, can greatly improve the operation speed. Therefore, the study of Manhattan distance has extremely important theoretical value and practical significance.
At present, there is some research on the secure computing of Manhattan distance [29,30,31], and the existing protocols are designed in the semi-honest model. Consequently, it is particularly significant to study the MPC protocol of Manhattan distance to resist malicious attacks. In this paper, an MPC protocol for calculating the Manhattan distance is designed. The contributions are as follows:
Firstly, the protocol in Reference [29] is analyzed and found that some situations may be attacked by malicious participants.
According to the possible attacks of malicious participants, we design a new MPC protocol for computing the Manhattan distance can resist malicious attacks. In the process of designing the protocol, we use the Goldwasser–Micali and Paillier encryption algorithm, the cut-choose and zero-knowledge proof methods are used. The secure computation of the Manhattan distance will be converted into the Millionaires’ problem to further improve the efficiency of the protocol.
The real/ideal model paradigm method is used to prove the security of the proposed malicious model MPC protocol. The performance and efficiency of the protocol are analyzed and simulated by experiments compared with existing protocols.
2. Related Work
Manhattan distance is a secure multi-party computational geometry problem. Manhattan distance can be seen everywhere in real life, which can be called the CityBlock distance or the taxi distance, that is, the actual distance as taxis pass from one crossroads to another. In a standard coordinate system, the sum of the absolute wheelbase of two points, which is the distance of two points in the north-south direction plus the distance in the east-west direction, which is the Manhattan distance between two points, can be noted as . As shown in Figure 1.
In Fang [29], the authors designed a new coding method. With the help of homomorphism, the problem of calculating the Manhattan distance between two points is flexibly and skillfully transformed into calculating the Hamming distance of two vectors. This conversion idea not only improves the protocol efficiency but also prevents the disclosure of intermediate information. However, the protocol cannot resist malicious attacks.
Reference [30] invoked the absolute value of the difference and designed the MPC of Manhattan distance under different restrictions. The protocol’s performance is poor.
Reference [31] designed a new graph encryption scheme for shortest distance queries based on a 2-hop cover labeling, which uses symmetric-key primitives. This scheme can obtain the shortest distance between any two points in the graph, but it cannot resist malicious attacks.
In the above references, the MPC protocols of Manhattan distance is designed based on the semi-honest model, which cannot resist the attack of malicious participants. The protocol for secure computing Manhattan distance under the malicious model needs to be designed. The protocol proposed in reference [32] is a classic problem in the malicious model, but it is used to solve the Millionaire problem, which is different from the problem scenario we solve.
3. Preparatory Knowledge
3.1. Paillier Encryption Algorithm
Paillier proposed a probabilistic encryption algorithm [33] to solve the problem of composite residue classes. It has additive homomorphism.
Preparation: Select two large prime numbers and , satisfying , calculate , , , and defining function . A random number is selected, with as the public key, and as the private key.
Encryption: A random number is selected to perform the encryption operation .
Decryption: The private key is used for decryption to obtain the ciphertext: .
Addition homomorphism: .
3.2. Goldwasser–Micali Encryption Algorithm
The Goldwasser–Micali (GM) encryption algorithm [34] has XOR homomorphism.
Preparation: Two large prime numbers and are selected to get . And (where is a subset of Jacobi containing elements of ) is selected as part of the public key. The private key of the algorithm is and the public key is .
Encryption: For in binary representation, the random number is selected to encrypt the message :
.
Decryption: The private key is used for decryption to obtain the ciphertext:
.
Among them, is defined as follows:
XOR homomorphism: .
3.3. Zero-Knowledge Proof
The zero-knowledge proof means that in the process of interaction between the certifier and the verifier, when the certifier does not provide effective information, the verifier believes that the conclusion is correct through the interaction of both parties, then we say that the process has realized the zero-knowledge proof. In the process of interaction between the two sides, the information obtained by the verifier is only the right and wrong of the conclusion. For example, the zero-knowledge proof protocol [35] is as follows, where , .
The certifier selects random numbers and , calculates , , and finally publishes .
The verifier can verify whether is established. If it is true, the verifier believes that the conclusion is correct, that is, the certifier knows the secret .
3.4. Encoding
To study the MPC protocol of Manhattan distance, the encoding method is used to further simplify the research problem. The following methods are the coding rules and calculation principles of this protocol.
3.4.1. Encoding Rule
A universal set , , where . And the abscissa and ordinate of points and are . Next, take as an example to introduce the coding method.
Point can be constructed as an array according to the full set , and its construction method is as follows: If , , set , ; if , , set , .
Then can be coded as .
3.4.2. Calculation Principle
The universal set , Alice holds , Bob holds , and .
is coded as ; is coded as .
Then, the Manhattan distance between points and can be calculated according to the following formula:
(1)
3.5. Security Definition under the Malicious Model
Under the malicious model, the widely accepted security definition is the real /ideal model paradigm method [32].
For in the ideal protocol, if can be recognized in the actual protocol, so that:
(2)
At this time, the protocol can be said to safely calculate the function , where and are the probability polynomials constructed under the actual protocol and the ideal protocol respectively; and are the information owned by both parties; is the function of executing ; and is the auxiliary input information. refers to that in the ideal situation the participant uses strategy to calculate with the participation of auxiliary input information . During the interaction between and , the output result generated is recorded as .
4. The MPC Protocol of Computing Manhattan Distance under the Semi-Honest Model
In Reference [29], the method of calculating the Manhattan distance between two points is converted into the Hamming distance between vectors. The specific MPC protocol is as follows (Algorithm 1):
Algorithm 1 Securely computing the Manhattan distance under the semi-honest model |
Input: Alice owns point
and Bob owns point
.
|
This protocol is secure for Alice and Bob under the semi-honest model. However, if either Alice or Bob is malicious, the protocol will no longer be secure. Solutions need to be designed for possible malicious behavior.
5. The MPC Protocol of Computing Manhattan Distance under the Malicious Model
Ideas: This part first analyzes the possible malicious attacks of the semi-honest model protocol, designs the corresponding countermeasures to resist the malicious attacks, and finally makes the malicious participant unable to attack or be found (Note: the case where participants provided incorrect input cannot be considered, because this could not be avoided under the ideal model).
Possible malicious attacks in Algorithm 1 (as shown in Figure 2):
In Step 3 of Algorithm 1, the result can only be calculated by Alice (Bob has no private key), which is unfair to Bob.
There may be a malicious attack in step 3, that is, Alice may tell Bob the wrong calculation result or terminate the protocol. In the end, Alice gets the right result, while Bob may get the wrong result or not.
To prevent the above attacks, the solution is to use the GM and Paillier encryption algorithm, utilizing the zero-knowledge proof and cut-choose method.
5.1. Specific Protocol
The specific protocol is as follows (Algorithm 2):
Algorithm 2 Securely computing the Manhattan distance under the malicious model |
Input: Alice owns point and Bob owns point .
|
5.2. Correctness Analysis
The following is a correctness analysis of Algorithm 2:
The main purpose of the first six steps in Algorithm 2 is that Alice and Bob calculate the Manhattan distance respectively. In this process, Alice and Bob decrypt using their own GM private key, so they cannot get each other’s information. At the same time, in order to prevent the other party from obtaining its own information, the obtained ciphertext is randomly scrambled in steps 2 and 5 and then sent to the other party.
In 7–16 steps, the problem of calculating Manhattan distance has been skillfully transformed into the socialist millionaires’ problem.
In step 13, Alice must calculate correctly, otherwise, it cannot be proved by the zero-knowledge, that is, cheating is impossible. If in the remaining group also satisfies and Bob selects , Bob can calculate after publishing .
In this process, if Alice wants to successfully implement the malicious behavior, she can only select a that does not meet the requirements, which is not found in the verification in step 8 and is selected by Bob in step 10, so Bob will not get the correct result. But Alice cannot get , because is unsolvable (an equation has two unknown numbers).
If Alice uses the above method to cheat, the maximum success rate of deception is that in group , groups meet the requirements, and only one group does not meet the requirements, that is, the maximum probability is . When the probability of success is the largest (i.e., one group does not meet the requirements), when the probability of success of deception is and five groups do not meet the requirements, the probability of success of deception is reduced to . When , these two probabilities are reduced to and respectively. If the group greater than does not meet the requirements, the probability of successful deception will be reduced to 0 (it will always be found in the verification stage). Similarly, Bob’s probability of successful malicious behavior is the same as Alice’s. Therefore, the protocol is secure.
5.3. Example Description
Suppose Alice holds , Bob holds , and the full set is . The output should be .
Preparation:
Alice and Bob respectively generate the public and private keys and of the GM encryption system and send their public keys to each other. Alice generates the public key and private key of Paillier encryption system and calculates . Similarly, Bob generates , , and calculates . Alice and Bob exchange and .
Convert points to vectors:
Alice constructs the vector of point according to the coding rules. Bob constructs the vector of point according to the coding rules.
Protocol Start:
Alice encrypts vector with to get , and sends to Bob.
Bob encrypts vector with to obtain: , and calculates the ciphertext based on the XOR homomorphism of GM encryption system. Bob randomly disturbs the sequence of elements in to get and sends it to Bob.
Alice decrypts term by term using to get and calculates: .
Bob encrypts vector with to get: , and sends to Alice.
Alice encrypts vector with to obtain: , and calculates the ciphertext . Alice randomly disturbs the sequence of elements in to get and then sent it to Bob.
Bob decrypts term by term with to obtain and calculates .
In steps 7–12, Alice and Bob follow Algorithm 2, which will not be described in detail.
In Algorithm 2, Alice and Bob have the same operations, and the status of both parties is fair. Assume Alice is a malicious participant to explain. Alice’s possible malicious behaviors include: using the wrong to calculate in step 11, using the wrong to calculate in step 13, etc. Then Alice cannot prove through the zero-knowledge proof in step 14. Bob knows that Alice is a malicious participant, and Algorithm 2 is terminated. If Algorithm 2 is not finished by step 15 and is obtained, it can be proved that both parties have implemented the protocol in a semi-honest way, and Bob will get the correct conclusion that in step 17.
5.4. Security Proof
This paper uses the real/ideal model paradigm method to prove the security.
In steps 3 and 6 of Algorithm 2, Alice and Bob get and respectively. We can take and as the input data for further execution of Algorithm 2 in the first six steps. Executing the protocol with the false and is equivalent to providing the false input, which is unavoidable under an ideal protocol, so it is not considered. Therefore, only steps 7–17 need to be proven secure.
Algorithm 2 (mentioned as) is secure.
The Algorithm is feasible only if at least one of the two parties in the protocol is not a malicious participant, that is, there are two cases that need to be proven secure.
(Case I) is honest, is dishonest. In this situation, and execute , then:
(3)
where is the sequence message received by through the zero-knowledge proof.will execute the protocol honestly, and is determined. of the ideal model is indistinguishable from of the actual protocol needs to be proven. The output of is indistinguishable from in the actual model (note: is the actual executor of . Therefore, when proving, the security of needs to be verified according to ’s behavior, that is ).
in the actual protocol is honest, so will send right to TTP. According to dishonest ’s strategy, decides what information to send to TTP. Consequently, the input of is .
TTP obtains the and calculates .
dresses up as and executes with , that is, selects and makes .
①. and execute and send the information to in step 7 based on Algorithm 2.
②. In step 8, verifies the information he asked to publish.
③. In step 9, publishes the information required by .
④. In steps 10–12, selects, calculates, and publishes the information according to .
⑤. In step 13, is calculated and published.
⑥. In step 14, the information sequence is obtained.
In the process of , the following can be got:
(4)
In steps 7–14, adopts the same encryption algorithm, , , and the zero-knowledge proof ensures , so:
(5)
(Case II) is dishonest, is honest. There are two cases:
Alice gets the result and ignores TTP, then is sent to Bob by TTP, so:
(6)
Conversely, is sent to Bob by TTP, then:
(7)
where is the sequence message received by .
is honest, is determined. of the ideal model is indistinguishable from of the actual protocol needs to be proven. That is, the output of strategy pair is indistinguishable from needs to be proven (note: is the actual executor of . Therefore, when proving, the security of needs to be verified according to ’s behavior, that is ).
According to dishonest ’s strategy, decides what information to send to TTP. Therefore, the input value sends to TTP is .
is obtained by TTP to calculate .
executes with by dressing up as , that is, selects simulation protocol and makes .
①. and execute the protocol and send in step 7 to .
②. In step 9, verifies the information he asked to publish in step 8.
③. In steps 10–12, selects, calculates, and publishes the information according to .
④. In step 13, calculates and publishes it.
⑤. In step 14, the information sequence is obtained.
In the process of the protocol, there are two situations:
receives the message and ignores TTP, so:
(8)
Conversely, that is:
(9)
In steps 7–14, uses the same encryption algorithm, so , , and ensured by the zero-knowledge proof, then:
(10)
Combining the above two cases it is proved that the output of the strategy to in the ideal model is indistinguishable from in the actual model, which meets Definition 1. Therefore, Algorithm 2 is secure. □
6. Performance Analysis
6.1. Overall Performance Comparison
This paper analyzes the performance of Algorithm 2 and protocols in other references [29,30,31], as shown in Table 1.
6.2. Computational Complexity
In Fang [29], the protocol adopts the GM encryption system. One-time encryption needs two modular multiplication operations, and one-time decryption needs modular multiplication operations. Alice’s encryption and decryption need times. Bob’s encryption needs times and the multiplication calculation is times. Therefore, a total of modular multiplication operations are carried out.
In Dou [30], its protocol adopts the Paillier encryption algorithm. For the Paillier algorithm, one-time encryption or decryption needs modular multiplications. Alice’s encryption and decryption times are and 1 respectively; Bob’s encryption times are 1. Therefore, the protocol performs a total of modular multiplication operations.
The protocol proposed by Liu [31] uses the 2HCL and symmetric-key primitives, and its computational complexity cannot be expressed by modular multiplication. In reference [31], is used to represent the length of the label in the 2HCL index and is denoted as the number of vertices in the graph, and the computational complexity of the protocol is .
In Algorithm 2 of this paper, the GM encryption system is used in steps 1–6. Alice and Bob perform encryption, decryption, and modular multiplication operations , , and times respectively. Steps 7–14 transformed the judgment conditions into the socialist Millionaires’ problem and carried out times of modular multiplication. Therefore, the protocol performs a total of modular multiplication operations.
6.3. Communication Complexity
In Fang [29], the two parties conducted two rounds of communication. In Dou [30], the two parties conducted three rounds of communication. In Liu [31], the number of communication rounds between the client-side and the server-side are three rounds. In Algorithm 2, four rounds of communication are carried out. Table 2 shows the specific comparison.
6.4. Experimental Simulation
We use Python language to simulate Algorithm 2 and references [29,30], and the consistency of the universal set’s potential and input information is maintained. For the above three protocols, 1000 experiments were performed based on different data lengths, and the average value of 10 execution times was randomly taken.
As shown in Figure 3, the computational complexity of reference [29] is slightly lower than that of Algorithm 2. In Dou [30], the proposed protocol is designed based on invoking the MPC protocol that takes the absolute value of the difference between two numbers, which greatly increases the amount of calculation, so its computational complexity is higher than Algorithm 2.
Compared with references [29,30], the protocols have little difference in the number of communication rounds, but only Algorithm 2 proposed in this paper can resist malicious attacks. Although the efficiency of Algorithm 2 is not the highest, its complexity mainly comes from steps such as zero-knowledge proof, and this part of the calculation can be outsourced to improve efficiency.
7. Applications
The applications of Manhattan distance permeate many aspects of real life. Moreover, the research on MPC of Manhattan distance also has important practical application value, such as privacy computation, computer graphics, data mining, and machine learning. The following are some specific application scenarios.
Computing distance is a measurement method. Manhattan distance is often used to measure the length of the path in many scientific studies. For example, in the study of biological cryptography, it is often necessary to judge whether the two biological templates are the same or similar. In data mining and machine learning, we often judge the analogy and similarity of individuals. When consuming products, it will also judge the similarity of consumers. Therefore, the similarity of different individuals can be deduced by calculating the distance value of individual feature vectors, that is, the protocol for MPC of Manhattan distance is the basic module for constructing the secret calculation vector similarity protocol.
The Manhattan distance between two points can better protect personal privacy and solve the constrained optimization problem. As shown in Figure 4, both military sides select military bases in an area, and neither side wants the other party to know where their military bases are located. At the same time, the military exchanges between the two sides are close, and the driving distance between the two military bases should be moderate, that is, the distance should be appropriate. In such an actual scene, the range size of the specified area is equivalent to the given complete set. Both parties just select the appropriate coordinate system in the area, and the location of the military bases of both parties is selected within the range of the complete set. For the suitability of the distance, both parties can jointly calculate the Manhattan distance between two points to make appropriate adjustments.
There are many similar scenarios, and there will be many constrained optimization problems in engineering practice, scientific research, and other fields. Therefore, to better solve the optimization constraint problem, it is particularly important to calculate the Manhattan distance between two points.
3.. Today, with the development of information, information search and matching have practical application value. The location relationship between the security decision vector and the vector interval is the solution to solve the secure searching and matching. The problem of the relationship between the security decision vector and the vector set can also be solved by computing the Manhattan distance securely.
8. Conclusions
Securely computing Manhattan distance is a basic module for designing other MPC geometric protocols, so it has important theoretical significance and application value to study this problem. Given the shortcomings of existing protocols, combining Paillier’s algorithm with additive homomorphism and GM encryption algorithm with Xor homomorphism, this paper takes the lead in designing a protocol with high-security performance under the premise of resisting malicious participant attacks. Algorithm 2 used tools such as the cut-choose method to prevent deception. The real/ideal model paradigm method is used to prove the security of the malicious model protocol. Compared with existing protocols, the experimental simulation shows that only Algorithm 2 can resist malicious participants’ attacks while maintaining high efficiency. The protocol is close to the reality of the existence of malicious participants and has more practical value. The next step is to improve Algorithm 2, using the homogeneous secret sharing to pass the ciphertext, to improve the protocol efficiency.
Conceptualization, X.L. (Xin Liu) and X.L. (Xiaomeng Liu); funding acquisition, X.L. (Xin Liu); investigation, X.L. (Xin Liu); methodology, R.Z.; software, D.L. and G.X.; validation, G.X. and X.C.; writing—original draft, X.L. (Xiaomeng Liu); writing—review and editing, X.L. (Xin Liu), G.X., and X.C. All authors have read and agreed to the published version of the manuscript.
This article does not contain any studies with human participants performed by any of the authors.
Not applicable.
The authors approve that data used to support the finding of this study are included in the article.
In the process of completing the manuscript, I got the help of many people. First of all, I should thank Baoshan Li for giving me many valuable opinions and providing me with the greatest support in thought and action. Second, I thank Yongxing Du for making a lot of amendments and suggestions to the manuscript. Finally, I want to thank my family, classmates, and friends for their support and encouragement.
The authors declare no conflict of interest.
|
|
|
Plaintext |
|
Ciphertext |
|
The public and private keys of Alice’s GM encryption system |
|
The public and private keys of Bob’s GM encryption system |
|
The public key of Alice’s Paillier encryption system |
|
The public key of Bob’s Paillier encryption system |
|
The private key of Alice’s Paillier encryption system |
|
The public key of Bob’s Paillier encryption system |
|
The process of converting encrypted plaintext into ciphertext |
|
The process of decrypting ciphertext into plaintext |
|
Random numbers |
|
Results for a random permutation of the ciphertext |
|
Encrypted calculation with A’s public key |
|
Encrypted calculation with B’s public key |
|
The function calculation results of |
|
The function calculation results of |
|
Function calculation results |
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Protocol’s performance analysis.
Protocol | Fairness | Cryptography Tools | Resist Malicious Attacks |
---|---|---|---|
Fang [ |
unfair | GM | × |
Dou [ |
unfair | Paillier | × |
Liu [ |
unfair | Symmetric cryptography | × |
Algorithm 2 | fair | GM, Paillier | √ |
Efficiency comparison (based on modular multiplication).
Protocol | Computational Complexity | Rounds of Communication | Resist Malicious Attacks |
---|---|---|---|
Fang [ |
|
2 | No |
Dou [ |
|
3 | No |
Liu [ |
|
3 | No |
Algorithm 2 |
|
4 | Yes |
Note: the computational complexity of most MPC protocols is relatively high, due to the use of some cryptographic tools, such as the cut-choose method and zero-knowledge proof. These calculations do not reveal private data and can therefore be outsourced to improve the efficiency of the protocol.
References
1. Ishai, Y.; Rijmen, V. Advances in cryptology-eurocrypt 2019. Proceedings of the 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques; Darmstadt, Germany, 19–23 May 2019; Springer: Berlin/Heidelberg, Germany, 2019; pp. 94-97.
2. Wang, Z.; Pang, X.; Chen, Y. Privacy-preserving crowd-sourced statistical data publishing with an untrusted server. IEEE Trans. Mob. Comput.; 2018; 18, pp. 1356-1367. [DOI: https://dx.doi.org/10.1109/TMC.2018.2861765]
3. Zhou, J.; Feng, Y.; Wang, Z.; Guo, D. Using secure multi-party computation to protect privacy on a permissioned blockchain. Sensors; 2021; 21, 1540. [DOI: https://dx.doi.org/10.3390/s21041540] [PubMed: https://www.ncbi.nlm.nih.gov/pubmed/33672175]
4. Wu, D.; Si, S.; Wu, S. Dynamic trust relationships aware data privacy protection in mobile crowd-sensing. IEEE Internet Things J.; 2017; 5, pp. 2958-2970. [DOI: https://dx.doi.org/10.1109/JIOT.2017.2768073]
5. Fălămaş, D.E.; Marton, K.; Suciu, A. Assessment of Two Privacy Preserving Authentication Methods Using Secure Multiparty Computation Based on Secret Sharing. Symmetry; 2021; 13, 894. [DOI: https://dx.doi.org/10.3390/sym13050894]
6. Yao, A.C. Protocols for secure computations. Proceedings of the 23rd Annual Symposium on Foundation of Computer Science (SFCS 1982); Chicago, IL, USA, 3–5 November 1982.
7. Goldreich, O. Foundations of Cryptography; Basic Applications Cambridge University Press: Cambridge, UK, 2009; Volume 2.
8. Cramer, R.; Damgard, I.B.; Nielsen, J.B. Secure Multiparty Compution; Cambridge University Press: Cambridge, UK, 2015.
9. Hunt, T.; Jia, Z.; Miller, V.; Szekely, A.; Hu, Y. Telekine: Secure computing with cloud {GPUs}. Proceedings of the 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 2020); Santa Clara, CA, USA, 25–27 February 2020.
10. Jiang, J.; Tang, L.; Gu, K.; Jia, W. Secure computing resource allocation framework for open fog computing. Comput. J.; 2020; 63, pp. 567-592. [DOI: https://dx.doi.org/10.1093/comjnl/bxz108]
11. Shen, H.; Liu, Y.; Xia, Z.; Zhang, M. An efficient aggregation scheme resisting on malicious data mining attacks for smart grid. Inf. Sci.; 2020; 526, pp. 289-300. [DOI: https://dx.doi.org/10.1016/j.ins.2020.03.107]
12. Wang, J.; Wu, L.; Zeadally, S.; Khan, M.K.; He, D. Privacy-preserving data aggregation against malicious data mining attack for IoT-enabled smart grid. ACM Trans. Sens. Netw.; 2021; 3, pp. 1-25. [DOI: https://dx.doi.org/10.1145/3440249]
13. Akram, A.; Giannakou, A.; Akella, V.; Lowe, J.; Peisert, S. Performance analysis of scientific computing workloads on general purpose TEEs. Proceedings of the 35th IEEE International Parallel & Distributed Processing Symposium (IPDPS); Portland, OR, USA, 17–21 May 2021.
14. Rao, V.S.; Satyanarayana, N. Experimental analysis and comparative study of secure data outsourcing schemes in cloud. Int. J. Cloud Comput.; 2019; 1, pp. 83-101. [DOI: https://dx.doi.org/10.1504/IJCC.2019.097932]
15. Li, W.; Meng, P.; Hong, Y.; Cui, X. Using deep learning to preserve data confidentiality. Appl Intell; 2020; 50, pp. 341-353. [DOI: https://dx.doi.org/10.1007/s10489-019-01515-3]
16. Zhang, K.X.; Yang, C.; Li, S.D. Privacy preserving string matching. J. Cryptologic Res.; 2022; 9, pp. 619-632. [DOI: https://dx.doi.org/10.13868/j.cnki.jcr.000537]
17. Fakroon, M.; Alshahrani, M.; Gebali, F.; Traore, I. Secure remote anonymous user authentication scheme for smart home environment. IoT; 2020; 9, 100158. [DOI: https://dx.doi.org/10.1016/j.iot.2020.100158]
18. Li, S.D.; Xu, W.T.; Wang, W.L. Secure Maximum (Minimum) Computation in Malicious Model. Chin. J. Comput.; 2021; 44, pp. 2076-2089.
19. Liu, X.; Xu, Y.; Xu, G. Secure Judgment of Point and Line Relationship Against Malicious Adversaries and Its Applications. J. Internet Technol.; 2022; 23, pp. 1019-1027.
20. Liu, X.; Zhang, R.L.; Xu, G. Securely determine the inclusion relation of a point and a convex polygon in malicious model. J. Cryptologic Res.; 2022; 9, pp. 524-534. [DOI: https://dx.doi.org/10.13868/j.cnki.jcr.000531]
21. Resende, A.; Railsback, D.; Dowsley, R. Fast privacy-preserving text classification based on secure multiparty computation. IEEE Trans. Inf. Forensics Secur.; 2022; 17, pp. 428-442. [DOI: https://dx.doi.org/10.1109/TIFS.2022.3144007]
22. Wang, Q.; Guo, Y.; Wang, X.; Ji, T.; Yu, L.; Li, P. AI at the edge: Blockchain-empowered secure multiparty learning with heterogeneous models. IEEE Internet Things J.; 2020; 10, pp. 9600-9610. [DOI: https://dx.doi.org/10.1109/JIOT.2020.2987843]
23. Tran, A.T.; Luong, T.D.; Karnjana, J. An efficient approach for privacy preserving decentralized deep learning models based on secure multi-party computation. Neurocomputing; 2021; 422, pp. 245-262. [DOI: https://dx.doi.org/10.1016/j.neucom.2020.10.014]
24. Shutty, N.; Wootters, M. Low-bandwidth recovery of linear functions of Reed-Solomon-encoded data. arXiv; 2021; [DOI: https://dx.doi.org/10.48550/arXiv.2107.11847] arXiv: 2107.11847
25. Fosli, I.; Ishai, Y.; Kolobov, V.I.; Wootters, M. On the download rate of homomorphic secret sharing. arXiv; 2021; [DOI: https://dx.doi.org/10.48550/arXiv.2111.10126] arXiv: 2111.10126
26. Roy, L.; Singh, J. Large message homomorphic secret sharing from DCR and applications. Proceedings of the 41st Annual International Cryptology Conference (CRYPTO 2021); Virtual Event, 16–20 August 2021; [DOI: https://dx.doi.org/10.1007/978-3-030-84252-9_23]
27. Naor, M.; Pinkas, B. Efficient oblivious transfer protocols. Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms (SODA ’01); Washington, DC, USA, 7–9 January 2001.
28. Lindell, Y.; Pinkas, B. Secure two-party computation via cut-and-choose oblivious transfer. J. Cryptology; 2012; 25, pp. 680-722. [DOI: https://dx.doi.org/10.1007/s00145-011-9107-0]
29. Fang, L.; Li, S.; Dou, J. Secure manhattan distance computation. J. Cryptologic Res.; 2019; 4, pp. 512-525. [DOI: https://dx.doi.org/10.13868/j.cnki.jcr.000319]
30. Dou, J.; Ge, X.; Wang, Y. Secure Manhattan distance computation and its application. J. Comput. Sci.; 2020; 2, pp. 352-365. [DOI: https://dx.doi.org/10.11897/SP.J.1016.2020.00352]
31. Liu, C.; Zhu, L.; He, X.; Chen, J. Enabling privacy-preserving shortest distance queries on encrypted graph data. IEEE Trans. Dependable Secur. Comput.; 2018; 18, pp. 192-204. [DOI: https://dx.doi.org/10.1109/TDSC.2018.2880981]
32. Li, S.D.; Wang, W.; Du, R. Protocol for millionaires’ problem in malicious model. Sci. Sin. Inf.; 2021; 1, pp. 75-88. [DOI: https://dx.doi.org/10.1360/SSI-2019-0226]
33. Paillier, P. Public-key cryptosystems based on composite degree residuosity classes. Proceedings of the international Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT′99); Prague, Czech Republic, 2–6 May 1999.
34. Goldwasser, S.; Micali, S. Probabilistic encryption & how to play mental poker keeping secret all partial information. Proceedings of the fourteenth annual ACM symposium on Theory of computing (STOC’82); San Francisco, CA, USA, 5–7 May 1982; [DOI: https://dx.doi.org/10.1145/800070.802212]
35. Chaum, D.; Pedersen, T.P. Transferred cash grows in size. Proceedings of the workshop on the Theory and Application of Cryptographic Techniques (EUROCRYPT ′92); Balatonfüred, Hungary, 24–28 May 1992.
You have requested "on-the-fly" machine translation of selected content from our databases. This functionality is provided solely for your convenience and is in no way intended to replace human translation. Show full disclaimer
Neither ProQuest nor its licensors make any representations or warranties with respect to the translations. The translations are automatically generated "AS IS" and "AS AVAILABLE" and are not retained in our systems. PROQUEST AND ITS LICENSORS SPECIFICALLY DISCLAIM ANY AND ALL EXPRESS OR IMPLIED WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES FOR AVAILABILITY, ACCURACY, TIMELINESS, COMPLETENESS, NON-INFRINGMENT, MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Your use of the translations is subject to all use restrictions contained in your Electronic Products License Agreement and by using the translation functionality you agree to forgo any and all claims against ProQuest or its licensors for your use of the translation functionality and any output derived there from. Hide full disclaimer
© 2022 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.
Abstract
Manhattan distance is mainly used to calculate the total absolute wheelbase of two points in the standard coordinate system. The secure computation of Manhattan distance is a new geometric problem of secure multi-party computation. At present, the existing research secure computing protocols for Manhattan distance cannot resist the attack of malicious participants. In the real scene, the existence of malicious participants makes it necessary to study a solution that can resist malicious attacks. This paper first analyzes malicious attacks of the semi-honest model protocol of computing Manhattan distance and then designs an advanced protocol under the malicious model by using the Goldwasser–Micali encryption system and Paillier encryption algorithm, and utilizing some cryptographic tools such as the cut-choose method and zero-knowledge proof. Finally, the real/ideal model paradigm method is used to prove the security of the malicious model protocol. Compared with existing protocols, the experimental simulation shows that the proposed protocol can resist malicious participant attacks while maintaining high efficiency. It has practical value.
You have requested "on-the-fly" machine translation of selected content from our databases. This functionality is provided solely for your convenience and is in no way intended to replace human translation. Show full disclaimer
Neither ProQuest nor its licensors make any representations or warranties with respect to the translations. The translations are automatically generated "AS IS" and "AS AVAILABLE" and are not retained in our systems. PROQUEST AND ITS LICENSORS SPECIFICALLY DISCLAIM ANY AND ALL EXPRESS OR IMPLIED WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES FOR AVAILABILITY, ACCURACY, TIMELINESS, COMPLETENESS, NON-INFRINGMENT, MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Your use of the translations is subject to all use restrictions contained in your Electronic Products License Agreement and by using the translation functionality you agree to forgo any and all claims against ProQuest or its licensors for your use of the translation functionality and any output derived there from. Hide full disclaimer
Details

1 Department of Computer Science and Technology, Tianjin Ren’ai College, Tianjin 733299, China; School of Information Engineering, Inner Mongolia University of Science and Technology, Baotou 014010, China
2 School of Information Engineering, Inner Mongolia University of Science and Technology, Baotou 014010, China
3 Department of Computer Science and Technology, Tianjin Ren’ai College, Tianjin 733299, China
4 School of Information Science and Technology, North China University of Technology, Beijing 100144, China; Beijing Key Laboratory of Security and Privacy in Intelligent Transportation, Beijing Jiaotong University, Beijing 100044, China
5 Information Security Center, State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China