GRAPH ENCRYPTION FOR TOP-K NEAREST KEYWORD SEARCH QUERIES ON CLOUD
ABSTRACT
Driven by the growing security demands of data outsourcing applications in sustainable smart cities, encrypting clients’ datahas been widely accepted by academia and industry. Data encryptions should be done at the client side before outsourcing, becauseclouds and edges are not trusted. Therefore, how to properly encrypt data in a way that the encrypted and remotely stored data canstill be queried has become a challenging issue. Though keyword searches over encrypted textual data have been extensively studied,approaches for encrypting graph-structured data with support for answering graph queries are still lacking in the literature. In this paper,we specially investigate graph encryption method for an important graph query type, called top-k Nearest Keyword (kNK) searches. Wedesign several indexes to store necessary information for answering queries and guarantee that private information about the graphsuch as vertex identifiers, keywords and edges are encrypted or excluded. Security and efficiency of our graph encryption scheme aredemonstrated by theoretical proofs and experiments on real-world datasets, respectively.
PROPOSED SYSTEM:
our ContributionsThis paper makes the following contributions:_ To the best of our knowledge, we are the first toinvestigate kNK queries over encrypted graphs. Wedefine a typical graph encryption scheme supportingkNK queries and offer its security model._ We propose an efficient and secure graph encryptionscheme._ We have implemented the proposed graph encryptionscheme and conducted its performance evaluationsover real-world graphs.
EXISTING SYSTEM:
Querying on encrypted and remotely stored data was firstlyaddress by a series of searchable symmetric encryption(SSE) works, which support keyword searches over textualdocuments. The first practical SSE scheme was proposed bySong et al.. However, they did not offer a soundsecurity model for SSE. Such an issue was addressed byCurtmola et al. They claimed that an SSE schemeshould be secure against adaptive chosen-keyword attacks(CKA). Most subsequent SSE works adopted the CKA securitymodel.Querying on structure data was initiated by Chase andKamara in. They proposed the notion of structured encryptionand extended the CKA security model of SSE intothe CQA (i.e., chosen-query attacks) security model servingfor structured encryption. They also proposed several structuredencryption schemes including a matrix-structureddata encryption scheme answering lookup queries, a labeleddata encryption scheme answering keyword search queries,a graph encryption scheme answering neighbor queries, agraph encryption scheme answering adjacency queries anda graph encryption scheme answering focused subgraphqueries. Designing graph encryption schemes supportinghigher-leveled query types then became a challenging issue.Until recently, Meng, Kamara and Nissim proposeda graph encryption scheme for approximate shortest distancequeries. Though their main indexing methods arefrom classical SSE works, they designed novel and efficientapproaches to overcome the problem of encrypted valuecomputation.
CONCLUSION
In this paper, we present a graph encryption scheme for kNKqueries. The proposed graph encryption scheme only makesuse of lightweight cryptographic primitives such as pseudorandomfunction and symmetric-key encryption, rather thanslow homomorphic encryptions. Therefore, the proposedgraph encryption scheme is friendly to a wide set of graphdatabased cloud computing and edge computing applicationssuch as social networks, e-maps, criminal analyses,etc. Compare to graph anonymization approaches fromdatabase community, our scheme attains higher securitylevel as the graph itself is encrypted and we do not makeany assumptions on the types of attacks.An interesting and challenging future work would beusing the proposed kNK graph encryption scheme as abuilding block to design other graph encryption schemessupporting more complex graph query types such as clusteringsand classifications.
REFERENCES
[1] I. Abraham, D. Delling, A. V. Goldberg, and R. F. Werneck.Hierarchical hub labelings for shortest paths. In Algorithms–ESA,pages 24–35. Springer, 2012.
[2] R. Agarwal, P. Godfrey, and S. Har-Peled. Approximate distancequeries and compact routing in sparse graphs. In IEEE INFOCOM,pages 1754–1762, 2011.
[3] T. Akiba, Y. Iwata, and Y. Yoshida. Fast exact shortest-pathdistance queries on large networks by pruned landmark labeling.In ACM SIGMOD, pages 349–360, 2013.
[4] B. Bahmani and A. Goel. Partitioned multi-indexing: bringingorder to social search. In WWW, pages 399–408, 2012.
[5] J. Blocki, A. Blum, A. Datta, and O. Sheffet. Differentially privatedata analysis of social networks via restricted sensitivity. In ACMITCS, pages 87–96, 2013.
[6] D. Cash, J. Jaeger, S. Jarecki, C. Jutla, H. Krawczyk, M.-C. Rosu,and M. Steiner. Dynamic searchable encryption in very largedatabases: Data structures and implementation. In NDSS, 2014.
[7] D. Cash, S. Jarecki, C. Jutla, H. Krawczyk, M.-C. Ros¸u, andM. Steiner. Highly-scalable searchable symmetric encryption withsupport for boolean queries. In CRYPTO, pages 353–373. Springer,2013.
[8] V. Chang, Y.-H. Kuo, and M. Ramachandran. Cloud computingadoption framework: A security framework for business clouds.Future Generation Computer Systems, 57:24–41, 2016.
[9] M. Chase and S. Kamara. Structured encryption and controlleddisclosure. In ASIACRYPT, pages 577–594. Springer, 2010.
[10] S. Chechik. Approximate distance oracles with constant querytime. In ACM STOC, pages 654–663, 2014.