{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T11:16:14Z","timestamp":1780053374387,"version":"3.54.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,10,14]],"date-time":"2023-10-14T00:00:00Z","timestamp":1697241600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"R&D for Trustworthy Networking for Smart and Connected Communities"},{"name":"Commissioned Research of National Institute of Information and Communications Technology","award":["JP21H03431, JP19H05665"],"award-info":[{"award-number":["JP21H03431, JP19H05665"]}]},{"name":"National Science Foundation","award":["1647015, 1818901, CNS-2030611, CNS-1818942, SaTC-2030624, SaTC-2030611, ECCS-2319995"],"award-info":[{"award-number":["1647015, 1818901, CNS-2030611, CNS-1818942, SaTC-2030624, SaTC-2030611, ECCS-2319995"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Cyber-Phys. Syst."],"published-print":{"date-parts":[[2023,10,31]]},"abstract":"<jats:p>\n            Route Planning Systems (RPS) are a core component of autonomous personal transport systems essential for safe and efficient navigation of dynamic urban environments with the support of edge-based smart city infrastructure, but they also raise concerns about user route privacy in the context of both privately owned and commercial vehicles. Numerous high-profile data breaches in recent years have fortunately motivated research on privacy-preserving RPS, but most of them are rendered impractical by greatly increased communication and processing overhead. We address this by proposing an approach called Hierarchical Privacy-Preserving Route Planning (HPRoP), which divides and distributes the route-planning task across multiple levels and protects locations along the entire route. This is done by combining Inertial Flow partitioning, Private Information Retrieval (PIR), and Edge Computing techniques with our novel route-planning heuristic algorithm. Normalized metrics were also formulated to quantify the privacy of the source\/destination points (\n            <jats:italic>endpoint location privacy<\/jats:italic>\n            ) and the route itself (\n            <jats:italic>route privacy<\/jats:italic>\n            ). Evaluation on a simulated road network showed that HPRoP reliably produces routes differing only by \u2264 20% in length from optimal shortest paths, with completion times within \u223c 25 seconds, which is reasonable for a PIR-based approach. On top of this, more than half of the produced routes achieved near-optimal endpoint location privacy (\u223c 1.0) and good route privacy (\u2265 0.8).\n          <\/jats:p>","DOI":"10.1145\/3616874","type":"journal-article","created":{"date-parts":[[2023,8,30]],"date-time":"2023-08-30T09:50:01Z","timestamp":1693389001000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["HPRoP: Hierarchical Privacy-preserving Route Planning for Smart Cities"],"prefix":"10.1145","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9316-2863","authenticated-orcid":false,"given":"Francis","family":"Tiausas","sequence":"first","affiliation":[{"name":"Nara Institute of Science and Technology (NAIST), Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1579-3237","authenticated-orcid":false,"given":"Keiichi","family":"Yasumoto","sequence":"additional","affiliation":[{"name":"Nara Institute of Science and Technology (NAIST), Japan and RIKEN Center for Advanced Intelligence Project (AIP), Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0921-182X","authenticated-orcid":false,"given":"Jose Paolo","family":"Talusan","sequence":"additional","affiliation":[{"name":"Vanderbilt University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7542-4826","authenticated-orcid":false,"given":"Hayato","family":"Yamana","sequence":"additional","affiliation":[{"name":"Waseda University, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2273-4876","authenticated-orcid":false,"given":"Hirozumi","family":"Yamaguchi","sequence":"additional","affiliation":[{"name":"Osaka University, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3596-9447","authenticated-orcid":false,"given":"Shameek","family":"Bhattacharjee","sequence":"additional","affiliation":[{"name":"Western Michigan University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0168-4948","authenticated-orcid":false,"given":"Abhishek","family":"Dubey","sequence":"additional","affiliation":[{"name":"Vanderbilt University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9471-0868","authenticated-orcid":false,"given":"Sajal K.","family":"Das","sequence":"additional","affiliation":[{"name":"Missouri University of Science and Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,10,14]]},"reference":[{"key":"e_1_3_1_2_2","first-page":"3918","volume-title":"Proceedings of the Web Conference","author":"Aggarwal Gaurav","year":"2021","unstructured":"Gaurav Aggarwal, Sreenivas Gollapudi, and Ali Kemal Sinop. 2021. Sketch-based algorithms for approximate shortest paths in road networks. In Proceedings of the Web Conference. 3918\u20133929."},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2018.00062"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.adhoc.2021.102680"},{"key":"e_1_3_1_5_2","article-title":"A security and privacy preserved intelligent vehicle navigation system","author":"Baruah Barnana","year":"2022","unstructured":"Barnana Baruah and Subhasish Dhal. 2022. A security and privacy preserved intelligent vehicle navigation system. IEEE Trans. Depend. Sec. Comput. 20, 2 (2022).","journal-title":"IEEE Trans. Depend. Sec. Comput."},{"key":"e_1_3_1_6_2","first-page":"55","volume-title":"Proceedings of the 20th Annual International Cryptology Conference","author":"Beimel Amos","year":"2000","unstructured":"Amos Beimel, Yuval Ishai, and Tal Malkin. 2000. Reducing the servers computation in private information retrieval: PIR with preprocessing. In Proceedings of the 20th Annual International Cryptology Conference. Springer, 55\u201373."},{"key":"e_1_3_1_7_2","first-page":"577","volume-title":"Proceedings of the 16th International Conference on the Theory and Application of Cryptology and Information Security","author":"Chase Melissa","year":"2010","unstructured":"Melissa Chase and Seny Kamara. 2010. Structured encryption and controlled disclosure. In Proceedings of the 16th International Conference on the Theory and Application of Cryptology and Information Security. Springer, 577\u2013594."},{"key":"e_1_3_1_8_2","first-page":"304","volume-title":"Proceedings of the 29th Annual ACM Symposium on Theory of Computing","author":"Chor Benny","year":"1997","unstructured":"Benny Chor and Niv Gilboa. 1997. Computationally private information retrieval. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing. 304\u2013313."},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.10.2.163"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403098"},{"key":"e_1_3_1_11_2","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","year":"2009","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms. MIT Press."},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2014.0579"},{"key":"e_1_3_1_13_2","first-page":"1135","volume-title":"Proceedings of the IEEE International Parallel & Distributed Processing Symposium","author":"Delling Daniel","year":"2011","unstructured":"Daniel Delling, Andrew V. Goldberg, Ilya Razenshteyn, and Renato F. Werneck. 2011. Graph partitioning with natural cuts. In Proceedings of the IEEE International Parallel & Distributed Processing Symposium. IEEE, 1135\u20131146."},{"key":"e_1_3_1_14_2","article-title":"Somewhat practical fully homomorphic encryption","author":"Fan Junfeng","year":"2012","unstructured":"Junfeng Fan and Frederik Vercauteren. 2012. Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive (2012). https:\/\/eprint.iacr.org\/2012\/144","journal-title":"Cryptology ePrint Archive"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1049\/iet-cps.2019.0042"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/1868470.1868479"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1110.0401"},{"key":"e_1_3_1_18_2","first-page":"516","volume-title":"Proceedings of the ACM Asia Conference on Computer and Communications Security","author":"Ghosh Esha","year":"2021","unstructured":"Esha Ghosh, Seny Kamara, and Roberto Tamassia. 2021. Efficient graph encryption scheme for shortest path queries. In Proceedings of the ACM Asia Conference on Computer and Communications Security. 516\u2013525."},{"key":"e_1_3_1_19_2","first-page":"156","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905)","volume":"5","author":"Goldberg Andrew V.","year":"2005","unstructured":"Andrew V. Goldberg and Chris Harrelson. 2005. Computing the shortest path: A search meets graph theory. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905), Vol. 5. Citeseer, 156\u2013165."},{"key":"e_1_3_1_20_2","article-title":"One server for the price of two: Simple and fast single-server private information retrieval","author":"Henzinger Alexandra","year":"2022","unstructured":"Alexandra Henzinger, Matthew M. Hong, Henry Corrigan-Gibbs, Sarah Meiklejohn, and Vinod Vaikuntanathan. 2022. One server for the price of two: Simple and fast single-server private information retrieval. Cryptology ePrint Archive (2022). https:\/\/eprint.iacr.org\/2022\/949","journal-title":"Cryptology ePrint Archive"},{"key":"e_1_3_1_21_2","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1090\/dimacs\/074\/03","article-title":"Fast point-to-point shortest path computations with arc-flags","volume":"74","author":"Hilger Moritz","year":"2009","unstructured":"Moritz Hilger, Ekkehard K\u00f6hler, Rolf H. M\u00f6hring, and Heiko Schilling. 2009. Fast point-to-point shortest path computations with arc-flags. Short. Path Prob.: Ninth DIMACS Implement. Chall. 74 (2009), 41\u201372.","journal-title":"Short. Path Prob.: Ninth DIMACS Implement. Chall."},{"key":"e_1_3_1_22_2","first-page":"291","volume-title":"Proceedings of the Vehicle Navigation and Information Systems Conference (VNIS\u201994)","author":"Ikeda Takahiro","year":"1994","unstructured":"Takahiro Ikeda, Min-Yao Hsu, Hiroshi Imai, Shigeki Nishimura, Hiroshi Shimoura, Takeo Hashimoto, Kenji Tenmoku, and Kunihiko Mitoh. 1994. A fast algorithm for finding better routes by AI search techniques. In Proceedings of the Vehicle Navigation and Information Systems Conference (VNIS\u201994). IEEE, 291\u2013296."},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2002.806806"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2002.1033772"},{"issue":"2","key":"e_1_3_1_25_2","first-page":"1133","article-title":"Privacy-preserving navigation supporting similar queries in vehicular networks","volume":"19","author":"Li Meng","year":"2020","unstructured":"Meng Li, Yifei Chen, Shuli Zheng, Donghui Hu, Chhagan Lal, and Mauro Conti. 2020. Privacy-preserving navigation supporting similar queries in vehicular networks. IEEE Trans. Depend. Sec. Comput. 19, 2 (2020), 1133\u20131148.","journal-title":"IEEE Trans. Depend. Sec. Comput."},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3430507"},{"issue":"1","key":"e_1_3_1_27_2","first-page":"192","article-title":"Enabling privacy-preserving shortest distance queries on encrypted graph data","volume":"18","author":"Liu Chang","year":"2018","unstructured":"Chang Liu, Liehuang Zhu, Xiangjian He, and Jinjun Chen. 2018. Enabling privacy-preserving shortest distance queries on encrypted graph data. IEEE Trans. Depend. Sec. Comput. 18, 1 (2018), 192\u2013204.","journal-title":"IEEE Trans. Depend. Sec. Comput."},{"key":"e_1_3_1_28_2","first-page":"930","volume-title":"Proceedings of the IEEE Symposium on Security and Privacy (SP\u201922)","author":"Menon Samir Jordan","year":"2022","unstructured":"Samir Jordan Menon and David J. Wu. 2022. Spiral: Fast, high-rate single-server PIR via FHE composition. In Proceedings of the IEEE Symposium on Security and Privacy (SP\u201922). IEEE, 930\u2013947."},{"key":"e_1_3_1_29_2","first-page":"136","volume-title":"Proceedings of the IEEE 29th International Conference on Data Engineering Workshops (ICDEW\u201913)","author":"Mouratidis Kyriakos","year":"2013","unstructured":"Kyriakos Mouratidis. 2013. Strong location privacy: A case study on shortest path queries. In Proceedings of the IEEE 29th International Conference on Data Engineering Workshops (ICDEW\u201913). IEEE, 136\u2013143."},{"key":"e_1_3_1_30_2","first-page":"2292","volume-title":"Proceedings of the ACM SIGSAC Conference on Computer and Communications Security","author":"Mughees Muhammad Haris","year":"2021","unstructured":"Muhammad Haris Mughees, Hao Chen, and Ling Ren. 2021. OnionPIR: Response efficient single-server PIR. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security. 2292\u20132306."},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2018.2873950"},{"key":"e_1_3_1_32_2","article-title":"How to exchange secrets with oblivious transfer","author":"Rabin Michael O.","year":"2005","unstructured":"Michael O. Rabin. 2005. How to exchange secrets with oblivious transfer. Cryptology ePrint Archive (2005). https:\/\/eprint.iacr.org\/2005\/187","journal-title":"Cryptology ePrint Archive"},{"key":"e_1_3_1_33_2","first-page":"16","volume-title":"Proceedings of the 14th Workshop on Algorithm Engineering and Experiments (ALENEX\u201912)","author":"Sanders Peter","year":"2012","unstructured":"Peter Sanders and Christian Schulz. 2012. Distributed evolutionary graph partitioning. In Proceedings of the 14th Workshop on Algorithm Engineering and Experiments (ALENEX\u201912). SIAM, 16\u201329."},{"key":"e_1_3_1_34_2","first-page":"286","volume-title":"Proceedings of the International Symposium on Experimental Algorithms","author":"Schild Aaron","year":"2015","unstructured":"Aaron Schild and Christian Sommer. 2015. On balanced separators in road networks. In Proceedings of the International Symposium on Experimental Algorithms. Springer, 286\u2013297."},{"key":"e_1_3_1_35_2","volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916)","author":"Sommer Christian","year":"2016","unstructured":"Christian Sommer. 2016. All-pairs approximate shortest paths and distance oracle preprocessing. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_1_36_2","article-title":"Privacy-preserving shortest path computation","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. arXiv preprint arXiv:1601.02281 (2016).","journal-title":"arXiv preprint arXiv:1601.02281"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.25"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2019.07.082"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11277-017-4299-8"},{"key":"e_1_3_1_40_2","article-title":"EPNS: Efficient privacy preserving intelligent traffic navigation from multiparty delegated computation in cloud-assisted VANETs","author":"Zhou Jun","year":"2021","unstructured":"Jun Zhou, Shiying Chen, Kim-Kwang Raymond Choo, Zhenfu Cao, and Xiaolei Dong. 2021. EPNS: Efficient privacy preserving intelligent traffic navigation from multiparty delegated computation in cloud-assisted VANETs. IEEE Trans. Mob. Comput. 22, 3 (2021).","journal-title":"IEEE Trans. Mob. Comput."}],"container-title":["ACM Transactions on Cyber-Physical Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3616874","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3616874","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:49:13Z","timestamp":1750286953000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3616874"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,14]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,10,31]]}},"alternative-id":["10.1145\/3616874"],"URL":"https:\/\/doi.org\/10.1145\/3616874","relation":{},"ISSN":["2378-962X","2378-9638"],"issn-type":[{"value":"2378-962X","type":"print"},{"value":"2378-9638","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,14]]},"assertion":[{"value":"2023-01-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-08-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-10-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}