A Secure Multi-Party Computation Protocol for Graph Editing Distance against Malicious Attacks

Xin Liu, Jianwei Kong, Lu Peng, Dan Luo (), Gang Xu, Xiubo Chen and Xiaomeng Liu
Additional contact information
Xin Liu: School of Information Engineering, Inner Mongolia University of Science and Technology, Baotou 014010, China
Jianwei Kong: School of Information Engineering, Inner Mongolia University of Science and Technology, Baotou 014010, China
Lu Peng: Beijing Institute of Computer Technology and Applications, Beijing 100039, China
Dan Luo: Department of Computer Science, Tianjin Renai University, Tianjin 301636, China
Gang Xu: School of Information Science and Technology, North China University of Technology, Beijing 100144, China
Xiubo Chen: State Key Laboratory of Network and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China
Xiaomeng Liu: School of Information Engineering, Inner Mongolia University of Science and Technology, Baotou 014010, China

Mathematics, 2023, vol. 11, issue 23, 1-17

Abstract: The secure computation of the graph structure is an important element in the field of secure calculation of graphs, which is important in querying data in graphs, since there are no algorithms for the graph edit distance problem that can resist attacks by malicious adversaries. In this paper, for the problem of secure computation of similarity edit distance of graphs, firstly, the encoding method applicable to the Paillier encryption algorithm is proposed, and the XOR operation scheme is proposed according to the Paillier homomorphic encryption algorithm. Then, the security algorithm under the semi-honest model is designed, which adopts the new encoding method and the XOR operation scheme. Finally, for the malicious behaviors that may be implemented by malicious participants in the semi-honest algorithm, using the hash function, a algorithm for secure computation of graph editing distance under the malicious model is designed, and the security of the algorithm is proved, and the computational complexity and the communication complexity of the algorithm are analyzed, which is more efficient compared with the existing schemes, and has practical value. The algorithm designed in this paper fills the research gap in the existing literature on the problem of graph edit distance and contributes to solving the problem.

Keywords: secure multi-party computation; graph editing distance; XOR; hash function; malicious model (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/23/4847/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/23/4847/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:23:p:4847-:d:1292666

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().