DataVXApplied SciencesPaper
journal article·2022-11-17Open access

Securely Computing the Manhattan Distance under the Malicious Model and Its Applications

Xin Liu, Xiaomeng Liu, Ruiling Zhang, Dan Luo, Gang Xu, Xiubo Chen

Applied Sciences· Volume 12· Issue 22
Publisher pageOpen full text
Source abstract

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.
Source: crossref · Quality: baseline

Research context

OpenAlex topics: Cryptography and Data Security · Cryptographic Implementations and Security · Complexity and Algorithms in Graphs

SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.

Affiliations

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

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

Information Security Center, State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China

Funding

NSFC · Inner Mongolia Natural Science Foundation · 2022 Basic Scientific Research Project of Direct Universities of Inner Mongolia · 2022 Fund Project of Central Government Guiding Local Science and Technology Development · 2022 “Western Light” Talent Training Program “Western Young Scholars” Project · Inner Mongolia Discipline Inspection and Supervision Big Data Laboratory Open Project Fund · Baotou Kundulun District Science and Technology Plan Project · 14th Five Year Plan of Education and Science of Inner Mongolia · Inner Mongolia Science and Technology Major Project · 2022 Inner Mongolia Postgraduate Education and Teaching Reform Project · 2022 Ministry of Education Central and Western China Young Backbone Teachers and Domestic Visiting Scholars Program · Basic Scientific Research Business Fee Project of Beijing Municipal Commission of Education · Research Startup Fund Project of North China University of Technology

References (35)

Show source-provided references
1. Ishai, Y., and Rijmen, V. (2019, January 19–23). Advances in cryptology-eurocrypt 2019. Proceedings of the 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany.10.1007/978-3-030-17659-4 ↗
2. Privacy-preserving crowd-sourced statistical data publishing with an untrusted server10.1109/TMC.2018.2861765 ↗
3. Zhou, J., Feng, Y., Wang, Z., and Guo, D. (2021). Using secure multi-party computation to protect privacy on a permissioned blockchain. Sensors, 21.10.3390/s21041540 ↗
4. Dynamic trust relationships aware data privacy protection in mobile crowd-sensing10.1109/JIOT.2017.2768073 ↗
5. Fălămaş, D.E., Marton, K., and Suciu, A. (2021). Assessment of Two Privacy Preserving Authentication Methods Using Secure Multiparty Computation Based on Secret Sharing. Symmetry, 13.10.3390/sym13050894 ↗
6. Yao, A.C. (1982, January 3–5). Protocols for secure computations. Proceedings of the 23rd Annual Symposium on Foundation of Computer Science (SFCS 1982), Chicago, IL, USA.10.1109/SFCS.1982.38 ↗
7. Goldreich, O. (2009). Foundations of Cryptography, Cambridge University Press. Basic Applications.
8. Cramer, R., Damgard, I.B., and Nielsen, J.B. (2015). Secure Multiparty Compution, Cambridge University Press.10.1017/CBO9781107337756 ↗
9. Hunt, T., Jia, Z., Miller, V., Szekely, A., and Hu, Y. (2020, January 25–27). Telekine: Secure computing with cloud {GPUs}. Proceedings of the 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 2020), Santa Clara, CA, USA.
10. Secure computing resource allocation framework for open fog computing10.1093/comjnl/bxz108 ↗
11. An efficient aggregation scheme resisting on malicious data mining attacks for smart grid10.1016/j.ins.2020.03.107 ↗
12. Privacy-preserving data aggregation against malicious data mining attack for IoT-enabled smart grid
13. Akram, A., Giannakou, A., Akella, V., Lowe, J., and Peisert, S. (2021, January 17–21). Performance analysis of scientific computing workloads on general purpose TEEs. Proceedings of the 35th IEEE International Parallel & Distributed Processing Symposium (IPDPS), Portland, OR, USA.10.1109/IPDPS49936.2021.00115 ↗
14. Experimental analysis and comparative study of secure data outsourcing schemes in cloud10.1504/IJCC.2019.097932 ↗
15. Using deep learning to preserve data confidentiality10.1007/s10489-019-01515-3 ↗
16. Privacy preserving string matching
17. Secure remote anonymous user authentication scheme for smart home environment
18. Secure Maximum (Minimum) Computation in Malicious Model
19. Secure Judgment of Point and Line Relationship Against Malicious Adversaries and Its Applications10.53106/160792642022092305010 ↗
20. Securely determine the inclusion relation of a point and a convex polygon in malicious model
21. Fast privacy-preserving text classification based on secure multiparty computation10.1109/TIFS.2022.3144007 ↗
22. AI at the edge: Blockchain-empowered secure multiparty learning with heterogeneous models10.1109/JIOT.2020.2987843 ↗
23. An efficient approach for privacy preserving decentralized deep learning models based on secure multi-party computation10.1016/j.neucom.2020.10.014 ↗
24. Shutty, N., and Wootters, M. (2021). Low-bandwidth recovery of linear functions of Reed-Solomon-encoded data. arXiv.
25. Fosli, I., Ishai, Y., Kolobov, V.I., and Wootters, M. (2021). On the download rate of homomorphic secret sharing. arXiv.
26. Roy, L., and Singh, J. (2021, January 16–20). Large message homomorphic secret sharing from DCR and applications. Proceedings of the 41st Annual International Cryptology Conference (CRYPTO 2021), Virtual Event.10.1007/978-3-030-84252-9_23 ↗
27. Naor, M., and Pinkas, B. (2001, January 7–9). Efficient oblivious transfer protocols. Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms (SODA ’01), Washington, DC, USA.
28. Secure two-party computation via cut-and-choose oblivious transfer10.1007/s00145-011-9107-0 ↗
29. Secure manhattan distance computation
30. Secure Manhattan distance computation and its application
31. Enabling privacy-preserving shortest distance queries on encrypted graph data10.1109/TDSC.2018.2880981 ↗
32. Protocol for millionaires’ problem in malicious model10.1360/SSI-2019-0226 ↗
33. Paillier, P. (1999, January 2–6). 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.
34. Goldwasser, S., and Micali, S. (1982, January 5–7). 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.10.1145/800070.802212 ↗
35. Chaum, D., and Pedersen, T.P. (1992, January 24–28). Transferred cash grows in size. Proceedings of the workshop on the Theory and Application of Cryptographic Techniques (EUROCRYPT ′92), Balatonfüred, Hungary.