{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,30]],"date-time":"2026-07-30T14:03:08Z","timestamp":1785420188801,"version":"3.56.0"},"publisher-location":"New York, NY, USA","reference-count":68,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,12,2]],"date-time":"2024-12-02T00:00:00Z","timestamp":1733097600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Armasuisse Science and Technology"},{"DOI":"10.13039\/501100006374","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-2154490"],"award-info":[{"award-number":["CNS-2154490"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,12,2]]},"DOI":"10.1145\/3658644.3670305","type":"proceedings-article","created":{"date-parts":[[2024,12,9]],"date-time":"2024-12-09T12:19:20Z","timestamp":1733746760000},"page":"4047-4061","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["PathGES: An Efficient and Secure Graph Encryption Scheme for Shortest Path Queries"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8415-6237","authenticated-orcid":false,"given":"Francesca","family":"Falzon","sequence":"first","affiliation":[{"name":"ETH Z\u00fcrich, Z\u00fcrich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-6937-9197","authenticated-orcid":false,"given":"Esha","family":"Ghosh","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, WA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5145-4489","authenticated-orcid":false,"given":"Kenneth G.","family":"Paterson","sequence":"additional","affiliation":[{"name":"ETH Z\u00fcrich, Z\u00fcrich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2445-6064","authenticated-orcid":false,"given":"Roberto","family":"Tamassia","sequence":"additional","affiliation":[{"name":"Brown University, Providence, RI, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,12,9]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"https:\/\/aws.amazon.com\/neptune\/ Accessed on","author":"Neptune Amazon","year":"2022","unstructured":"Amazon. 2021. Amazon Neptune. https:\/\/aws.amazon.com\/neptune\/ Accessed on September 10, 2022."},{"key":"e_1_3_2_1_2_1","unstructured":"Heer Ambavi Mridul Sharma and Varun Gohil. 2020. Densest-Subgraph-Discovery. https:\/\/github.com\/varungohil\/Densest-Subgraph-Discovery."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978303"},{"key":"e_1_3_2_1_4_1","volume-title":"Searchable Encryption: New Constructions of Encrypted Databases. Universit\u00e9 de Rennes 1.","author":"Bost Rapha\u00ebl","year":"2018","unstructured":"Rapha\u00ebl Bost. 2018. Searchable Encryption: New Constructions of Encrypted Databases. Universit\u00e9 de Rennes 1."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.2478\/popets-2019-0062"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3133980"},{"key":"e_1_3_2_1_7_1","first-page":"1","article-title":"Preserving Communities in Anonymized Social","volume":"8","author":"Campan Alina","year":"2015","unstructured":"Alina Campan, Yasmeen Alufaisan, and Traian Marius Truta. 2015. Preserving Communities in Anonymized Social Networks. Trans. Data Privacy, Vol. 8, 1 (dec 2015), 55--87.","journal-title":"Networks. Trans. Data Privacy"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2810103.2813700"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14722\/ndss.2014.23264"},{"key":"e_1_3_2_1_10_1","volume-title":"Advances in Cryptology (CRYPTO)","author":"Cash David","unstructured":"David Cash, Stanislaw Jarecki, Charanjit Jutla, Hugo Krawczyk, Marcel-Cuatualin Rocsu, and Michael Steiner. 2013. Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries. In Advances in Cryptology (CRYPTO). Springer, Lyon, France, 353--373."},{"key":"e_1_3_2_1_11_1","volume-title":"Improved Structured Encryption for SQL Databases via Hybrid Indexing","author":"Cash David","unstructured":"David Cash, Ruth Ng, and Adam Rivkin. 2021. Improved Structured Encryption for SQL Databases via Hybrid Indexing. In Applied Cryptography and Network Security, Kazue Sako and Nils Ole Tippenhauer (Eds.). Springer International Publishing, Cham, 480--510."},{"key":"e_1_3_2_1_12_1","first-page":"13","article-title":"GraphOS","volume":"16","author":"Chamani Javad Ghareh","year":"2023","unstructured":"Javad Ghareh Chamani, Ioannis Demertzis, Dimitrios Papadopoulos, Charalampos Papamanthou, and Rasool Jalili. 2023. GraphOS: Towards Oblivious Graph Processing. Proc. VLDB Endow., Vol. 16, 13 (sep 2023), 4324--4338.","journal-title":"Towards Oblivious Graph Processing. Proc. VLDB Endow."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/646688.702972"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17373-8_33"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/545381.545503"},{"key":"e_1_3_2_1_16_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, Third Edition 3rd ed.). The MIT Press.","edition":"3"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1180405.1180417"},{"key":"e_1_3_2_1_18_1","volume-title":"30th USENIX Security Symposium, USENIX Security 2021","author":"Damie Marc","year":"2021","unstructured":"Marc Damie, Florian Hahn, and Andreas Peter. 2021. A Highly Accurate Query-Recovery Attack against Searchable Encryption using Non-Indexed Documents. In 30th USENIX Security Symposium, USENIX Security 2021, August 11--13, 2021, Michael Bailey and Rachel Greenstadt (Eds.). USENIX Association, 143--160. https:\/\/www.usenix.org\/conference\/usenixsecurity21\/presentation\/damie"},{"key":"e_1_3_2_1_19_1","unstructured":"NetworkX Developers. 2021. NetworkX. https:\/\/networkx.org\/ version 2.6.2."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2023.3241164"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Francesca Falzon Esha Ghosh Kenneth G. Paterson and Roberto Tamassia. 2024. PathGES: An Efficient and Secure Graph Encryption Scheme for Shortest Path Queries. Cryptology ePrint Archive Paper 2024\/845. https:\/\/eprint.iacr.org\/2024\/845 https:\/\/eprint.iacr.org\/2024\/845.","DOI":"10.1145\/3658644.3670305"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3372297.3417275"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3574245.3574247"},{"key":"e_1_3_2_1_24_1","volume-title":"Paterson","author":"Falzon Francesca","year":"2022","unstructured":"Francesca Falzon and Kenneth G. Paterson. 2022. An Efficient Query Recovery Attack Against a\u00a0Graph Encryption Scheme. In Computer Security -- ESORICS 2022: 27th European Symposium on Research in Computer Security, Copenhagen, Denmark, September 26--30, 2022, Proceedings, Part I (Copenhagen, Denmark). Springer-Verlag, Berlin, Heidelberg, 325--345."},{"key":"e_1_3_2_1_25_1","volume-title":"A fully homomorphic encryption scheme","author":"Gentry Craig","unstructured":"Craig Gentry and Dan Boneh. 2009. A fully homomorphic encryption scheme. Vol. 20:09. Stanford university Stanford."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3243734.3243833"},{"key":"e_1_3_2_1_27_1","volume-title":"Efficient Graph Encryption Scheme for Shortest Path Queries","author":"Ghosh Esha","unstructured":"Esha Ghosh, Seny Kamara, and Roberto Tamassia. 2021. Efficient Graph Encryption Scheme for Shortest Path Queries. Association for Computing Machinery, New York, NY, USA, 516--525."},{"key":"e_1_3_2_1_28_1","unstructured":"Anselme Goetschmann. 2020. Design and Analysis of Graph Encryption Schemes. Master's Thesis. ETH Z\u00fcrich."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69507-3_6"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28416"},{"key":"e_1_3_2_1_31_1","volume-title":"Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security","author":"Grubbs Paul","unstructured":"Paul Grubbs, Marie-Sarah Lacharite, Brice Minaud, and Kenneth G. Paterson. 2018. 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 (Toronto, Canada) (CCS '18). Association for Computing Machinery, New York, NY, USA, 315--331."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-03326-2_6"},{"key":"e_1_3_2_1_33_1","volume-title":"Proceedings, Part I","author":"Kamara Seny","year":"2018","unstructured":"Seny Kamara, Tarik Moataz, and Olya Ohrimenko. 2018. Structured Encryption and Leakage Suppression. In Advances in Cryptology -- CRYPTO 2018: 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19--23, 2018, Proceedings, Part I (Santa Barbara, CA, USA). Springer-Verlag, Berlin, Heidelberg, 339--370."},{"key":"e_1_3_2_1_34_1","volume-title":"Parallel and Dynamic Searchable Symmetric Encryption","author":"Kamara Seny","unstructured":"Seny Kamara and Charalampos Papamanthou. 2013. Parallel and Dynamic Searchable Symmetric Encryption. In Financial Cryptography and Data Security, Ahmad-Reza Sadeghi (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 258--274."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382196.2382298"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978386"},{"key":"e_1_3_2_1_37_1","unstructured":"Robert Kern. 2023. line-profiler. https:\/\/pypi.org\/project\/line-profiler\/ version4.0.3."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3560593"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP40000.2020.00029"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP40001.2021.00044"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2018.00002"},{"key":"e_1_3_2_1_42_1","volume-title":"Chow","author":"Lai Russell W. F.","year":"2017","unstructured":"Russell W. F. Lai and Sherman S. M. Chow. 2017. Forward-Secure Searchable Encryption on Labeled Bipartite Graphs. In Applied Cryptography and Network Security, Dieter Gollmann, Atsuko Miyaji, and Hiroaki Kikuchi (Eds.). Springer International Publishing, Cham, 478--497."},{"key":"e_1_3_2_1_43_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_3_2_1_44_1","volume-title":"Advances in Spatial and Temporal Databases, Claudia Bauzer Medeiros, Max J","author":"Li Feifei","unstructured":"Feifei Li, Dihan Cheng, Marios Hadjieleftheriou, George Kollios, and Shang-Hua Teng. 2005. On Trip Planning Queries in Spatial Databases. In Advances in Spatial and Temporal Databases, Claudia Bauzer Medeiros, Max J. Egenhofer, and Elisa Bertino (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 273--290."},{"key":"e_1_3_2_1_45_1","volume-title":"Forward and Backward Secure Searchable Encryption Scheme Supporting Conjunctive Queries over Bipartite Graphs","author":"Li Mingyue","year":"2021","unstructured":"Mingyue Li, Chunfu Jia, Ruizhong Du, and Wei Shao. 2021. Forward and Backward Secure Searchable Encryption Scheme Supporting Conjunctive Queries over Bipartite Graphs. IEEE Transactions on Cloud Computing (2021), 1--1."},{"key":"e_1_3_2_1_46_1","volume-title":"Forward and Backward Secure Searchable Encryption Scheme Supporting Conjunctive Queries over Bipartite Graphs","author":"Li Mingyue","year":"2021","unstructured":"Mingyue Li, Chunfu Jia, Ruizhong Du, and Wei Shao. 2021. Forward and Backward Secure Searchable Encryption Scheme Supporting Conjunctive Queries over Bipartite Graphs. IEEE Transactions on Cloud Computing (2021), 1--1."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSUSC.2017.2704163"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2018.2880981"},{"key":"e_1_3_2_1_49_1","unstructured":"Kevin Scott Mader. 2019. Parsing SBB Routes as a Graph. https:\/\/www.kaggle.com\/code\/kmader\/parsing-sbb-routes-as-a-graph\/notebook."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460120.3484552"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2810103.2813672"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212352"},{"key":"e_1_3_2_1_53_1","volume-title":"2014 IEEE Symposium on Security and Privacy. 639--654","author":"Naveed Muhammad","unstructured":"Muhammad Naveed, Manoj Prabhakaran, and Carl A. Gunter. 2014. Dynamic Searchable Encryption via Blind Storage. In 2014 IEEE Symposium on Security and Privacy. 639--654."},{"key":"e_1_3_2_1_54_1","volume-title":"https:\/\/neo4j.com\/ Accessed on","author":"Inc. Neo4j. 2021. Neo4j.","year":"2021","unstructured":"Inc. Neo4j. 2021. Neo4j. https:\/\/neo4j.com\/ Accessed on September 10, 2021."},{"key":"e_1_3_2_1_55_1","unstructured":"Ruth Ng Alexander Hoover David Cash and Eileen Ee. 2023. Structured Encryption for Indirect Addressing. IACR Cryptol. ePrint Arch. (2023) 1146. https:\/\/eprint.iacr.org\/2023\/1146"},{"key":"e_1_3_2_1_56_1","volume-title":"https:\/\/graphdb.ontotext.com\/ Accessed on","author":"DB.","year":"2022","unstructured":"Ontotext. 2021. GraphDB. https:\/\/graphdb.ontotext.com\/ Accessed on September 10, 2022."},{"key":"e_1_3_2_1_57_1","volume-title":"30th USENIX Security Symposium, USENIX Security 2021","author":"Oya Simon","year":"2021","unstructured":"Simon Oya and Florian Kerschbaum. 2021. Hiding the Access Pattern is Not Enough: Exploiting Search Pattern Leakage in Searchable Encryption. In 30th USENIX Security Symposium, USENIX Security 2021, August 11--13, 2021, Michael Bailey and Rachel Greenstadt (Eds.). USENIX Association, 127--142. https:\/\/www.usenix.org\/conference\/usenixsecurity21\/presentation\/oya"},{"key":"e_1_3_2_1_58_1","volume-title":"Moesfa Soeheila Mohamad, and Muhammad Reza Z'aba","author":"Poh Geong Sen","year":"2012","unstructured":"Geong Sen Poh, Moesfa Soeheila Mohamad, and Muhammad Reza Z'aba. 2012. Structured Encryption for Conceptual Graphs. In Advances in Information and Computer Security, Goichiro Hanaoka and Toshihiro Yamauchi (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 105--122."},{"key":"e_1_3_2_1_59_1","unstructured":"Python Cryptographic Authority. 2023. pyca\/cryptography. https:\/\/cryptography.io\/en\/latest\/ version 39.0.0."},{"key":"e_1_3_2_1_60_1","unstructured":"Open-Data-Plattform \u00f6V Schweiz. 2016. Fahrplan 2016 (GTFS). https:\/\/opentransportdata.swiss\/en\/dataset\/timetable-2016-gtfs."},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902291"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIFS.2017.2774451"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/SECPRI.2000.848445"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213957"},{"key":"e_1_3_2_1_66_1","volume-title":"FC 2017, Sliema, Malta, April 3--7","volume":"97","author":"Wang Qian","year":"2017","unstructured":"Qian Wang, Kui Ren, Minxin Du, Qi Li, and Aziz Mohaisen. 2017. SecGDB: Graph Encryption for Exact Shortest Distance Queries with Efficient Updates. In Financial Cryptography and Data Security - 21st International Conference, FC 2017, Sliema, Malta, April 3--7, 2017, Revised Selected Papers (Lecture Notes in Computer Science, Vol. 10322), Aggelos Kiayias (Ed.). Springer, 79--97."},{"key":"e_1_3_2_1_67_1","volume-title":"Privacy-Preserving Shortest Path Computation. In 23rd Annual Network and Distributed System Security Symposium, NDSS 2016","author":"Wu David J.","year":"2016","unstructured":"David J. Wu, Joe Zimmerman, J\u00e9r\u00e9my Planul, and John C. Mitchell. 2016. Privacy-Preserving Shortest Path Computation. In 23rd Annual Network and Distributed System Security Symposium, NDSS 2016, San Diego, California, USA, February 21--24, 2016. The Internet Society."},{"key":"e_1_3_2_1_68_1","first-page":"11","article-title":"Shortest-Path Queries on Complex Networks","volume":"15","author":"Zhang Junhua","year":"2022","unstructured":"Junhua Zhang, Wentao Li, Long Yuan, Lu Qin, Ying Zhang, and Lijun Chang. 2022. Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement. Proc. VLDB Endow., Vol. 15, 11 (jul 2022), 2640--2652.","journal-title":"Experiments, Analyses, and Improvement. Proc. VLDB Endow."}],"event":{"name":"CCS '24: ACM SIGSAC Conference on Computer and Communications Security","location":"Salt Lake City UT USA","acronym":"CCS '24","sponsor":["SIGSAC ACM Special Interest Group on Security, Audit, and Control"]},"container-title":["Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3658644.3670305","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3658644.3670305","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T06:23:27Z","timestamp":1755843807000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3658644.3670305"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,2]]},"references-count":68,"alternative-id":["10.1145\/3658644.3670305","10.1145\/3658644"],"URL":"https:\/\/doi.org\/10.1145\/3658644.3670305","relation":{},"subject":[],"published":{"date-parts":[[2024,12,2]]},"assertion":[{"value":"2024-12-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}