{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T03:40:07Z","timestamp":1756525207634,"version":"3.44.0"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T00:00:00Z","timestamp":1756512000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T00:00:00Z","timestamp":1756512000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cybersecurity"],"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>The problem of querying shortest distance on a graph has attracted significant research attention due to the widespread applicability of graphs and the ability of graph shortest path queries to address numerous application problems. Given the limited capabilities of clients and the ongoing advancements in cloud computing, people would like to outsource their graph data. Outsourcing data, however, poses the problem of privacy breaches. We should enable clients to encrypt their data before outsource it to cloud servers while retaining the capability of querying the data. The major challenge lies in designing a scheme computing the shortest distance on encrypted graph is how to strike a balance between security, efficiency and accuracy. Moreover, this challenge becomes even more pronounced as the scale of the graph increases. In this article, we propose an efficient scheme called Encrypted Shortest Distance Approximate Query (<jats:italic>ESDAQ<\/jats:italic>). We design a new algorithm<jats:italic> k<\/jats:italic>-level <jats:italic>BFS<\/jats:italic> and make use of cryptographic primitive AES to fulfill the scheme where <jats:italic>k<\/jats:italic> is an optional parameter selected by user. The total time cost can be <jats:italic>O<\/jats:italic>(<jats:italic>N<\/jats:italic>) at best to finish setup and query, which is superior to SOTA solutions of <jats:italic>O<\/jats:italic>(<jats:italic>NlogN<\/jats:italic>). Theoretical security analysis shows that <jats:italic>ESDAQ<\/jats:italic> can reach<jats:italic> CQA2<\/jats:italic>-security . Theoretical analysis on security, performance and accuracy are provided of our proposed scheme. Meanwhile, experiments on 12 representative real-world datasets and comprehensive comparison with top and latest schemes are provided. The experiments results demonstrates that our scheme is highly efficient and can be effectively applied to large-scale graphs which comprising over 3 million nodes and 1 billion edges.<\/jats:p>","DOI":"10.1186\/s42400-025-00368-3","type":"journal-article","created":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T03:03:29Z","timestamp":1756523009000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient shortest distance approximate query on large scale encrypted graph data"],"prefix":"10.1186","volume":"8","author":[{"given":"Xiaotong","family":"Dong","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bo","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaojie","family":"Zhu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yong","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weiping","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,8,30]]},"reference":[{"key":"368_CR1","doi-asserted-by":"crossref","unstructured":"Akiba T, Iwata Y, Yoshida Y (2013) Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In: Proceedings of the ACM SIGMOD international conference on management of data. pp 349\u2013360","DOI":"10.1145\/2463676.2465315"},{"key":"368_CR2","doi-asserted-by":"crossref","unstructured":"Cash D et al. (2014) Dynamic searchable encryption in very large databases: data structures and implementation. In: NDSS","DOI":"10.14722\/ndss.2014.23264"},{"key":"368_CR3","doi-asserted-by":"crossref","unstructured":"Chase M, Kamara S (2010) Structured encryption and controlled disclosure. In: International conference on the theory and application of cryptology and information security, Springer","DOI":"10.1007\/978-3-642-17373-8_33"},{"key":"368_CR4","doi-asserted-by":"crossref","unstructured":"Chase M, Kamara S (2010) Structured encryption and controlled disclosure. In: Proc. ASIACRYPT. pp 577\u2013594","DOI":"10.1007\/978-3-642-17373-8_33"},{"key":"368_CR5","doi-asserted-by":"crossref","unstructured":"Chen C et al. (2018) Distributed collaborative hashing and its applications in ant financial. In: SIGKDD. ACM. pp 100\u2013109","DOI":"10.1145\/3219819.3219844"},{"issue":"5","key":"368_CR6","doi-asserted-by":"publisher","first-page":"895","DOI":"10.3233\/JCS-2011-0426","volume":"19","author":"R Curtmola","year":"2011","unstructured":"Curtmola R et al (2011) Searchable symmetric encryption: improved definitions and efficient constructions. J Comput Secur 19(5):895\u2013934","journal-title":"J Comput Secur"},{"key":"368_CR7","unstructured":"Daneshamooz J, Yu M, Maddury S (2024) Seagull: Privacy preserving network verification system. arXiv:2402.08956 [cs.CR]"},{"key":"368_CR8","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra EW (1959) A note on two problems in connexion with graphs. Numerische Mathematik 1:269\u2013271","journal-title":"Numerische Mathematik"},{"issue":"5","key":"368_CR9","doi-asserted-by":"publisher","first-page":"1338","DOI":"10.1137\/S0097539702403098","volume":"32","author":"Cohen Edith","year":"2003","unstructured":"Edith Cohen et al (2003) Reachability and distance queries via 2-hop labels. SIAM J Comput 32(5):1338\u20131355","journal-title":"SIAM J Comput"},{"key":"368_CR10","doi-asserted-by":"publisher","unstructured":"Elgedawy I, Srivastava B, Mittal S (2009) Exploring queriability of encrypted and compressed XML data. In: 2009 24th international symposium on computer and information sciences. pp 141\u2013146. https:\/\/doi.org\/10.1109\/ISCIS.2009.5291834","DOI":"10.1109\/ISCIS.2009.5291834"},{"key":"368_CR11","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1145\/367766.368166","volume":"5","author":"RW Floyd","year":"1962","unstructured":"Floyd RW (1962) Algorithm 97: shortest path. Commun. ACM 5:344\u2013348","journal-title":"Commun. ACM"},{"key":"368_CR12","doi-asserted-by":"crossref","unstructured":"Gao J et al. (2011) Neighborhood-privacy protected shortest distance computing in cloud. In: Proceedings of the 2011 ACM SIGMOD international conference on management of data. pp 409\u2013420","DOI":"10.1145\/1989323.1989367"},{"issue":"1","key":"368_CR13","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1109\/JAS.2017.7510313","volume":"4","author":"MH Ghahramani","year":"2017","unstructured":"Ghahramani MH, Zhou M, Tony Hon C-K (2017) Toward cloud computing QoS architecture: analysis of cloud systems and cloud services. IEEE\/CAA J Autom Sinica 4(1):6\u201318","journal-title":"IEEE\/CAA J Autom Sinica"},{"key":"368_CR14","doi-asserted-by":"crossref","unstructured":"Gubichev A et al. (2010) Fast and accurate estimation of shortest paths in large graphs. In: Proceedings of the 19th ACM international conference on information and knowledge management. pp 499\u2013508","DOI":"10.1145\/1871437.1871503"},{"key":"368_CR15","doi-asserted-by":"crossref","unstructured":"Jarecki S, et al. (2013) Outsourced symmetric private information retrieval. In: ACM CCS. pp 875\u2013888","DOI":"10.1145\/2508859.2516730"},{"key":"368_CR16","doi-asserted-by":"crossref","unstructured":"Kamara S, Papamanthou C, Roeder T (2012) Dynamic searchable symmetric encryption. In: ACM CCS. pp 965\u2013976","DOI":"10.1145\/2382196.2382298"},{"key":"368_CR17","unstructured":"Kastrenakes J (2021) TikTok is rolling out longer videos to everyone. In: The Verge"},{"issue":"13","key":"368_CR18","doi-asserted-by":"publisher","first-page":"1928","DOI":"10.1016\/j.ins.2005.08.001","volume":"176","author":"JG Lee","year":"2006","unstructured":"Lee JG, Whang KY (2006) Secure query processing against encrypted XML data using query-aware decryption. Inf Sci 176(13):1928\u20131947","journal-title":"Inf Sci"},{"key":"368_CR19","unstructured":"Leskovec J, Krevl A (2014) SNAP datasets: stanford large network dataset collection. http:\/\/snap.stanford.edu\/data"},{"issue":"1","key":"368_CR20","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1109\/TDSC.2018.2880981","volume":"18","author":"C Liu","year":"2018","unstructured":"Liu C et al (2018) Enabling privacy-preserving shortest distance queries on encrypted graph data. IEEE Trans Dependable Secur Comput 18(1):192\u2013204","journal-title":"IEEE Trans Dependable Secur Comput"},{"key":"368_CR21","doi-asserted-by":"publisher","unstructured":"Luo Y et al. (2022) Approximate Shortest Distance Queries with Advanced Graph Analytics over Large-scale Encrypted Graphs. In: 2022 18th international conference on mobility, sensing and networking (MSN). pp 287\u2013294. https:\/\/doi.org\/10.1109\/MSN57253.2022.00056","DOI":"10.1109\/MSN57253.2022.00056"},{"key":"368_CR22","doi-asserted-by":"crossref","unstructured":"Meng X et al. (2015) Grecs: graph encryption for approximate shortest distance queries. In: Proceedings of the 22nd ACM SIGSAC conference on computer and communications security","DOI":"10.1145\/2810103.2813672"},{"key":"368_CR23","unstructured":"Mislove A et al. (2007) Measurement and analysis of online social networks. In: Proceedings of the 5th ACM\/usenix internet measurement conference (IMC\u201907). San Diego, CA"},{"key":"368_CR24","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1142\/S021972001000477X","volume":"2","author":"M Mongiovi","year":"2010","unstructured":"Mongiovi M et al (2010) Sigma: a set-cover-based inexact graph matching algorithm. J. Bioinform Comput Biol 2:199\u2013218","journal-title":"J. Bioinform Comput Biol"},{"key":"368_CR25","doi-asserted-by":"crossref","unstructured":"Naveed M, Prabhakaran M, Gunter CA (2014) Dynamic searchable encryption via blind storage. In: IEEE S &P","DOI":"10.1109\/SP.2014.47"},{"issue":"1","key":"368_CR26","doi-asserted-by":"publisher","first-page":"61","DOI":"10.14778\/2732219.2732225","volume":"7","author":"Z Qi","year":"2013","unstructured":"Qi Z et al (2013) Toward a distance oracle for billion-node graphs. Proc VLDB Endow 7(1):61\u201372","journal-title":"Proc VLDB Endow"},{"key":"368_CR27","doi-asserted-by":"crossref","unstructured":"Shang H et al. (2010) Connected substructure similarity search. In: SIGMOD. pp 903\u2013914","DOI":"10.1145\/1807167.1807264"},{"issue":"4","key":"368_CR28","doi-asserted-by":"publisher","first-page":"940","DOI":"10.1109\/TIFS.2017.2774451","volume":"13","author":"M Shen","year":"2017","unstructured":"Shen M et al (2017) Cloud-based approximate constrained shortest distance queries over encrypted graphs with privacy protection. IEEE Trans Inf Forensics Secur 13(4):940\u2013953","journal-title":"IEEE Trans Inf Forensics Secur"},{"key":"368_CR29","doi-asserted-by":"crossref","unstructured":"Song DX, Wagner D, Perrig A (2000) Practical techniques for searches on encrypted data. In: Proceeding 2000 IEEE symposium on security and privacy. S &P 2000. IEEE. pp 44\u201355","DOI":"10.1109\/SECPRI.2000.848445"},{"key":"368_CR30","doi-asserted-by":"crossref","unstructured":"Stefanov E, Papamanthou C, Shi E (2014) Practical dynamic searchable encryption with small leakage. In: NDSS","DOI":"10.14722\/ndss.2014.23298"},{"key":"368_CR31","doi-asserted-by":"publisher","first-page":"102456","DOI":"10.1016\/j.cose.2021.102456","volume":"111","author":"F Sun","year":"2021","unstructured":"Sun F et al (2021) Constrained top-k nearest fuzzy keyword queries on encrypted graph in road network. Comput Secur 111:102456","journal-title":"Comput Secur"},{"issue":"2","key":"368_CR32","doi-asserted-by":"publisher","first-page":"1729","DOI":"10.1109\/JSYST.2023.3238809","volume":"17","author":"F Sun","year":"2023","unstructured":"Sun F et al (2023) Privacy-preserving shortest distance query for dynamic large-scale road network. IEEE Syst J 17(2):1729\u20131740. https:\/\/doi.org\/10.1109\/JSYST.2023.3238809","journal-title":"IEEE Syst J"},{"key":"368_CR33","doi-asserted-by":"crossref","unstructured":"Tong H et al. (2007) Fast best-effort pattern matching in large attributed graphs. In: SIGKDD","DOI":"10.1145\/1281192.1281271"},{"key":"368_CR34","doi-asserted-by":"crossref","unstructured":"Wang H et al. (2020) Variable-length indistinguishable binary tree for keyword searching over encrypted data. In: Web Information Systems and Applications. Springer, p 12432","DOI":"10.1007\/978-3-030-60029-7_51"},{"issue":"2","key":"368_CR35","doi-asserted-by":"publisher","first-page":"61","DOI":"10.14778\/3015274.3015277","volume":"10","author":"S Wang","year":"2016","unstructured":"Wang S et al (2016) Effective indexing for approximate constrained shortest path queries on large road networks. Proc VLDB Endow 10(2):61\u201372","journal-title":"Proc VLDB Endow"},{"issue":"22","key":"368_CR36","doi-asserted-by":"publisher","first-page":"22516","DOI":"10.1109\/JIOT.2022.3184045","volume":"9","author":"W Wang","year":"2022","unstructured":"Wang W et al (2022) SPCS: strong privacy-preserving-constrained shortest distance queries on encrypted graphs. IEEE Internet Things J 9(22):22516\u201322528. https:\/\/doi.org\/10.1109\/JIOT.2022.3184045","journal-title":"IEEE Internet Things J"},{"key":"368_CR37","unstructured":"Wang H, Lakshmanan LVS (2006) Efficient secure query evaluation over encrypted XML databases. In: Proceedings of the 32nd international conference on very large data bases"},{"key":"368_CR38","doi-asserted-by":"crossref","unstructured":"Wang Q, Ren K, Du M (2017) SecGDB: graph encryption for exact shortest distance queries with efficient updates[C]. In: International conference on financial cryptography and data security Springer, Cham, pp 79\u201397","DOI":"10.1007\/978-3-319-70972-7_5"},{"key":"368_CR39","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/s00778-018-0517-6","volume":"28","author":"Z Wu","year":"2019","unstructured":"Wu Z, Li K (2019) VBTree: forward secure conjunctive queries over encrypted data for cloud computing. VLDB J 28:25\u201346","journal-title":"VLDB J"},{"issue":"1","key":"368_CR40","first-page":"136","volume":"52","author":"G Xinrui","year":"2021","unstructured":"Xinrui G et al (2021) SPPS: a search pattern privacy system for approximate shortest distance query of encrypted graphs in IIoT. IEEE Trans Syst Man Cybern Syst 52(1):136\u2013150","journal-title":"IEEE Trans Syst Man Cybern Syst"},{"key":"368_CR41","doi-asserted-by":"publisher","unstructured":"Xu L et al. (2021) Privacy preserving strong simulation queries on large graphs. In: 2021 IEEE 37th international conference on data engineering (ICDE). pp 1500\u20131511. https:\/\/doi.org\/10.1109\/ICDE51399.2021.00133","DOI":"10.1109\/ICDE51399.2021.00133"},{"issue":"1","key":"368_CR42","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1109\/TPDS.2015.2392760","volume":"27","author":"K Xu","year":"2016","unstructured":"Xu K et al (2016) Achieving optimal traffic engineering using a generalized routing ramework. IEEE Trans Parallel Distrib Syst 27(1):51\u201365","journal-title":"IEEE Trans Parallel Distrib Syst"},{"key":"368_CR43","unstructured":"Yabo0815 (2023) Source code of ESDAQ. https:\/\/github.com\/Yabo0815\/Efficient-Shortest-Distance-Approximate-Query-on-Large-Scale-Encrypted-Graph-Data.git"},{"key":"368_CR44","unstructured":"Yang J, Leskovec J (2012) Defining and evaluating network communities based on ground-truth. In: CoRR abs\/1205.6233. arXiv:1205.6233. http:\/\/arxiv.org\/abs\/1205.6233"},{"key":"368_CR45","doi-asserted-by":"crossref","unstructured":"Yan X, Yu PS, Han J (2005) Substructure similarity search in graph databases. In: SIGMOD. pp 766\u2013777","DOI":"10.1145\/1066157.1066244"},{"issue":"9","key":"368_CR46","doi-asserted-by":"publisher","first-page":"800","DOI":"10.14778\/2311906.2311908","volume":"5","author":"Y Yuan","year":"2012","unstructured":"Yuan Y et al (2012) Efficient subgraph similarity search on large probabilistic graph databases. Proc VLDB Endow 5(9):800\u2013811","journal-title":"Proc VLDB Endow"},{"issue":"2","key":"368_CR47","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1093\/bioinformatics\/btl571","volume":"23","author":"T Yuanyuan","year":"2007","unstructured":"Yuanyuan T et al (2007) Saga: a subgraph matching tool for biological graphs. Bioinformatics 23(2):232\u2013239","journal-title":"Bioinformatics"},{"key":"368_CR48","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/j.ins.2019.07.082","volume":"506","author":"Can Zhang","year":"2020","unstructured":"Zhang Can et al (2020) PGAS: privacy-preserving graph encryption for accurate constrained shortest distance queries. Inf Sci 506:325\u2013345","journal-title":"Inf Sci"},{"key":"368_CR49","doi-asserted-by":"crossref","unstructured":"Zhao X et al. (2024) Privacy-preserving any-hop cover shortest distance queries on encrypted graphs. In: IEEE Internet Things J","DOI":"10.1109\/JIOT.2024.3352904"}],"container-title":["Cybersecurity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s42400-025-00368-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s42400-025-00368-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s42400-025-00368-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T03:03:37Z","timestamp":1756523017000},"score":1,"resource":{"primary":{"URL":"https:\/\/cybersecurity.springeropen.com\/articles\/10.1186\/s42400-025-00368-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,30]]},"references-count":49,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,12]]}},"alternative-id":["368"],"URL":"https:\/\/doi.org\/10.1186\/s42400-025-00368-3","relation":{},"ISSN":["2523-3246"],"issn-type":[{"value":"2523-3246","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,30]]},"assertion":[{"value":"15 December 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 January 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 August 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"We declare that we have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"102"}}