Research On The Key Technologies Of Searchable Encryption And Privacy-preserving Protocol Based On Graph Structure

Under the big data environment,cloud storage and cloud computing have become an important part of our daily life,since they are low-cost,efficient and highly scalable.More and more corporations,governments and individuals outsource their data to cloud servers,in order to reduce the requirements of local hardware and reduce the pressure of data maintenance and management.Furthermore,cloud computing provides pay-per-use computing services to users,which can greatly reduce the local computation costs.Moreover,along with the fast development of information industry,the type of data is becoming more and more rich in variety,and the structure of data is becoming more and more complex.In order to achieve flexible usage of complex data,the data can be represented and stored using graph structures,and many graph algorithms can be used to achieve different types of search and computation.However,although cloud storage and cloud computing provide high-quality services,it brings security problems as well.In terms of data security,cloud services make the users to loss their physical control of data.The outsourced data and the corresponding computation tasks are facing serious risks of privacy disclosure.As a result,the privacy protecting technologies have become a hot research topic in both academia and industry in recent years,and they receive more and more attentions from scholars.In order to achieve the requirements of performing allpath searches,adjacency queries,intersection/union computation and subgraph matching computation,this dissertation studies the key technologies of graph-based searchable encryption and privacy-preserving protocol.The main contributions are summarized as below:(1)For the problem of performing all-path searches in encrypted graph structures,this dissertation proposed a graph-based searchable encryption for all-path searches(GSE-APS).The scheme allows a user to perform all-path searches over an encrypted graph structure.By using a start vertex and a destination vertex,the user can obtain all the paths between them in the encrypted graph structure.This dissertation proposed the model and definitions of the scheme,and designed an encrypted index based on linked structure.Meanwhile,this dissertation described the detailed construction of the scheme,and proved the security under the semihonest adversary mode.The efficiency of the scheme is analyzed in terms of storage,computation and communication costs.By using real graph structure datasets,the simulation of the scheme is performed.The simulation results show that the search time is irrelevant to the size of the graph structure,and the scheme achieves efficient all-path search process.(2)For the problem of performing adjacency queries in encrypted graph structures,this dissertation proposed a graph-based searchable encryption for adjacency queries(GSE-AQ).It allows a user to query the adjacency relation between two vertices over an encrypted graph structure.This dissertation proposed the model and definitions of the scheme,and designed an encrypted index based on dictionary and matrix data structures.Moreover,this dissertation described the detailed construction of the scheme,and proved the scheme is IND-CKA2 secure under the semi-honest adversary model.The efficiency analysis and simulation results show that the computation cost of the scheme is constant,which satisfied the efficiency requirements of real-world applications.(3)For the problem of computing intersection/union between two encrypted graph structures,this dissertation proposed a graph-based privacy-preserving intersection/union protocol(GPI/U).The protocol allows two users to compute the intersection/union of their graph structures,and protects the privacies of the inputs.This dissertation provides the model and definitions of the protocol,as well as the detailed computation and communication process.The computation costs and communication costs of the protocol are analyzed.The security proofs and simulation results show that the protocol achieves the privacy-preserving property.Neither of the parties can learn any information about the graph structure of the other party.(4)For the problem of computing subgraph matching between two encrypted graph structures,this dissertation proposed a graph-based privacy-preserving subgraph matching protocol(GPSM).The protocol allows two parties to jointly testing the subgraph relationship between their graph structures.Meanwhile,neither of the parties needs to transfer any plaintext information about the graph structure to the other party,and therefore the privacies of the graph structures are preserved.This dissertation provides the model and definitions of the protocol,as well as the detailed construction.The security of the protocol is proved under the semi-honest adversary model.At last,the correctness and efficiencies of the protocol is tested through simulations.