Research On Graph Structure Encryption Supporting Exact Shortest Distance Search

The amount of data generated based on network services worldwide has reached the scale of zettabytes due to the rapid growth of data in various fields such as finance,retail,and public services in recent years,driven by the popularization of network communication technology and industrial development.Cloud computing has become an important tool for large-scale data storage and processing.However,cloud servers are not always trustworthy,and outsourced storage data and computing tasks face the risk of privacy leaks.Recently,privacy leak incidents have emerged one after another,causing severe impacts on individuals’ privacy and lives,damaging corporate images and economic benefits,and even endangering national security and interests.To prevent privacy leaks,encryption technology can be used to protect data security.However,traditional encryption technology transforms original data into ciphertext data,causing the data to lose its original semantic features and making it difficult to apply plaintext data retrieval methods to ciphertext data directly.In order to tackle the problem,researchers have suggested using searchable encryption techniques that allow users to search for specific keywords in encrypted text data without compromising the privacy of sensitive information.Currently,research on searchable encryption technology for shortest distance searches has achieved some results,but there are still shortcomings in the accuracy of search results.To solve the problem of accurate shortest distance search in encrypted graph structures,this paper conducts research on key technologies for searchable encryption of graph structures that support accurate shortest distance search.The main contributions are as follows:(1)Addressing the problem that previous graph structure encryption schemes cannot achieve accurate shortest distance search,this paper proposes a secure distance comparison protocol and a secure shortest distance protocol based on secure multiparty computation.Through these two protocols,comparison operations on encrypted distance values can be executed to obtain accurate shortest distance values.The protocols directly calculate ciphertext without leaking any information about plaintext and send the private key to both the cloud service platform and the computing server for joint calculation using partial private keys to minimize the chances of private key leakage,providing better security.In addition,these protocols can be used not only for the proposed scheme in this paper,but also for other integer operation application scenarios that require privacy protection.(2)To address the shortest distance search problem in encrypted graph structures,this paper proposes a graph structure encryption scheme that supports accurate shortest distance search based on the secure distance comparison protocol and secure shortest distance protocol.The formal definition of the scheme is given,and the construction process of the scheme is described in detail.By defining threat models and leakage functions,the paper rigorously proves that the scheme satisfies chosen query attack security.The proposed solution was also subjected to a cost analysis,which included evaluating its computational,communication,and storage costs.(3)Based on the above research,a prototype system for the proposed scheme is developed.The prototype system implements functions such as uploading graph structure data,constructing secure indexes,and performing shortest distance searches.Our proposed solution has been tested on real-world datasets through simulated experiments,and the results demonstrate its ability to perform accurate shortest distance searches.