{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,3]],"date-time":"2026-05-03T11:04:47Z","timestamp":1777806287244,"version":"3.51.4"},"reference-count":45,"publisher":"SAGE Publications","issue":"6","license":[{"start":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T00:00:00Z","timestamp":1753833600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T00:00:00Z","timestamp":1753833600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Journal of Computer Security"],"published-print":{"date-parts":[[2025,11]]},"abstract":"<jats:p>\n                    Ghosh, Kamara, and Tamassia (GKT) (ASIA CCS 2021) proposed a graph encryption scheme supporting shortest path queries. This work presents a query recovery attack against the scheme when the adversary is given the original graph and the leakage of certain subsets of queries. The attack falls within the security model used by GKT, and is the first targeting schemes\u00a0supporting shortest path queries. The attack uses classical graph algorithms to compute the canonical names of the single-destination shortest path spanning trees of the underlying graph and uses these canonical names to precompute the set of candidate queries that match each response. When all shortest path queries to a single node have been observed, the canonical names for the corresponding query tree are computed, and the responses are matched to the candidate queries from the offline phase. The output is guaranteed to contain the correct query. For a graph on\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\">\n                        <mml:mi>n<\/mml:mi>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    vertices, the attack runs in time\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\">\n                        <mml:mi>O<\/mml:mi>\n                        <mml:mo stretchy=\"false\">(<\/mml:mo>\n                        <mml:msup>\n                          <mml:mi>n<\/mml:mi>\n                          <mml:mn>3<\/mml:mn>\n                        <\/mml:msup>\n                        <mml:mo stretchy=\"false\">)<\/mml:mo>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    and matches the time complexity of the GKT scheme\u2019s setup. The attack\u2019s practicality is demonstrated through an implementation and evaluation on the real-world datasets used in the original paper and on random graphs.\n                  <\/jats:p>","DOI":"10.1177\/0926227x251355849","type":"journal-article","created":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T07:24:07Z","timestamp":1753860247000},"page":"402-424","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":0,"title":["An efficient query recovery attack against a graph encryption scheme"],"prefix":"10.1177","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8415-6237","authenticated-orcid":false,"given":"Francesca","family":"Falzon","sequence":"first","affiliation":[{"name":"Department of Computer Science, ETH Z\u00fcrich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5145-4489","authenticated-orcid":false,"given":"Kenneth G.","family":"Paterson","sequence":"additional","affiliation":[{"name":"Department of Computer Science, ETH Z\u00fcrich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2025,7,30]]},"reference":[{"key":"e_1_3_3_2_2","unstructured":"Amazon. Amazon Neptune. https:\/\/aws.amazon.com\/neptune\/ (2021 accessed 27 October 2021)."},{"key":"e_1_3_3_3_2","unstructured":"Bronson N Amsden Z Cabrera G et\u00a0al. TAO: Facebook\u2019s distributed data store for the social graph. In: 2013 USENIX annual technical conference (USENIX ATC 13). San Jose CA: USENIX Association 2013 pp.49\u201360."},{"key":"e_1_3_3_4_2","unstructured":"I. Neo4j. Neo4j. https:\/\/neo4j.com\/ (2021 accessed 27 October 2021)."},{"key":"e_1_3_3_5_2","unstructured":"Ontotext. GraphDB. https:\/\/graphdb.ontotext.com\/ (2021 accessed 27 October 2021)."},{"key":"e_1_3_3_6_2","doi-asserted-by":"crossref","unstructured":"Malewicz G Austern MH Bik AJC et al. Pregel: a system for large-scale graph processing. In: Proceedings of the 2010 ACM SIGMOD international conference on management of data Indianapolis IN USA \u00a02010 pp.135\u2013146. New York NY USA: Association for Computing Machinery.","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_3_3_8_2","doi-asserted-by":"crossref","unstructured":"Shao B Wang H Li Y. Trinity: a distributed graph engine on a memory cloud. In: Proceedings of the 2013 ACM SIGMOD international conference on management of data SIGMOD\u201913 2013 pp.505\u2013516. New York NY USA: Association for Computing Machinery.","DOI":"10.1145\/2463676.2467799"},{"key":"e_1_3_3_9_2","doi-asserted-by":"crossref","unstructured":"Chase M Kamara S. Structured encryption and controlled disclosure. In: Advances in cryptology \u2013 ASIACRYPT 2010 \u2013 16th international conference on the theory and application of cryptology and information security 2010 pp.577\u2013594 Lecture notes in computer science Vol. 6477. Singapore: Springer Cham Switzerland.","DOI":"10.1007\/978-3-642-17373-8_33"},{"key":"e_1_3_3_10_2","doi-asserted-by":"crossref","unstructured":"Meng X Kamara S Nissim K et al. GRECS: graph encryption for approximate shortest distance queries. In: Proceedings of the 22nd ACM SIGSAC conference on computer and communications security Denver Colorado 2015 pp.504\u2013517.\u00a0New York NY USA:\u00a0Association for Computing Machinery.","DOI":"10.1145\/2810103.2813672"},{"key":"e_1_3_3_11_2","doi-asserted-by":"crossref","unstructured":"Ghosh E Kamara S Tamassia R. Efficient graph encryption scheme for shortest path queries. In: Proceedings of the 2021 ACM Asia conference on computer and communications security ASIA CCS\u201921 \u00a0Virtual Hong Kong \u00a02021 \u00a0pp.516\u2013525.\u00a0New York NY USA:\u00a0Association for Computing Machinery.","DOI":"10.1145\/3433210.3453099"},{"key":"e_1_3_3_12_2","doi-asserted-by":"crossref","unstructured":"Wang Q Ren K Du M et al. SecGDB: graph encryption for exact shortest distance queries with efficient updates. In: Financial cryptography and data security \u2013 21st international conference FC 2017 Sliema Malta April 3\u20137 2017 revised selected papers (ed A Kiayias) Lecture notes in computer science Vol. 10322 2017 pp.79\u201397.\u00a0Cham Switzerland:\u00a0Springer.","DOI":"10.1007\/978-3-319-70972-7_5"},{"key":"e_1_3_3_13_2","doi-asserted-by":"crossref","unstructured":"Falzon F Paterson KG. An efficient query recovery attack against a graph encryption scheme. In: Computer security \u2013 ESORICS 2022 \u2013 27th European symposium on research in computer security Copenhagen Denmark September 26\u201330 2022 proceedings part I (eds V Atluri RD Pietro CD Jensen and W Meng) lecture notes in computer science Vol. 13554 2022 pp.325\u2013345. Berlin: Springer.","DOI":"10.1007\/978-3-031-17140-6_16"},{"key":"e_1_3_3_14_2","doi-asserted-by":"crossref","unstructured":"Sealfon A. Shortest paths and distances with differential privacy. In: Proceedings of the 35th ACM SIGMOD\u2013SIGACT\u2013SIGAI symposium on principles of database systems PODS\u201916. New York NY USA: Association for Computing Machinery 2016 pp.29\u201341.","DOI":"10.1145\/2902251.2902291"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212352"},{"key":"e_1_3_3_16_2","volume-title":"Data structures and algorithms","author":"Aho AV","year":"1983","unstructured":"Aho AV, Hopcroft JE, Ullman J. Data structures and algorithms, 1st edn. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1983.","edition":"1"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/367766.368168"},{"key":"e_1_3_3_18_2","doi-asserted-by":"crossref","unstructured":"Poh GS Mohamad MS Z\u2019aba MR. Structured encryption for conceptual graphs. In: Hanaoka G and Yamauchi T (eds) Advances in information and computer security. Berlin: Springer 2012 pp.105\u2013122.","DOI":"10.1007\/978-3-642-34117-5_7"},{"key":"e_1_3_3_19_2","doi-asserted-by":"crossref","unstructured":"Wu DJ Zimmerman J Planul J et\u00a0al. Privacy-preserving shortest path computation. In: 23rd annual network and distributed system security symposium NDSS 2016 San Diego California USA February 21\u201324 2016. San Diego CA USA: The Internet Society 2016. http:\/\/wp.internetsociety.org\/ndss\/wp-content\/uploads\/sites\/25\/2017\/09\/privacy-preserving-shortest-path-computation.pdf.","DOI":"10.14722\/ndss.2016.23052"},{"key":"e_1_3_3_20_2","doi-asserted-by":"crossref","unstructured":"Lai S Yuan X Sun S-F et\u00a0al. GraphSE2: an encrypted graph database for privacy-preserving social search. In: Proceedings of the 2019 ACM Asia conference on computer and communications security Asia CCS\u201919. New York NY USA: Association for Computing Machinery 2019 pp.41\u201354.","DOI":"10.1145\/3321705.3329803"},{"key":"e_1_3_3_21_2","doi-asserted-by":"crossref","unstructured":"Sala A Zhao X Wilson C et\u00a0al. Sharing graphs using differentially private graph models. In: Proceedings of the 2011 ACM SIGCOMM conference on internet measurement conference IMC\u201911. New York NY USA: Association for Computing Machinery 2011 pp.81\u201398.","DOI":"10.1145\/2068816.2068825"},{"key":"e_1_3_3_22_2","doi-asserted-by":"crossref","unstructured":"Blackstone L Kamara S Moataz T. Revisiting leakage abuse attacks. In: 27th annual network and distributed system security symposium NDSS 2020 San Diego California USA February 23\u201326 2020. San Diego CA USA: The Internet Society 2020.","DOI":"10.14722\/ndss.2020.23103"},{"key":"e_1_3_3_23_2","doi-asserted-by":"crossref","unstructured":"Cash D Grubbs P Perry J et al. Leakage-abuse attacks against searchable encryption. In: Proceedings of the 22nd ACM SIGSAC conference on computer and communications security (CCS '15) Denver Colorado \u00a0pp.668\u2013679.\u00a0New York NY USA:\u00a0Association for Computing Machinery.","DOI":"10.1145\/2810103.2813700"},{"key":"e_1_3_3_24_2","unstructured":"Zhang Y Katz J Papamanthou C. All your queries are belong to us: the power of file-injection attacks on searchable encryption. In: 25th USENIX security symposium (USENIX Security 16). Austin TX: USENIX Association 2016 pp.707\u2013720."},{"key":"e_1_3_3_25_2","unstructured":"Islam MS Kuzu M Kantarcioglu M. Access pattern disclosure on searchable encryption: ramification attack and mitigation. In: 19th annual network and distributed system security symposium NDSS 2012. San Diego CA USA: The Internet Society 2012."},{"key":"e_1_3_3_26_2","doi-asserted-by":"crossref","unstructured":"Pouliot D Wright CV. The shadow nemesis: inference attacks on efficiently deployable efficiently searchable encryption. In: Proceedings of the 2016 ACM SIGSAC conference on computer and communications security (CCS '16) Vienna Austria 2016 pp.1341\u20131352.\u00a0New York NY USA:\u00a0Association for Computing Machinery.","DOI":"10.1145\/2976749.2978401"},{"key":"e_1_3_3_27_2","doi-asserted-by":"crossref","unstructured":"Gui Z Paterson KG Patranabis S. Rethinking searchable symmetric encryption. In: 44th IEEE symposium on security and privacy SP 2023 San Francisco CA USA May 21\u201325 2023 pp.1401\u20131418.\u00a0NY USA:\u00a0The Institute of Electrical and Electronics Engineers (IEEE).","DOI":"10.1109\/SP46215.2023.10179460"},{"key":"e_1_3_3_28_2","doi-asserted-by":"crossref","unstructured":"Kellaris G Kollios G Nissim K et al. Generic attacks on secure outsourced databases. In: Proceedings of the 2016 ACM SIGSAC conference on computer and communications security (CCS '16) Vienna Austria 2016 pp.1329\u20131340. New York NY USA: Association for Computing Machinery.","DOI":"10.1145\/2976749.2978386"},{"key":"e_1_3_3_29_2","doi-asserted-by":"crossref","unstructured":"Lacharit\u00e9 M-S Minaud B Paterson KG. Improved reconstruction attacks on encrypted data using range query leakage. In: IEEE symposium on security and privacy (SP) San Francisco CA USA 2018 pp.297\u2013314.\u00a0NY USA:\u00a0The Institute of Electrical and Electronics Engineers (IEEE).","DOI":"10.1109\/SP.2018.00002"},{"key":"e_1_3_3_30_2","doi-asserted-by":"crossref","unstructured":"Grubbs P Lacharit\u00e9 M Minaud B et al. Pump up the volume: practical database reconstruction from volume leakage on range queries. In: Proceedings of the 2018 ACM SIGSAC conference on computer and communications security CCS 2018 Toronto ON Canada October 15\u201319 2018 (eds D Lie M Mannan M Backes and X Wang) 2018 pp.315\u2013331. New York NY USA:\u00a0Association for Computing Machinery.","DOI":"10.1145\/3243734.3243864"},{"key":"e_1_3_3_31_2","doi-asserted-by":"crossref","unstructured":"Grubbs P Lacharit\u00e9 M-S Minaud B et al. Learning to reconstruct: statistical learning theory and encrypted database attacks. In: Proceedings of IEEE symposium on security and privacy (SP) San Francisco CA USA \u00a02019 \u00a0pp.1067\u20131083.\u00a0NY USA:\u00a0Institute of Electrical and Electronics Engineers.","DOI":"10.1109\/SP.2019.00030"},{"key":"e_1_3_3_32_2","doi-asserted-by":"crossref","unstructured":"Gui Z Johnson O Warinschi B. Encrypted databases: new volume attacks against range queries. In: Proceedings of the 2019 ACM SIGSAC conference on computer and communications security CCS 2019 London UK November 11\u201315 2019 (eds L Cavallaro J Kinder X Wang and J Katz) 2019 pp.361\u2013378. New York NY USA: Association for Computing Machinery.","DOI":"10.1145\/3319535.3363210"},{"key":"e_1_3_3_33_2","doi-asserted-by":"crossref","unstructured":"Kornaropoulos EM Papamanthou C Tamassia R. The state of the uniform: attacks on encrypted databases beyond the uniform query distribution. In: Proceedings of IEEE symposium on security and privacy (SP) San Francisco CA USA 2018 pp.297\u2013314. NY USA:\u00a0Institute of Electrical and Electronics Engineers 2020.","DOI":"10.1109\/SP40000.2020.00029"},{"key":"e_1_3_3_34_2","doi-asserted-by":"crossref","unstructured":"Kornaropoulos EM Papamanthou C Tamassia R. Response-hiding encrypted ranges: revisiting security via parametrized leakage-abuse attacks. In: Proceedings of IEEE symposium on security and privacy San Francisco CA USA 2021 pp.1502\u20131519. NY USA:\u00a0Institute of Electrical and Electronics Engineers.","DOI":"10.1109\/SP40001.2021.00044"},{"key":"e_1_3_3_35_2","doi-asserted-by":"crossref","unstructured":"Markatou EA Tamassia R. Full database reconstruction with access and search pattern leakage. In: Information security \u2013 22nd international conference ISC 2019 New York City NY USA September 16\u201318 2019 proceedings lecture notes in computer science Vol. 11723 2019 pp.25\u201343.\u00a0Cham Switzerland:\u00a0Springer.","DOI":"10.1007\/978-3-030-30215-3_2"},{"key":"e_1_3_3_36_2","doi-asserted-by":"crossref","unstructured":"Falzon F Markatou EA Cash D et al. Full database reconstruction in two dimensions. In: Proceedings of the 2020 ACM SIGSAC conference on computer and communications security (CCS '20) Virtual 2020 pp.443\u2013460. New York NY USA:\u00a0Association for Computing Machinery.","DOI":"10.1145\/3372297.3417275"},{"key":"e_1_3_3_37_2","doi-asserted-by":"crossref","unstructured":"Markatou EA Falzon F Tamassia R et al.\u00a0Reconstructing with less: leakage abuse attacks in two dimensions. In: Proceedings of the 2021 ACM SIGSAC conference on computer and communications security (CCS '21) Virtual 2021 pp.2243\u20132261. New York NY USA:\u00a0Association for Computing Machinery.","DOI":"10.1145\/3460120.3484552"},{"key":"e_1_3_3_38_2","doi-asserted-by":"crossref","unstructured":"Kornaropoulos EM Papamanthou C Tamassia R. Data recovery on encrypted databases with k-nearest neighbor query leakage. In: Proceedings of IEEE symposium on security and privacy 2019 (S&P 2019) San Francisco CA USA 2019 pp.1033\u20131050. NY USA:\u00a0Institute of Electrical and Electronics Engineers (IEEE).","DOI":"10.1109\/SP.2019.00015"},{"key":"e_1_3_3_39_2","unstructured":"Goetschmann A. Design and analysis of graph encryption schemes. Master\u2019s Thesis ETH Z\u00fcrich 2020."},{"key":"e_1_3_3_40_2","volume-title":"Introduction to algorithms","author":"Cormen TH","year":"2009","unstructured":"Cormen TH, Leiserson CE, Rivest RL, et\u00a0al. Introduction to algorithms, 3rd edn. The MIT Press, 2009.","edition":"3"},{"key":"e_1_3_3_41_2","doi-asserted-by":"crossref","unstructured":"Cash D Jaeger J Jarecki S et\u00a0al. Dynamic searchable encryption in very-large databases: data structures and implementation. In: 21st annual network and distributed system security symposium 2014 NDSS 2014. San Diego CA USA: The Internet Society 2014.","DOI":"10.14722\/ndss.2014.23264"},{"key":"e_1_3_3_42_2","unstructured":"Developers P. PyCryptodome 2021 version 3.10.1. https:\/\/www.pycryptodome.org\/."},{"key":"e_1_3_3_43_2","unstructured":"Developers N. NetworkX 2021 version 2.6.2. https:\/\/networkx.org\/."},{"key":"e_1_3_3_44_2","unstructured":"Leskovec J Krevl A. SNAP datasets: Stanford large network dataset collection 2014."},{"key":"e_1_3_3_45_2","doi-asserted-by":"crossref","unstructured":"Charikar M. Greedy approximation algorithms for finding dense components in a graph. In: Jansen K and S Khuller S (eds) Approximation algorithms for combinatorial optimization. Berlin: Springer 2000 pp.84\u201395.","DOI":"10.1007\/3-540-44436-X_10"},{"key":"e_1_3_3_46_2","volume-title":"Densest-subgraph-discovery","author":"Ambavi H","year":"2020","unstructured":"Ambavi H, Sharma M, Gohil V. Densest-subgraph-discovery. GitHub, 2020."}],"container-title":["Journal of Computer Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0926227X251355849","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/0926227X251355849","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0926227X251355849","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T20:45:55Z","timestamp":1777495555000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0926227X251355849"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,30]]},"references-count":45,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,11]]}},"alternative-id":["10.1177\/0926227X251355849"],"URL":"https:\/\/doi.org\/10.1177\/0926227x251355849","relation":{},"ISSN":["0926-227X","1875-8924"],"issn-type":[{"value":"0926-227X","type":"print"},{"value":"1875-8924","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,30]]}}}