HPRoP: Hierarchical Privacy-Preserving Route Planning for
Smart Cities
FRANCIS TIAUSAS, Nara Institute of Science and Technology (NAIST), Japan
KEIICHI YASUMOTO, Nara Institute of Science and Technology (NAIST), Japan and RIKEN Center for
Advanced Intelligence Project (AIP), JapanJOSE PAOLO TALUSAN, Vanderbilt University, USA
HAYATO YAMANA, Waseda University, JapanHIROZUMI YAMAGUCHI, Osaka University, JapanSHAMEEK BHATTACHARJEE, Western Michigan University, USA
ABHISHEK DUBEY, Vanderbilt University, USA
SAJAL K. DAS, Missouri University of Science and Technology, USA
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 andcommercial vehicles. Numerous high profile data breaches in recent years have fortunately motivated researchon privacy-preserving RPS, but most of them are rendered impractical by greatly increased communication andprocessing overhead. We address this by proposing an approach called Hierarchical Privacy-Preserving RoutePlanning (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 (endpoint location privacy)
and the route itself (route privacy). Evaluation on a simulated road network showed that HPRoP reliably
produces routes differing only by ≤ 20% in length from optimal shortest paths, with completion times within∼ 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 (∼ 1.0) and good route privacy (≥ 0.8).
CCS Concepts: • Security and privacy → Privacy-preserving protocols; Domain-specific security and privacy
architectures.
Additional Key Words and Phrases: Route Planning Services, Location Privacy, Route Planning Algorithms
Authors’ addresses: Francis Tiausas, Nara Institute of Science and Technology (NAIST), Ikoma, 630-0192, Nara, Japan,
tiausas.francis_jerome.ta5@is.naist.jp; Keiichi Yasumoto, yasumoto@is.naist.jp, Nara Institute of Science and Technology(NAIST), Ikoma, 630-0192, Nara, Japan and RIKEN Center for Advanced Intelligence Project (AIP), Tokyo, 103-0027,
Japan; Jose Paolo Talusan, jose.paolo.talusan@vanderbilt.edu, Vanderbilt University, 2201 West End, Nashville, Tennessee,
USA; Hayato Yamana, yamana@waseda.jp, Waseda University, 1-104 Totsukamachi, Shinjuku, Tokyo, Japan; Hirozumi
Yamaguchi, h-yamagu@ist.osaka-u.ac.jp, Osaka University, 1-1 Yamadaoka, Suita, Osaka, Japan; Shameek Bhattacharjee,
shameek.bhattacharjee@wmich.edu, Western Michigan University, 1903 W Michigan Ave., Kalamazoo, Michigan, USA;
Abhishek Dubey, abhishek.dubey@vanderbilt.edu, Vanderbilt University, 2201 West End, Nashville, Tennessee, USA; Sajal
K. Das, sdas@mst.edu, Missouri University of Science and Technology, 300 W 13th St., Rolla, Missouri, USA.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee
provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice andthe full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored.
Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires
prior specific permission and/or a fee. Request permissions from permissions@acm.org.
© 2023 Association for Computing Machinery.
2378-962X/2023/10-ART111 $15.00
https://doi.org/XXXXXXX.XXXXXXX
ACM Trans. Cyber-Phys. Syst., Vol. 6, No. 4, Article 111. Publication date: October 2023.

111

111:2Tiausas, et al.

ACM Reference Format:
Francis Tiausas, Keiichi Yasumoto, Jose Paolo Talusan, Hayato Yamana, Hirozumi Yamaguchi, Shameek
Bhattacharjee, Abhishek Dubey, and Sajal K. Das. 2023. HPRoP: Hierarchical Privacy-Preserving RoutePlanning for Smart Cities. ACM Trans. Cyber-Phys. Syst. 6, 4, Article 111 (October 2023), 25 pages. https://doi.org/XXXXXXX.XXXXXXX

1INTRODUCTION

Route Planning Services (RPS) are web-based applications which can calculate routes between two
chosen points in a road network, and are indispensable navigational aids for commuters, vehicle
operators, autonomous vehicles, etc. However, these same routes can reveal points of interest [15]which may contain users’ places of work and residence, in addition to highly-sensitive information
about their political, sexual, or religious tendencies [30]. Furthermore, this exposes users to risks oftargeted criminal acts, mass surveillance, discrimination, etc. The rise in high-profile data breaches
over the past decade has highlighted the importance of protecting user location (and route) data,and has spurred many recent works focusing on adding privacy-preserving mechanisms to RPS.
In the RPS context, privacy primarily entails keeping users’ origin, destination, and route information from being acquired by untrusted entities. It exists side-by-side with other important Qualityof Service (QoS) metrics such as Utility (e.g. the accuracy of the routes, etc.) and Performance (e.g.
the response time of the RPS, etc.) which affect whether or not an RPS would gain widespread
adoption. Finding a good balance between these metrics is crucial for any privacy-preserving RPS.
For instance, privacy-preserving protocols for querying road traffic data have been developed for
Vehicle Ad-hoc Networks (VANETs) but these either offload the computation cost of route planning
onto the vehicle itself [24, 25, 39] or an external trusted entity [3, 4]. The latter approaches are
already done by modern RPS, while the former are not web-based RPS at all. Structured encryption schemes [17, 26, 37] provide privacy-protection for both user queries and road network data
while also being relatively lightweight and efficient but at the cost of inherently leaking somequery-related information which are detrimental to the privacy of user routes.
Aside from these, there are also works that utilize Private Information Retrieval (PIR) [7] since
this protocol has strong privacy guarantees. In an RPS, their efficiency depends mostly on therouting algorithm but are often considered too computationally-heavy to be used on very large
databases — such as the road network graph of a large city. As such, only a few examples of
PIR-based RPS have been developed over the past decade. One approach [35] compresses road
network graphs in a novel PIR-queryable manner but results in longer pre-processing and query
response times. The other approach [28] partitions the road network into disjoint subgraphs andthese are individually retrieved via PIR to inform a local routing algorithm on the user’s device. This
results in longer route completion times since many PIR queries are needed to complete the route.
Both approaches clearly entail a significant degradation of QoS which dissuades most mainstream
RPS from experimenting with and adopting them.
Our approach aims to create a RPS that addresses the aforementioned issues by fulfilling thefollowing three objectives: (1) produce close-to-optimal users’ routes, (2) provide strong privacy
guarantees for users’ route data, and (3) maintain an adequate level of performance by minimizing
processing and communication overhead as much as possible. The approach involves two phases.
In the pre-processing phase, a graph partitioning technique is used to hierarchically divide the road
network into balanced partitions. Routes within each partition are then pre-computed and stored
in separate databases, and the same is done for an additional set of routes between neighboring
partitions. In the routing phase, a novel hierarchical heuristic algorithm on the user’s device
privately obtains partial routes from the different partition databases using PIR, and iteratively
ACM Trans. Cyber-Phys. Syst., Vol. 6, No. 4, Article 111. Publication date: October 2023.

HPRoP: Hierarchical Privacy-Preserving Route Planning for Smart Cities

111:3

combines them to create a progressively finer route. We named the proposed approach, HierarchicalPrivacy-Preserving Route Planning (HPRoP), which makes the following key contributions:• A RPS that uses a hierarchical partitioning of the road network with a novel hierarchicalroute planning algorithm to produce routes with good optimal route approximation while
maintaining strong privacy guarantees and low route completion times,• A pair of privacy metrics — endpoint location privacy and route privacy — that aim to begeneral enough to be applicable to other privacy-preserving RPS while also accounting
for specific characteristics of PIR-based RPS (such as providing strong privacy guarantees
between routes in the same database), and• A comprehensive evaluation of the Utility, Privacy, and Performance of the proposed RPS ona simulated road network based on Osaka City against two PIR-based baseline approaches.
Note that the baseline approaches mentioned above were also developed solely for this paper toaddress the lack of recent PIR-based route planning approaches which HPRoP can be comparedagainst. However, we do not count them as separate contributions since they are primarily used as
an evaluation tool. The rest of this article is organized as follows. Section 2 presents a summaryof prior work related to privacy-preserving route planning. Section 3 discusses the mathematicalmodels, assumptions, and other preliminaries. Section 4 presents the concept and intuition behindroute planning under the constraints of PIR. Section 5 defines and discusses the privacy metrics
used to evaluate the RPS. Section 6 presents the key ideas behind the approach itself, and the detailsof the heuristic algorithm. Section 7 discusses the evaluation framework and the results. Section 8
concludes with a brief summary of the article and some notes on potential future work.
2

RELATED WORK

Most algorithms for calculating exact shortest paths require knowledge of the exact source anddestination locations. Classical algorithms like Dijkstra’s and Bellman-Ford [10] calculate routes
by repeatedly scanning connected vertices from some source point and assigning them weights
until a path to the destination point is found. Modern algorithms improve upon this by leveraging
unique properties of road networks. ALT [18] pre-computes distances to fixed landmarks, anduses them as lower bounds to informa a bidirectional A* search [21]. Contraction Hierarchies [16]pre-processes the network graph to establish “shortcut edges,” facilitating faster route calculation
between distant points. Customizable Route Planning [11] uses the network graph’s topology in their
metric-independent hierarchical routing method. Regardless, deploying these on the server-side
inevitably means that the user’s origin and destination must be divulged so that the final route canbe computed. Meanwhile, deploying these on the client-side means downloading large amounts ofroad network data, and computing routes on more resource-constrained machines. In other words,
the first case compromises privacy while the second degrades functionality.
Alternatively, algorithms for finding approximate shortest paths also exist, focusing on quickly
obtaining short routes rather than finding the exact shortest ones. Point-to-point variants of these[8, 22, 23] were developed at a time when mobile computational power was very limited, and havebeen outclassed by modern exact shortest path algorithms. Yet, these remain useful in All-Pairs
Shortest Path (APSP) distance oracles [1, 34] for speeding up goal-directed route calculations.
Recent research on privacy-preserving route planning techniques generally fall under three
categories: (1) Structured Encryption-based, (2) PIR-based, and (3) Other encryption-based schemes.
In addition, a number of schemes for privately querying road traffic information with applications
to vehicle navigation systems also exist, but, since these either perform route planning on thevehicle itself [24, 25, 39] or an external trusted entity [3, 4], these works have been excluded here.
ACM Trans. Cyber-Phys. Syst., Vol. 6, No. 4, Article 111. Publication date: October 2023.

111:4

Tiausas, et al.

Structured Encryption [6] refers to techniques that allows data structures to be encrypted suchthat these can be queried later in a privacy-preserving manner. They are typically more efficient interms of computation time and communication overhead at the cost of leaking a small amount of
information about the data and the queries. The approaches in [26, 37] use structured encryption
to find the shortest distance between vertex-pairs in encrypted graphs. These, however, are only
able to find shortest distance values instead of the actual shortest paths, and are vulnerable tocollusion between the storage and computing servers — which are essentially the same entity in the
RPS context. In contrast, [17] is able to retrieve the actual shortest paths on a single-server setup
which effectively eliminates the aforementioned issues. However, pre-computing the encrypted
database for large sparse graphs (i.e. with |𝑉 | ≥ 10, 000 and |𝐸| ≥ 30, 000) took upwards of 16.5
hours and produced very large files (around 4.4 GB), rendering it impractical for dynamic scenarios
such as real-time route planning. Additionally, while all three have heavily-constrained leakage
profiles, some of the information they inherently leak may be detrimental to route privacy. For
instance, the number of potential query elements (i.e. the database size) can be used to determine
the specific subgraph of the road network graph being used. Query repetitions and total queries
for route completion can be jointly analyzed across multiple sessions to deduce the actual route.
Different approaches may also leak other information in addition to the ones mentioned here.
PIR [7] is a technique that allows remote databases to be queried in such a way that the retrieved
element would not be revealed to the service provider or any third-party entity. PIR-based schemes,
therefore, have slightly stronger privacy guarantees in that repeated queries and underlying
database sizes are not leaked, but have the disadvantage of much higher communication overhead.
While most modern
implementations [2, 19, 27, 29] have become very communication-efficient√(i.e. up to 𝑂 ( 𝑁 )), they remain impractical for accessing a database of APSP in a large city. Thisis because PIR schemes need to go through each individual element to avoid leaking information
about the element being retrieved [5]. The approach in [35] describes a method for compressing
road network graphs via sign-decomposition combined with Yao’s garbled circuits [36] and PIR toprotect both user queries and said graph, giving it strong end-to-end privacy guarantees. However,it also has relatively long pre-processing and query response times since the protocol must operateon compressed and encrypted data at all times. The approach in [28] partitions the network graphinto disjoint sections (i.e. each consisting of a separate subgraph) which can then be retrieved via PIR
during local computation of a shortest path during the routing phase. While this requires minimal
pre-processing time, the total route completion time remains rather long since the locally-run
routing algorithm would need multiple PIR queries to complete a single route.
Other encryption-based schemes with much stronger privacy guarantees also exist but they arealso much less efficient than the previous two. For instance, [38] allows users to request routes
between arbitrary source and destination partitions, as well as within said partitions in a privacypreserving manner using 1-of-n Oblivious Transfer [31]. However, the scheme needs to compute
All-Pairs of Shortest Paths (APSP) for the aforementioned partitions during the routing phase,drastically slowing down query response times. Similarly, the work in [14] uses Paillier’s Encryption
to privately query outgoing edge weights from vertices in the road network graph which, in turn,is used to inform a route planning algorithm running locally on the user’s own device. The scheme,
unfortunately, has a very high communication overhead since it has to make a separate query forevery vertex that needs to be “scanned” by the routing algorithm.
As this work aims to achieve strong privacy guarantees for users’ routes while also meeting
utility and performance targets, PIR was chosen as the core privacy-preservation mechanism forthe proposed approach. Unlike structured encryption, it does not leak information about query

ACM Trans. Cyber-Phys. Syst., Vol. 6, No. 4, Article 111. Publication date: October 2023.

HPRoP: Hierarchical Privacy-Preserving Route Planning for Smart Cities

111:5

repetitions, which can potentially be analyzed by an adversary to distinguish between different
route requests by the same user.
3

MODELS AND ASSUMPTIONSThis section presents the assumptions and mathematical models related to the road network graph,
its corresponding partition graph, and the “approximate” routes that can be derived from the latter.
Table 1. Summary of Symbols used in Sec. 3
SymbolDescription

𝐺 = (𝑉 , 𝐸 )𝑙𝐺 (𝑢, 𝑣)𝑠, 𝑑𝑟𝐺 (𝑠, 𝑑 )𝐿𝐺 (𝑟𝐺 (𝑠, 𝑑 ) )𝑅𝐺 (𝑠, 𝑑 )𝜌𝐺 (𝑠, 𝑑 )𝐺 𝑃 = (𝑃, 𝐶 )𝑝 = (𝑉𝑝 , 𝐸𝑝 )
𝑁 𝐵𝑝𝑢
ℓ
L
𝑃ℓ
𝑝𝑖ℓ
𝑥𝑢
𝑐 𝑝𝑢 𝑝 𝑣
𝑑𝑖𝑠𝑡𝐺 (𝑢, 𝑣)
D (𝑝 )C (𝜌 0 , ..., 𝜌𝑛 )∗ (𝑢, 𝑣)𝑟𝐺
∗ (𝑢, 𝑣) )𝛼 (𝑟𝐺Road network graph with road segments 𝐸 and intersections 𝑉
Length of a road segment having endpoints (𝑢, 𝑣)
Source (𝑠) and Destination (𝑑) vertices
Path/route between 𝑠 and 𝑑
Total length of path/route 𝑟𝐺 (𝑠, 𝑑 )All possible paths between 𝑠 and 𝑑
Shortest path between 𝑠 and 𝑑Partition graph derived from 𝐺 with the set of all partitions 𝑃 and the connections between them 𝐶
A partition (i.e., a subgraph of 𝐺) consisting of road segments 𝐸𝑝 and endpoints 𝑉𝑝 within it
Set of all neighboring partitions for partition 𝑝𝑢
Partition level
Maximum partition level (0 ≤ ℓ ≤ L)
Subset of partitions in 𝑃 at level ℓ
A partition belonging under 𝑃 ℓ with a given index 𝑖
Representative vertex for the partition 𝑝𝑢
A connection between partitions 𝑝𝑢 and 𝑝 𝑣 through shortest path 𝜌𝐺 (𝑥𝑢 , 𝑥 𝑣 )Shortest path distance between 𝑢 and 𝑣 in 𝐺
Database of shortest paths for partition 𝑝
Arbitrary route combination heuristic
Approximate shortest path between 𝑢 and 𝑣
Optimal route approximation metric

3.1

Road Network Partitioning Model

A road network can be modelled as a directed graph 𝐺 = (𝑉 , 𝐸) where the edges 𝐸 represent roadsegments, and the vertices 𝑉 represent either road intersections or terminals. Each road segment𝑒 ∈ 𝐸 is a directed edge between two vertices 𝑢, 𝑣 ∈ 𝑉 such that 𝑒 = (𝑢, 𝑣), with parallel opposing
lanes being represented by two directed edges going in opposite directions. The traversal costfor 𝑒 is given by its length, 𝑙𝐺 (𝑢, 𝑣). A route or path between two vertices 𝑠, 𝑑 ∈ 𝑉 is defined as
𝑠𝑑
𝑠𝑑
𝑠𝑑
𝑠𝑑
a sequence of vertices 𝑟𝐺 (𝑠, 𝑑) = (𝑣 𝑠𝑑
1 , 𝑣 2 , . . . , 𝑣 𝑛−1, 𝑣 𝑛 ) where the first vertex 𝑣 1 = 𝑠 and the
Í
|𝑟
(𝑠,𝑑
)
| −1
𝐺
𝑠𝑑 ).
last vertex 𝑣𝑛𝑠𝑑 = 𝑑. The total length of 𝑟𝐺 (𝑠, 𝑑) is given by 𝐿𝐺 (𝑟𝐺 (𝑠, 𝑑)) = 𝑖=1
𝑙𝐺 (𝑣𝑖𝑠𝑑 , 𝑣𝑖+1
Denoting all possible paths (between 𝑠 and 𝑑) as 𝑅𝐺 (𝑠, 𝑑), the Shortest Path is then:𝜌𝐺 (𝑠, 𝑑) = 𝑎𝑟𝑔 𝑚𝑖𝑛𝑟 ∈𝑅𝐺 (𝑠,𝑑 ) 𝐿𝐺 (𝑟 )(1)

Most modern route planning algorithms can already deal with very large road networks, but
typically do not incorporate route privacy protection mechanisms out of the box, as they tend to
significantly increase processing and communication overhead as mentioned in Sec. 2. However,if the route planning task can be divided, then the additional processing cost incurred by theprivacy mechanism can be distributed across multiple devices instead and ultimately improve RPS
performance. This is done by first dividing the road network into different areas called partitions.
An arbitrary partitioning of the road network graph 𝐺 is represented by a separate partition
graph 𝐺 𝑃 = (𝑃, 𝐶) where the vertices 𝑃 represent partitions and the edges 𝐶 represent connections
ACM Trans. Cyber-Phys. Syst., Vol. 6, No. 4, Article 111. Publication date: October 2023.

111:6

Tiausas, et al.

Fig. 1. Types of shortest paths stored by each partition

between them. Each partition 𝑝 ∈ 𝑃 is a subgraph 𝑝 = (𝑉𝑝 , 𝐸𝑝 ) such that 𝑉𝑝 ⊆ 𝑉 and 𝐸𝑝 ⊆ 𝐸. Eachconnection 𝑐 𝑝𝑢 𝑝 𝑣 ∈ 𝐶 is a shortest path 𝜌𝐺 (𝑥𝑢 , 𝑥 𝑣 ) between the representative vertices 𝑥𝑢 , 𝑥 𝑣 ∈ 𝑉 of
any two neighboring partitions 𝑝𝑢 , 𝑝 𝑣 ∈ 𝑃 where 𝑥𝑢 ∈ 𝑉𝑝𝑢 ∧ 𝑥 𝑣 ∈ 𝑉𝑝 𝑣 . Two partitions are considered“neighbors” if ∃ 𝑒 = (𝑢, 𝑣) s.t. 𝑒 ∈ 𝐸 ∧ 𝑢 ∈ 𝑉𝑝𝑢 ∧ 𝑣 ∈ 𝑉𝑝 𝑣 . Finally, the set of all neighboring partitions
for 𝑝𝑢 is defined as 𝑁 𝐵𝑝𝑢 = {𝑝 𝑣 |𝑝 𝑣 ∈ 𝑃 ∧ (𝑐 𝑝𝑢 𝑝 𝑣 ∈ 𝐶 ∨ 𝑐 𝑝 𝑣 𝑝𝑢 ∈ 𝐶)}
Representative vertices are ideally chosen to minimize the shortest path distance to all othervertices in the partition. Vertices with high graph centrality are good candidates, but our preliminary
experiments show that it is viable to simply choose the vertex closest to the geospatial average ofthe coordinates of each partition’s vertices with no impact on routing performance. Thus, representative vertices were chosen via this method. It then follows that 𝑙𝐺𝑃 (𝑝𝑢 , 𝑝 𝑣 ) = 𝐿𝐺 (𝜌𝐺 (𝑥𝑢 , 𝑥 𝑣 )).
For simplicity, the shortest path distance between any 𝑢, 𝑣 ∈ 𝐺 is represented by 𝑑𝑖𝑠𝑡𝐺 (𝑢, 𝑣), while
𝑑𝑖𝑠𝑡𝐺𝑃 (𝑝𝑢 , 𝑝 𝑣 ) refers to the shortest path distance between their containing partitions, 𝑝𝑢 , 𝑝 𝑣 ∈ 𝑃.
Partitions are defined in a hierarchical manner with the maximum partition level being L, and thesubset of partitions for each level ℓ < L denoted as 𝑃 ℓ ⊆ 𝑃 such that 𝑃 ℓ ⊂ 𝑃 ℓ −1 for ℓ > 0. A partition
may also be defined as 𝑝𝑖ℓ where ℓ is the partition’s level and 𝑖 is the partition’s index at that level
given 𝑃 ℓ = {𝑝 0ℓ , 𝑝 1ℓ , . . . , 𝑝𝑛ℓ }. The base level partition set 𝑃 0 contains only one partition/subgraph𝑝 00 = 𝐺 at ℓ = 0. Conversely, 𝑝 00 might be composed of several smaller partitions 𝑝 01 , 𝑝 11 , 𝑝 21 , and𝑝 31 at ℓ = 1 such that all of them are subgraphs of 𝑝 00 , and so on. For clarity, partition levels will
henceforth be referred to by their position (i.e., higher or lower) instead of their subgraph’s size.
Each partition 𝑝 ℓ has three sets of shortest path data as depicted in Fig. 1: (1) the shortest paths
within the partition 𝑝 ℓ (black edges), (2) the shortest paths to its neighboring partitions, 𝑁 𝐵𝑝 ℓ (blueedges), and (3) the shortest paths between the containing partition, 𝑝 ℓ −1 , to its own neighbors,
𝑁 𝐵𝑝 ℓ −1 (green edges). This database of shortest paths is represented by D (𝑝 ℓ ).
3.2

Approximate Shortest Path Model

Our approach relaxes the shortest path problem by accepting approximate shortest paths between
two areas (in this case, partitions) containing 𝑠 and 𝑑 in place of the exact shortest path between
the two points. This, in turn, reduces the number of queries required to obtain a route (hence,
faster route completion times) at the cost of potentially having slightly longer paths. These areformally defined here as follows. Given an arbitrary 𝑠, 𝑑 ∈ 𝑉 , the exact shortest path 𝜌𝐺 (𝑠, 𝑑) rarely
coincides with the shortest path 𝜌𝐺𝑃 (𝑥𝑠 , 𝑥𝑑 ) where 𝑥𝑠 and 𝑥𝑑 are the representative vertices in thesame partitions as 𝑠 and 𝑑, respectively. This is because only routes between representative vertices
ACM Trans. Cyber-Phys. Syst., Vol. 6, No. 4, Article 111. Publication date: October 2023.

HPRoP: Hierarchical Privacy-Preserving Route Planning for Smart Cities

111:7

of partitions in 𝑃 can be produced from 𝐺 𝑃 , and it is highly likely that 𝑠 ≠ 𝑥𝑠 or 𝑑 ≠ 𝑥𝑑 . However, it
it is still possible to “complete” the route by adding in the missing start and end sections. LettingC(𝜌 1, ..., 𝜌𝑛 ) be a route combination heuristic, the simplest “completed” route would be:(2)𝑟𝐺∗ (𝑠, 𝑑) = C(𝜌𝐺 (𝑠, 𝑥𝑠 ), 𝜌𝐺𝑃 (𝑥𝑠 , 𝑥𝑑 ), 𝜌𝐺 (𝑥𝑑 , 𝑑))This can be generalized further by replacing 𝜌𝐺𝑃 (𝑥𝑠 , 𝑥𝑑 ) with C(𝜌𝐺𝑃 (𝑥 1, 𝑥 2 ), . . . , 𝜌𝐺𝑃 (𝑥𝑛−1, 𝑥𝑛 )):𝑟𝐺∗ (𝑠, 𝑑) = C(𝜌𝐺 (𝑠, 𝑥𝑠 ), 𝜌𝐺𝑃 (𝑥 1, 𝑥 2 ), . . . , 𝜌𝐺𝑃 (𝑥𝑛−1, 𝑥𝑛 ), 𝜌𝐺 (𝑥𝑑 , 𝑑))(3)where 𝑥 1 = 𝑥𝑠 and 𝑥𝑛 = 𝑥𝑑 . In this work, these kinds of combined paths are designated as
approximate shortest paths, and their quality is measured based on how well they approximate theircounterpart exact shortest paths. This metric is defined as the optimal route approximation:𝑙𝐺 (𝑟𝐺∗ (𝑠, 𝑑))𝛼 (𝑟𝐺∗ (𝑠, 𝑑)) =(4)
𝑑𝑖𝑠𝑡𝐺∗ (𝑠, 𝑑)where 𝑙𝐺 (𝑟𝐺∗ (𝑠, 𝑑)) is the length of the approximate shortest path, and 𝑑𝑖𝑠𝑡𝐺 (𝑠, 𝑑) is the length ofthe exact shortest path in 𝐺.
3.3

Assumptions

Having presented the mathematical models relevant to route planning, we now state the coreassumptions in this work as follows. Foremost is that the RPS operates over a particular service
region, and is primarily used by the general public for their day-to-day activities. The service region
in this case is assumed to be a geographical area of arbitrary shape and size that has fixed bounds.
This area is assumed to have comprehensive road network data available such that a RPS can beused to calculate routes within it. This road network is assumed to be represented as a graph thatcan be divided multiple times to produce subgraphs representing partitions as per Sec. 3.1. Eachhighest-level partition is assumed to be handled by a distinct physical or virtual device for the
purpose of the RPS. Additionally, it is assumed that each partition can calculate, build, and maintainits own database of shortest paths D (𝑝) independent of its other tasks. This per-partition databaseis then assumed to be queryable by users in a privacy-preserving manner through PIR.
We additionally assume that all entities other than the user are potential threats — henceforth,simply called “adversaries” — interested in gaining access to the user’s route information. Note thatno distinction is made between the service providers themselves and malicious third-parties. The
kinds of information that can be leaked include the user’s: (1) exact origin, (2) exact destination,and (3) the calculated “route” between them.
4

ROUTE PLANNING WITH PIR
Table 2. Summary of Symbols used in Sec. 4
SymbolDescription

∗
𝑅𝐺
𝑚𝑎𝑥
𝐿𝐺
C𝑝𝑖𝑟
N𝑝
𝑎𝑑 𝑗
𝑉𝑝

Set of shortest paths between all possible pairs of vertices in 𝑉∗
Length of the longest path in the set, 𝑅𝐺
Constant representing the impact of database sizes on record retrieval times for PIR
Average number of vertices in a partition (across all 𝑝 ∈ 𝑃 )Set of vertices in partition 𝑝 that are adjacent to other partitions

𝑎𝑑 𝑗

Average number of vertices adjacent to other partitions (i.e. 𝑉𝑝 ) (across all 𝑝 ∈ 𝑃 )Average number of external connections (across all 𝑝 ∈ 𝑃 )

N𝑝
N𝑐

𝑎𝑑 𝑗

PIR can be used by RPS to provide strong privacy guarantees by protecting the database representation of the road network graph used to calculate routes. In the simplest case, consider a database
ACM Trans. Cyber-Phys. Syst., Vol. 6, No. 4, Article 111. Publication date: October 2023.

111:8Tiausas, et al.

containing APSP for the whole road network graph, indexed by pairs of origin and destination
vertices, (𝑠, 𝑑). PIR can then be used to retrieve any route between any two locations on the road
network using a single query (i.e. 𝑂 (1)) with very high privacy. This is the naive approach which is
not feasible in practice for two reasons: (1) it requires a prohibitively large amount of storage space,and (2) pre-computing APSP information for large road network graphs takes a very long time.
Assuming a graph with 10, 000 vertices, a longest path length of 20 vertices, and a 1-byte
representation for vertex data, the total PIR database size is already be around 2 GB. This is evenlarger for city-sized road networks such as Osaka City’s which has ∼ 99, 000 vertices (∼ 200.8𝑚𝑎𝑥 =GB keeping all other parameters same). In short, letting 𝑅𝐺∗ = {𝑟𝐺∗ (𝑢, 𝑣)|𝑢, 𝑣 ∈ 𝑉 } and 𝐿𝐺
2𝑚𝑎𝑥
𝐿𝐺 (arg max𝑟 ∈𝑅 ∗ |𝑟 |), the space complexity for such an approach is 𝑂 (|𝑉 | · 𝐿𝐺 ). This issue is𝐺made even worse by PIR since individual record retrieval times become slower with larger databasesizes. This has been verified through preliminary experiments where data retrieval times wereobserved to scale linearly with database sizes by a constant factor, C𝑝𝑖𝑟 , such that accessing a single
route would have a time complexity of 𝑂 (C𝑝𝑖𝑟 · |𝑉 | 2 ) ≈ 𝑂 (|𝑉 | 2 ) instead of the expected 𝑂 (1).
Since time complexity is heavily dependent on space-complexity for PIR-based approaches,existing works [28, 35] have focused on tackling the space complexity problem since pre-processing
is assumed to be done offline only once. This is not the case for real-world road networks, however,where traffic conditions can change very quickly. One way to solve this is by distributing route
data among several edge servers such that each one only manages vertices
for a distinct partition.
ÍThis reduces the time complexity to 𝑂 (|𝑉 | · N𝑝 ) where N𝑝 = 1/|𝑃 | · 𝑝 ∈𝑃 |𝑉𝑝 | is the average vertex𝑚𝑎𝑥 ). These
count per partition, while the per-partition space complexity becomes 𝑂 (N𝑝 · |𝑉 | · 𝐿𝐺
databases still need to be kept updated, but it is much easier to do so in a distributed manner.
However, dividing the data comes at the cost of weaker privacy since the set of route data stored
on the accessed edge server is assumed known to the adversary. This is analyzed further in Sec. 5.
Table 3. Summary of Time and Space Complexity for Sec. 4

4.1

Space Complexity

Time Complexity

Naive

𝑚𝑎𝑥 )
𝑂 (|𝑉 | 2 · 𝐿𝐺

𝑂 (|𝑉 | 2 )

EPR-D
APR-D

𝑎𝑑 𝑗
𝑂 (N𝑝 · [N𝑝 + N𝑝 ])∗,𝑚𝑎𝑥
𝑂 ([N𝑝2 + N𝑐 ] · 𝑅𝐺)

𝑂 (N𝑝 · [N𝑝 + N𝑝 ] · [|𝑉 | + |𝐸|𝑙𝑜𝑔|𝑉 |])𝑂 ([N𝑝2 + N𝑐 ] · [(|𝑃 | + |𝐶 |𝑙𝑜𝑔|𝑃 |) + 2)])𝑎𝑑 𝑗

Exact Partial Region Dijkstra’s Algorithm (EPR-D)

The space complexity problem can be mitigated further by storing only edge weights between
adjacent vertex pairs as this is the minimum information needed by Dijkstra’s algorithm. Thisis also known as the adjacency matrix representation which readily maps into a database which
can then be used with any PIR scheme. We designated this PIR-adapted approach as Exact Partial
Region Dijkstra’s Algorithm (EPR-D), since it simply partitions and distributes graph data acrossseveral edge servers, and produces exact shortest paths. A notable disadvantage is its use of separate
PIR queries to retrieve information for each vertex since the original algorithm tends to scan a
lot of vertices which can make route completion times very long. It is also possible to reidentify
routes based on the sequence of edge servers queried by the user. This is examined further in Sec.
5. This is reflected in its average time complexity of 𝑂 (N𝑝 · [N𝑝 + N𝑝𝑎𝑑 𝑗 ] · [|𝑉 | + |𝐸|𝑙𝑜𝑔|𝑉 |]) whereÍN𝑝𝑎𝑑 𝑗 = 1/|𝑃 | · 𝑝 ∈𝑃 |𝑉𝑝𝑎𝑑 𝑗 | is the average number of vertices adjacent to other partitions, in turn,
represented by 𝑉𝑝𝑎𝑑 𝑗 = {𝑣 |𝑣 ∉ 𝑉𝑝 ∧ [(𝑢, 𝑣) ∈ 𝐸 ∧ 𝑢 ∈ 𝑉𝑝 ]}. Meanwhile, its average per-partition
space complexity is 𝑂 (N𝑝 · [N𝑝 + N𝑝𝑎𝑑 𝑗 ]). Table 3 summarizes the complexity of EPR-D.
ACM Trans. Cyber-Phys. Syst., Vol. 6, No. 4, Article 111. Publication date: October 2023.

HPRoP: Hierarchical Privacy-Preserving Route Planning for Smart Cities

4.2

111:9

Approximate Partial Region Dijkstra’s Algorithm (APR-D)

A possible solution to the time complexity issue is by allowing the RPS to produce approximate
shortest paths instead of exact shortest paths. This can be done as follows: (1) calculate an approximate route between source and destination partitions 𝑝𝑠 and 𝑝𝑑 using Dijkstra’s algorithm overpartition graph 𝐺 𝑃 , (2) retrieve subpaths to both 𝑠 and 𝑑 from within their respective partitions
via database lookup, and (3) merge all obtained paths to form the final route. We designated thisapproach as Approximate Partial Region Dijkstra’s Algorithm (APR-D), since it produces approximate routes instead of exact ones. While it is significantly faster than EPR-D, it requires more
space (since full routes are stored). It also has weaker privacy guarantees since routes between
distant areas tend to follow the same intermediate route as will be expanded upon in Sec. 5. Since
the database has to store complete routes,Íthe space complexity is larger than EPR-D’s being at
𝑂 ([N𝑝2 + N𝑐 ] · 𝑅𝐺∗,𝑚𝑎𝑥 ) where N𝑐 = 1/|𝑃 | · 𝑝 ∈𝑃 |𝐶𝑝 | is the average number of external connections
from each partition. The different stages have different time complexities, with the first stage having
𝑂 ([N𝑝2 + N𝑐 ] · [|𝑃 | + |𝐶 |𝑙𝑜𝑔|𝑃 |]) and the second stage having 𝑂 (2 · N𝑝2 + N𝑐 ). The combined timecomplexity is then 𝑂 ( [N𝑝2 + N𝑐 ] · [(|𝑃 | + |𝐶 |𝑙𝑜𝑔|𝑃 |) + 2)]) which is significantly less than that of
EPR-D since |𝑃 | << |𝑉 |. The complexity of APR-D is also summarized in Table 3.
5

PROPOSED PRIVACY METRICS

To evaluate the effectiveness of a privacy-preserving PIR-based RPS, objectively quantifiable privacy
metrics must first be established in the RPS context. Thus, the two models presented in this section
jointly characterize the privacy of the different kinds of information that can be leaked by an RPS
as described in Sec. 3.3.
Table 4. Summary of Symbols used in Sec. 5

5.1

SymbolDescriptionΩ (𝑠, 𝑑 )R𝐺 (𝑢, 𝑣)
𝑄 𝑠,𝑑𝑄∗Φ(𝑄 ∗ )𝑃𝑠,𝑑𝑘 (𝑄𝑠,𝑑 , 𝑄 ∗ )𝑉𝑋

Endpoint location privacy metricArbitrary routing mechanism operating on some graph 𝐺
Query sequence used to obtain a route from 𝑠 to 𝑑
An arbitrary query sequence for no specific route
Route privacy metric for some candidate query sequence 𝑄 ∗Partition sequence derived from some query sequence 𝑄 𝑠,𝑑Indicator function for checking if 𝑄∗ can replace 𝑄𝑠,𝑑 and vice versa
A subset of 𝑉 containing only the representative vertices

Endpoint Location Privacy Model

As mentioned in Sec. 3.1, the partition database is used to store the shortest paths for each partition,and is queried privately using PIR in our approach. The queried partitions are assumed to beknowable by adversaries, but strong privacy is still guaranteed for exact locations within eachpartition. Let R𝐺𝑃 (𝑠, 𝑑) be a routing mechanism which returns the approximate shortest path𝜌𝐺𝑃 (𝑠, 𝑑), and suppose that the origin location 𝑠 is replaced with a nearby location 𝑠 ′ . If 𝑠 ′ is stillin the same partition as 𝑠 (i.e., 𝑠 ′ ∈ 𝑉𝑝𝑠 ), then R𝐺𝑃 (𝑠 ′, 𝑑) = R𝐺𝑃 (𝑠, 𝑑). The same applies replacing 𝑑with any 𝑑 ′ ∈ 𝑉𝑝𝑑 . An adversary knowing only R𝐺𝑃 (𝑠, 𝑑) would be unable to distinguish 𝑠, 𝑑 fromall other possible 𝑠 ′, 𝑑 ′ as long as 𝑠 ′ ∈ 𝑉𝑝𝑠 and 𝑑 ′ ∈ 𝑉𝑝𝑑 . Thus, location privacy is guaranteed for 𝑠
and 𝑑 within 𝑝𝑠 and 𝑝𝑑 respectively.
The privacy for any 𝑠, 𝑑 pair is then proportional to the number of possible 𝑠 ′, 𝑑 ′ pairs that canbe drawn between 𝑉𝑝𝑠 and 𝑉𝑝𝑑 . This is designated as the endpoint location privacy metric:1
Ω(𝑠, 𝑑) = 1 −(5)|𝑉𝑝𝑠 | · |𝑉𝑝𝑑 |ACM Trans. Cyber-Phys. Syst., Vol. 6, No. 4, Article 111. Publication date: October 2023.

111:10

Tiausas, et al.

Fig. 2. Queried Partitions using Dijkstra’s algorithm to calculate two routes with the same origin but different
destinations (∼ 1 km away from each other). The numbers indicate how many queries were handled by eachpartition.

where 𝑉𝑝𝑠 and 𝑉𝑝𝑑 give the sets of all vertices in 𝑝𝑠 and 𝑝𝑑 , respectively. Note that while having
more vertices per partition (i.e. larger |𝑉𝑝𝑠 | and |𝑉𝑝𝑑 |) is advantageous for endpoint location privacy,
this also means higher computation overhead for PIR. Extensive preliminary experiments with the
PIR scheme used by our approach showed that the retrieval times scaled almost linearly with the1
database size at a rate of roughly 45000≈ 2.22 × 10−5 seconds per record. That is, a database with
|𝑉𝑝 | 2 ≈ 10000 routes was found to have an average retrieval time of ∼ 0.25 seconds, while anotherwith |𝑉𝑝 | 2 ≈ 100000 routes took ∼ 2 seconds.
5.2

Route Privacy Model

Endpoint location privacy assumes that a route’s origin and destination partition are already known,
and thus quantifies only the privacy of the exact origin and destination points. This section focuseson the privacy of the routes themselves. As with endpoint location privacy, it is assumed thatthe queried partitions are knowable by adversaries. It is also assumed that they have in-depth
knowledge about the algorithms used by the RPS.
Let 𝑄𝑠,𝑑 = {𝑞 0, . . . , 𝑞𝑛 } be the query sequence that a user must perform to obtain a route from 𝑠
to 𝑑. This sequence can be transformed into a partition sequence 𝑃𝑠,𝑑 = {𝑝 0, . . . , 𝑝𝑛 } (where 𝑝 0 = 𝑝𝑠
and 𝑝𝑛 = 𝑝𝑑 ) using a function 𝑓𝑞𝑝 : 𝑄 →− 𝑃 that maps every element of 𝑄 to its handling partitionin 𝑃. If the partitioning is hierarchical, then only the highest-level partitions are considered since
they already contain the shortest path data of lower-level partitions as stated in Sec. 3.1.
Note that partition sequences are not simply partitions along the final route. For instance, in thecase of Dijkstra’s algorithm, they can be thought of as the entire sequence of “scanned” vertices as
depicted in Fig. 2. It is therefore possible for several routes to share the same partition sequence(though unlikely in the case of Dijkstra’s). This is modeled as an indicator function that identifies
whether or not a candidate 𝑄 ∗ can replace 𝑄𝑠,𝑑 for calculating 𝑟𝐺𝑃 (𝑠, 𝑑) and vice versa:(
1 if 𝑓𝑞𝑝 (𝑄𝑠,𝑑 ) = 𝑓𝑞𝑝 (𝑄 ∗ )∗𝑘 (𝑄𝑠,𝑑 , 𝑄 ) =(6)0 otherwise
With this, the lower bound for the total number of distinct routes that share 𝑄 ∗ is:∑︁
𝑘 (𝑄𝑠 ′ ,𝑑 ′ , 𝑄 ∗ )𝑠 ′ ,𝑑 ′ ∈𝑉𝑋

ACM Trans. Cyber-Phys. Syst., Vol. 6, No. 4, Article 111. Publication date: October 2023.

(7)

HPRoP: Hierarchical Privacy-Preserving Route Planning for Smart Cities

111:11

Fig. 3. Road network graph of Osaka City, Japan hierarchically-partitioned using the Inertial Flow algorithm

where 𝑉𝑋 ⊆ 𝑉 contains only the representative vertices (e.g., 𝑥𝑢 , 𝑥 𝑣 ) associated with the partition
graph 𝐺 𝑃 as described in Sec. 3.1. This ensures that routes where 𝑝𝑠 ′ ≠ 𝑝𝑠 and 𝑝𝑑 ′ ≠ 𝑝𝑑 are countedwith equal importance as the route where 𝑝𝑠 ′ = 𝑝𝑠 ∧ 𝑝𝑑 ′ = 𝑝𝑑 — hence, the focus on distinct routes.
Finally, the route privacy can then be quantified for any 𝑄 ∗ as follows:Φ(𝑄 ∗ ) = 1 −Í1𝑘 (𝑄𝑠 ′ ,𝑑 ′ , 𝑄 ∗ )(8)𝑠 ′ ,𝑑 ′ ∈𝑉𝑋

6HIERARCHICAL PRIVACY-PRESERVING ROUTE PLANNING

Our proposed approach, Hierarchical Privacy-Preserving Route Planning (HPRoP), is built up fromseveral key design choices to meet particular requirements. That is, HPRoP should be able to:• REQ1: Compose feasible approximate shortest paths by carefully choosing its component
routes from the appropriate partitions,• REQ2: Privately retrieve component route information from said partitions with minimal
processing overhead,• REQ3: Produce an approximate shortest path with good optimal route approximation values(i.e., 𝛼 (𝑟𝐺∗ (𝑠, 𝑑)) → 1.0),• REQ4: Ensure a good level of privacy protection for the user’s exact origin and destination
points, and intermediate route,• REQ5: Reflect dynamic and up-to-date road conditions, and• REQ6: Scale reasonably well with changes in client demand and computational resource
availability over time and per area.
All these are brought together by a novel hierarchical route planning heuristic presented in thelatter half of this section, along with other improvements to privacy and routing.
6.1

Private Information Retrieval (PIR)

HPRoP uses PIR as its core route privacy-preservation mechanism. The choice of implementation
was the SealPIR [2] library configured to use Brakerski/Fan-Vercauteren (BFV) Homomorphic
Encryption (HE)[13] with a database upper bound of 𝑁 = 216, a plaintext modulus of 𝑙𝑜𝑔(𝑡) = 12,
and a dimensionality factor, 𝑑 = 2. This implementation was chosen specifically for its significantly
reduced processing and communication overhead compared to other HE-based ones, making it
ideal for an RPS. This along with the hierarchical route planning heuristic drastically reduces thenumber of queries and, in effect, the route completion time.
6.2

Inertial Flow Partitioning

Optimal route approximation and endpoint location privacy are highly-dependent on how theservice region is partitioned. Straightforward methods such as grid partitioning are simple but
ACM Trans. Cyber-Phys. Syst., Vol. 6, No. 4, Article 111. Publication date: October 2023.

111:12Tiausas, et al.

Fig. 4. Cloud-based Architecture (Left) vs Distributed/Edge-based Architecture (Right)

often result in disjoint partition subgraphs in the presence of natural barriers like rivers, etc. To
mitigate this, one way would be to ensure that each partition subgraph is a strongly-connectedcomponent, ensuring high internal connectivity and reachability. Examples of road network graphaware partitioning methods include PUNCH [12], Buffoon [32], and Inertial Flow [33].
Inertial Flow was chosen for HPRoP as it is a relatively simple algorithm based on maximum flowwhich results in balanced partitions and also preserves internal connectivity. A vertex thresholdof around 300 nodes per partition was chosen instead of an area-based threshold to guarantee an
Endpoint Location Privacy of Ω(𝑠, 𝑑) ≈ 99.998% (i.e., < 0.002% probability). Moreover, based on
preliminary experiments with SealPIR, a partition database with 3002 ≈ 90000 routes is expected
to have retrieval times between 1.5 − 2.5 seconds (1.75 seconds on average) which is viable whencombined with HPRoP’s reduced query counts. A queue is initialized by adding the entire road
network graph to it. A graph from this queue is then used as input to the Inertial Flow algorithm toproduce two balanced partition subgraphs. The simple iterative technique in [1] was used alongside
Inertial Flow to find and apply optimal cuts during this step. If any of the subgraphs do not yet
satisfy vertex threshold, they are simply added back to the queue. This entire procedure is thenrepeated until the queue is empty. Afterwards, every two consecutive cuts was then retroactively
denoted as a separate partition level as shown in Fig. 3, and the partitions under each are thentagged accordingly. Due to the vertex threshold, the highest level partition may vary greatly fromarea to area. Some routes therefore require more queries to complete over other routes, which
increases profiling risk. A partition level threshold ℓ𝑡ℎ𝑟𝑒𝑠ℎ𝑜𝑙𝑑 = 3 was therefore imposed such thathigher level ones were reassigned to ℓ = ℓ𝑡ℎ𝑟𝑒𝑠ℎ𝑜𝑙𝑑 .
6.3

Distributed Architecture

HPRoP leverages the hierarchically partitioned road network by delegating each partition to adifferent entity. In the cloud-based scenario, these entities would be server instances; while, inthe edge-based scenario, these would be edge-servers throughout the smart city. The edge-basedarchitecture presents several advantages. First, it allows PIR queries to be directed only to partitions
which have the information necessary to answer them, effectively distributing the computationalload of using PIR. Second, it allows the system to better scale based on the number of users,
availability of computing resources, etc. which can vary greatly at different times across different
parts of the city as shown in Fig. 4. Finally, it also makes the pre-computation of shortest paths toneighboring partitions more efficient since it can be done independently by every partition after an
initial exchange of road condition information with said neighbors. This is useful for reflecting
dynamic road conditions bound to some local area.

ACM Trans. Cyber-Phys. Syst., Vol. 6, No. 4, Article 111. Publication date: October 2023.

HPRoP: Hierarchical Privacy-Preserving Route Planning for Smart Cities

6.4

111:13

Heuristic Algorithm

HPRoP uses a simple heuristic algorithm to arrive at an approximate shortest path as follows:(1) Initialization: Find an initial basis route between the lowest level partitions containing sourceand destination, then move up one level.
(2) Subroute Connection: Connect the source and destination partitions at the current level to thebasis route using subroutes.
(3) Basis Route Merging: Merge the subroutes into the basis route.
(4) Repeat steps (2) to (3) until the highest partition level is reached
Algorithm 1: Hierarchical Route Planning Heuristic
Input: Source node 𝑠, Destination node 𝑑, Current level 𝑙𝑐
Output: The final route 𝑟 ∗1 begin2
𝑙𝑜 ← 𝐹𝑖𝑛𝑑𝐵𝑎𝑠𝑒𝐿𝑒𝑣𝑒𝑙 (𝑠, 𝑑 );
3
4
5
6
7
8

𝑟 ∗ ← 𝑅𝑒𝑡𝑟𝑖𝑒𝑣𝑒𝑃𝑎𝑡ℎ (𝑝𝑠𝑙𝑜 , 𝑝𝑑𝑙𝑜 , “from source”);
Initialize 𝑙𝑐 ← 𝑙𝑜 + 1;
while 𝑙𝑐 ≤ 𝑙𝑡ℎ𝑟𝑒𝑠ℎ𝑜𝑙𝑑 do
Initialize 𝑟𝑠𝑙𝑐 , 𝑟𝑑𝑙𝑐 ← [ ];if 𝑙𝑐 < (𝑙𝑡ℎ𝑟𝑒𝑠ℎ𝑜𝑙𝑑 − 1) then𝑟𝑠𝑙𝑐 ← 𝐺𝑒𝑡𝑆𝑢𝑏𝑟𝑜𝑢𝑡𝑒 (𝑠, 𝑙𝑐 , 𝑟 ∗ , “from source”);
𝑟𝑑𝑙𝑐 ← 𝐺𝑒𝑡𝑆𝑢𝑏𝑟𝑜𝑢𝑡𝑒 (𝑑, 𝑙𝑐 , 𝑟 ∗ , “from destination”);

9
10

else

11

𝑟𝑠𝑙𝑐 ← 𝐺𝑒𝑡𝐸𝑛𝑑𝑆𝑢𝑏𝑟𝑜𝑢𝑡𝑒 (𝑠, 𝑙𝑐 , 𝑟 ∗ , “from source”);

12

𝑟𝑑𝑙𝑐 ← 𝐺𝑒𝑡𝐸𝑛𝑑𝑆𝑢𝑏𝑟𝑜𝑢𝑡𝑒 (𝑑, 𝑙𝑐 , 𝑟 ∗ , “from destination”);

13
14
15

𝑟 ∗ ← 𝑀𝑒𝑟𝑔𝑒𝑅𝑜𝑢𝑡𝑒𝑠 (𝑟 ∗ , 𝑟𝑠𝑙𝑐 , 𝑟𝑑𝑙𝑐 );𝑙𝑐 ← 𝑙𝑐 + 1;
return 𝑟 ∗ ;Algo. 1 runs exclusively on the client-side, sending PIR queries to edge servers handling specificpartitions. Route information is obtained solely through these PIR queries, and, thus, no informationis leaked by the queries themselves. However, the number of queries, their timestamps, and thepartitions they were sent to are still assumed to be known to the adversary.
The algorithm starts with an Initialization step (lines 2-4 in Algo. 1) which finds an approximate
shortest path between the lowest level partitions containing 𝑠 and 𝑑 separately as shown in Fig. 5.
This level is denoted as the base level 𝑙𝑜 = arg min𝑙 (𝑝𝑠𝑙 ≠ 𝑝𝑑𝑙 ). For simplicity, this is just denoted
as 𝐹𝑖𝑛𝑑𝐵𝑎𝑠𝑒𝐿𝑒𝑣𝑒𝑙 (𝑠, 𝑑) in Algo. 1. The client then sends a PIR query to partition 𝑝𝑠𝑙𝑜 , retrieving aroute to partition 𝑝𝑑𝑙𝑜 . This corresponds to 𝑅𝑒𝑡𝑟𝑖𝑒𝑣𝑒𝑃𝑎𝑡ℎ(𝑝𝑢 , 𝑝 𝑣 , 𝔇) which retrieves the shortest
path between two partitions taking into account some direction flag 𝔇. This flag simply indicates
whether the path is being calculated from the source or the destination, which will be relevant later.
The retrieved route is then denoted as the initial basis route 𝑟 ∗ shown in Fig. 6. At the end of thisstep, the current level variable 𝑙𝑐 is also initialized (line 4).
The main loop starts from the Subroute Connection steps (lines 6-9 in Algo. 1). The algorithm for
Subroute Connection itself is described in Algo. 2. A subroute 𝑟 𝑥𝑙𝑐 is defined as a path that connects
a basis partition 𝑝𝑥𝑙𝑐 to the current basis route 𝑟 ∗ . The basis partition given by 𝑝𝑥𝑙𝑐 is always thesource or destination partition at level 𝑙𝑐 containing some vertex 𝑥, and is used to obtain the sourceor destination sub-partitions (depending on the direction 𝔇) at line 3 of Algo. 2. For instance,
ACM Trans. Cyber-Phys. Syst., Vol. 6, No. 4, Article 111. Publication date: October 2023.

111:14

Tiausas, et al.

Fig. 5. Initialization: Find a shortest path between
the lowest-level partitions containing 𝑠 (blue circle) and 𝑑 (green) separately.

Fig. 6. Initialization: Use discovered path as basis
route (purple line) for the next level

Fig. 7. Source Subroute Connection: Find andconnect source subroute (blue line) to basis route(purple line)

Fig. 8. Dest. Subroute Connection: Find and connect dest. subroute (green line) to basis route (purple line)

Fig. 9. Basis Route Merging: Merge routes anduse as new basis route (purple line)

ACM Trans. Cyber-Phys. Syst., Vol. 6, No. 4, Article 111. Publication date: October 2023.

HPRoP: Hierarchical Privacy-Preserving Route Planning for Smart Cities

111:15the source subroute is obtained by finding a sequence of shortest paths from 𝑝𝑠𝑙𝑐 that connects
to the basis route as shown in Fig. 7. This step also uses several important functions, such as:(1) 𝐹𝑖𝑛𝑑𝑅𝑜𝑢𝑡𝑒𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝑠 (𝑟 ∗, 𝑙) which gives the sequence of partitions at level 𝑙 along 𝑟 ∗ , and (2)𝐷𝑜𝑒𝑠𝑁𝑜𝑡𝐼𝑛𝑡𝑒𝑟𝑠𝑒𝑐𝑡 (𝑟 𝑥𝑙𝑐 , 𝑟 ∗ ) which is “True” if 𝑟 𝑥𝑙𝑐 and 𝑟 ∗ have no common vertices. Starting from 𝑝𝑥𝑙𝑐 ,it builds 𝑟 𝑥𝑙𝑐 by retrieving a path to nearby connected partitions (line 9) and then connecting themto the subroute (lines 10-13). Since 𝑟 𝑥𝑙𝑐 might not yet intersect 𝑟 ∗ during the initial iteration, this isrepeated with an updated reference partition (lines 14-15) until an intersection is found. Computing
the destination subroute follows the same steps but first has to reverse the aforementioned sequence(lines 5-7) so that the algorithm can begin from the last route partition. This step is shown in Fig. 8.
The Basis Route Merging step (line 13 in Algo. 1) is performed once the source and destination
subroutes are found. The basic idea is to find the “best” point at which the subroutes intersect withthe basis route and join them there. For the source subroute, the “best” point is as far as possible
from the start of the basis route; while for the destination subroute, this is as far as possible fromthe end of the basis route. This is illustrated in Fig. 9. This merged route is then used as the newbasis route. The current level 𝑙𝑐 is then updated (line 15), and the loop is restarted. The loop is
terminated once 𝑙𝑐 reaches 𝑙𝑡ℎ𝑟𝑒𝑠ℎ𝑜𝑙𝑑 .
The time complexity of this algorithm depends on the required number of PIR database lookups.
Finding the initial basis route and calculating the final routes at 𝑝𝑠 and 𝑝𝑑 always require a single
lookup each. Meanwhile, the number of lookups at each level depends on the maximum lengthof the shortest path in 𝐺 𝑃 at that level which is given by 𝑚𝑎𝑥 𝑝𝑢ℓ ,𝑝 𝑣ℓ ∈𝑃 ℓ |𝑟𝐺∗ ℓ (𝑝𝑢ℓ , 𝑝 𝑣ℓ )| where 𝐺 𝑃ℓ ⊂ 𝐺 𝑃
𝑃containing only that level’s partitions 𝑃 ℓ and connections 𝐶 ℓ . The average time complexity is then:
"
#!
∑︁
∑︁
2
ℓ
∗
ℓ
ℓ
𝑂 [N𝑝 +
N𝑐 ] · 3 +2 · max |𝑟𝐺 ℓ (𝑝𝑢 , 𝑝 𝑣 )|
(9)
ℓ ∈𝐿

ℓ ∈𝐿

𝑝𝑢ℓ ,𝑝 𝑣ℓ ∈𝑃 ℓ

𝑃

where N𝑐ℓ is the average number of connections from each partition at level ℓ. Since HPRoP
precomputes and stores shortest path data for multiple levels per partition, it is necessary to
Algorithm 2: Subroute Connection
Input: Basis node 𝑥, Current level 𝑙𝑐 , Basis route 𝑟 ∗ , Direction 𝔇
Output: Subroute at the current level 𝑟 𝑥𝑙𝑐
1 begin2
Initialize 𝑟 𝑥𝑙𝑐 ← [ ];6𝑝𝑐 ← 𝑝𝑥𝑙𝑐 ;// This retrieves either source or destination sub-partition depending on direction 𝔇
𝑅𝑃 𝑙𝑐 ← 𝐹𝑖𝑛𝑑𝑅𝑜𝑢𝑡𝑒𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝑠 (𝑟 ∗ , 𝑙𝑐 )if 𝔇 is “from destination” then𝑅𝑒𝑣𝑒𝑟𝑠𝑒 (𝑅𝑃 𝑙𝑐 );7𝑖 ← 0;

3
4
5

8
9
10
11
12
13
14
15
16

while 𝐷𝑜𝑒𝑠𝑁 𝑜𝑡𝐼𝑛𝑡𝑒𝑟𝑠𝑒𝑐𝑡 (𝑟 𝑥𝑙𝑐 , 𝑟 ∗ ) and 𝑖 < |𝑅𝑃 𝑙𝑐 | do𝑟 𝑝𝑎𝑟𝑡 ← 𝑅𝑒𝑡𝑟𝑖𝑒𝑣𝑒𝑃𝑎𝑡ℎ (𝑝𝑐 , 𝑅𝑃 𝑙𝑐 [𝑖 ], 𝔇);
if 𝔇 is “from source” then𝑟 𝑥𝑙𝑐 ← 𝑟 𝑥𝑙𝑐 + 𝑟 𝑝𝑎𝑟𝑡 ;else if 𝔇 is “from destination” then𝑟 𝑥𝑙𝑐 ← 𝑟 𝑝𝑎𝑟𝑡 + 𝑟 𝑥𝑙𝑐 ;𝑝𝑐 ← 𝑅𝑃 𝑙𝑐 [𝑖 ];𝑖 ← 𝑖 + 1;
return 𝑟 𝑥𝑙𝑐 ;ACM Trans. Cyber-Phys. Syst., Vol. 6, No. 4, Article 111. Publication date: October 2023.

111:16

Tiausas, et al.

account for N𝑐ℓ in HPRoP’s space complexity:∑︁𝑂 ( [N𝑝2 +N𝑐ℓ ] · 𝑅𝐺∗,𝑚𝑎𝑥 )

(10)

ℓ ∈𝐿

6.4.1 Route Privacy Mechanism. Route privacy as defined in Sec. 5.2 quantifies the privacy basedon how many other possible routes have a query sequence matching that of a given route, wheremore matches mean better privacy. That is, an adequate route privacy mechanism should: (1)maximize the matching of query sequences between all possible routes, and (2) minimize theinformation gain from the order of queries in the sequence itself. HPRoP already achieves thelatter via hierarchical execution which can somewhat obfuscate the actual query sequence, butdoes not necessarily strengthen the former. To address this, the algorithm is extended to pad thequery sequence with dummy queries. The basic idea is to query multiple other partitions insteadof just 𝑝𝑠 and 𝑝𝑑 to ensure that the actual origin and destination partitions are “hidden’ among
them. In theory, querying more partitions would mean better route privacy at the cost of longer
route completion times. Achieving full route privacy, however, would require querying all levelpartitions at every iteration of the algorithm at least once, which would require prohibitively
long route completion times. For example, a service region with a total of 463 partitions would
require roughly 810 seconds (13.5 minutes) on average to complete a single route. However, simply
querying a small random subset of the aforementioned partitions will not be enough to ensure acertain level of route privacy, since an adversary can simply use the hierarchy of partitions to checkfor inconsistencies in the set of queried partitions and easily identify the dummy ones. Instead, wechose to limit HPRoP to querying all other partitions under the same parent as the highest levelpartitions containing 𝑠 and 𝑑. This selection method is straightforward and ensures that none of
the queried partitions can easily be identified as dummy partitions. Additionally, this ensures thatroute privacy will be around Φ(𝑄 ∗ ) ≈ 1 − 1/𝑗𝑘 where 𝑗 and 𝑘 are the total number of partitions
under the same parent partitions as 𝑝𝑠 and 𝑝𝑑 , respectively.
This is implemented through the Subroute End Connection steps (lines 10-12 in Algo. 1), while theprocedure itself is presented in Algo. 3. Instead of stopping when the subroute and basis route firstintersect, this algorithm continues until all other partitions sharing the same parent 𝑝𝑥𝑙𝑐 −1 as thebasis partition have been queried. This is done by repeatedly drawing a partition 𝑝𝑠𝑢𝑏 from a queueof these same-parent sub-partitions 𝑆𝑃 𝑙𝑐 (line 10). If 𝑝𝑠𝑢𝑏 is the same as the current partition 𝑝𝑐 ,then a part of the subroute is retrieved as normal (lines 11-18). If it is a route partition, it is instead
pushed back to the subpartition queue (lines 19-22). If both prior conditions are not satisfied, thena dummy query is simply sent to 𝑝𝑠𝑢𝑏 (line 24). This ensures that important queries are mixed inwith dummy queries, making it more difficult to determine which ones are relevant.
6.5

Shortcut Connections

A simple strategy for improving algorithm performance is through pre-computing and storing
shortest path data to partitions beyond just the adjacent ones. This reduces the number of queries
to complete a route while also improving optimal route approximation for paths to further away
partitions. These paths to non-adjacent partitions were therefore denoted as Shortcut Connections,represented as additional edges in the partition graph.
These shortcut connections, however, also increase the pre-computation time for each partition
relative to how many of them need to be made. In addition, the extent of the road network graphneeded for pre-computation also increases based on the distance to the partitions being connected. It
is therefore more useful to limit the number of partitions to connect to and how far those partitions
can be. HPRoP considers two methods for determining shortcut connections: (1) the Same Parent
Shortcuts method, and (2) the 𝑁 -hop Neighbor Shortcuts method. Same Parent Shortcuts simply
ACM Trans. Cyber-Phys. Syst., Vol. 6, No. 4, Article 111. Publication date: October 2023.

HPRoP: Hierarchical Privacy-Preserving Route Planning for Smart Cities

111:17

Algorithm 3: Subroute End Connection with Dummies
Input: Source or Destination node 𝑥, Current level 𝑙𝑐 , Basis route 𝑟 ∗Output: Source or Destination subroute at the current level 𝑟 𝑥𝑙𝑐
1 begin2
Initialize 𝑟 𝑥𝑙𝑐 ← [ ];
3
4
5
6
7
8
9
10
11
12
13
14

𝑝𝑐 ← 𝑝𝑥𝑙𝑐 ;𝑅𝑃 𝑙𝑐 ← 𝐹𝑖𝑛𝑑𝑅𝑜𝑢𝑡𝑒𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝑠 (𝑟 ∗ , 𝑙𝑐 )if 𝔇 is “from destination” then𝑅𝑒𝑣𝑒𝑟𝑠𝑒 (𝑅𝑃 𝑙𝑐 );𝑆𝑃 𝑙𝑐 ← 𝐹𝑖𝑛𝑑𝑆𝑢𝑏𝑃𝑎𝑟𝑡𝑖𝑡𝑖𝑜𝑛𝑠 (𝑝𝑥𝑙𝑐 −1 ) as 𝑄𝑢𝑒𝑢𝑒𝑗 ← 0;
while |𝑆𝑃𝑥𝑙𝑐 −1 | > 0 do
𝑝𝑠𝑢𝑏 ← 𝑃𝑜𝑝 (𝑆𝑃 𝑙𝑐 );if 𝑝𝑠𝑢𝑏 = 𝑝𝑐 and 𝐷𝑜𝑒𝑠𝑁 𝑜𝑡𝐼𝑛𝑡𝑒𝑟𝑠𝑒𝑐𝑡 (𝑟𝑑𝑙𝑐 , 𝑟 ∗ ) then𝑟 𝑝𝑎𝑟𝑡 ← 𝑅𝑒𝑡𝑟𝑖𝑒𝑣𝑒𝑃𝑎𝑡ℎ (𝑝𝑠𝑢𝑏 , 𝑅𝑃 𝑙𝑐 [ 𝑗 ] );if 𝔇 is “from source” then𝑟 𝑥𝑙𝑐 ← 𝑟 𝑥𝑙𝑐 + 𝑟 𝑝𝑎𝑟𝑡 ;else if 𝔇 is “from destination” then𝑟 𝑥𝑙𝑐 ← 𝑟 𝑝𝑎𝑟𝑡 + 𝑟 𝑥𝑙𝑐 ;15
16

𝑝𝑐 ← 𝑅𝑃 𝑙𝑐 [ 𝑗 ];𝑗 ← 𝑗 + 1;

17
18

22

else if 𝑝𝑠𝑢𝑏 ∈ 𝑅𝑃 𝑙𝑐 and 𝐷𝑜𝑒𝑠𝑁 𝑜𝑡𝐼𝑛𝑡𝑒𝑟𝑠𝑒𝑐𝑡 (𝑟𝑑𝑙𝑐 , 𝑟 ∗ ) thenif 𝐼𝑛𝑑𝑒𝑥 (𝑝𝑠𝑢𝑏 , 𝑅𝑃 𝑙𝑐 ) > 𝑗 then
𝑃𝑢𝑠ℎ (𝑝𝑠𝑢𝑏 , 𝑆𝑃 𝑙𝑐 )𝑆ℎ𝑢 𝑓 𝑓 𝑙𝑒 (𝑆𝑃 𝑙𝑐 )

23

else

19
20
21

24
25

𝑆𝑒𝑛𝑑𝐷𝑢𝑚𝑚𝑦𝑄𝑢𝑒𝑟 𝑦 (𝑝𝑠𝑢𝑏 );return 𝑟 𝑥𝑙𝑐 ;Fig. 10. Demonstration of different shortcut connection strategies for improving the heuristic algorithm’s
performance against the base case (Left), where the dark red shape represents the starting partition, and thelighter red shapes represent the partitions it connects to. The black outline represents the starting partition’s
parent. (Middle) uses Same Parent Shortcuts, while (Right) uses 1-hop Neighbor Shortcuts.

ACM Trans. Cyber-Phys. Syst., Vol. 6, No. 4, Article 111. Publication date: October 2023.

111:18

Tiausas, et al.

connects each partition to all other partitions under the same parent partition as shown in Fig.
10 (Middle). 𝑁 -hop Neighbor Shortcuts pre-computes shortcuts to other 𝑁 -hop away partitions asshown in Fig. 10 (Right). Both would theoretically improve the optimal route approximation whencalculating subroutes between non-adjacent partitions and greatly reduce the possibility of broken
routes. HPRoP currently has no mechanisms to handle these other than deferring to the user’s
device to perform local route calculation to bridge the final gap. The usefulness of these methods
are shown through the results in Sec. 7.3.1.
7

EVALUATIONIn this section, the details of the evaluation framework for HPRoP are first presented prior toshowing the actual evaluation results and their subsequent analysis.
7.1

Environment

HPRoP was implemented in Python on a Jupyter notebook for ease of testing and visualization,with the notebook itself encapsulated in a Docker container for portability. The execution environment was a dedicated Linux server running Ubuntu 20.04.1 SMP equipped with a AMD Ryzen
Threadripper 3970X 32-Core processor and 256 GB RAM in total.
The service region was a rectangular geographical area of roughly 546 𝑘𝑚 2 (i.e. 26 km in width,
21 km in height) encompassing the entire road network of Osaka City, Japan and a portion of
the immediately outlying areas. Its road network graph consists of |𝑉 | = 99, 734 vertices and|𝐸| = 269, 614 edges. The region is hierarchically partitioned using the Inertial Flow algorithm asshown in Fig. 3 based on the parameters in Sec. 6.2.
7.2

Methodology

Evaluation was done through several metrics under the following categories: (1) Utility, (2) Privacy,and (3) Performance. The Utility category pertains to the usefulness of the service, with the Optimal
Route Approximation metric falling under this category. Since the base algorithm in Sec. 6.4 cannot
guarantee complete routes, Route Errors are also included here as a metric. Route errors are thendefined as the occurrence count of broken routes during testing. In turn, a broken route is defined asa route where a subroute connection cannot be established to the highest level partition containing
either 𝑠 or 𝑑, and thereby results in a route that cannot be completed by HPRoP’s algorithm. The
Privacy category is comprised of the Endpoint Location Privacy, and Route Privacy metrics describedin Sec. 5. The Performance category pertains to how well the service can deal with higher clientdemand, dynamic road conditions, etc. without service quality degradation. The Memory Usage,
Route Completion Time, and Pre-processing Time metrics fall under this category.
Evaluation was done by comparing HPRoP to the two baseline PIR-based approaches — EPR-D
and APR-D — previously presented in Sec. 4. For the Utility category, Privacy category, and RouteCompletion Time metrics, all three approaches were evaluated by calculating routes for randomlygenerated 𝑠, 𝑑 pairs until 4,000 successful routes have been completed. This termination threshold
was chosen to be sufficiently high enough to capture any route errors that might occur for HPRoP.
Note that both APR-D and EPR-D are guaranteed to produce complete routes so this metric is nolonger evaluated for them. Memory Usage was evaluated by calculating the projected size of the
per-partition databases for the highest-level partitions. Finally, Pre-processing Time was evaluatedby measuring the time to build each partition’s database.
7.3

Results

7.3.1 Effect of Shortcut Connections. The base performance of HPRoP under different shortcut
connection methods in Sec. 6.5 is first characterized with the goal of finding the method that
ACM Trans. Cyber-Phys. Syst., Vol. 6, No. 4, Article 111. Publication date: October 2023.

HPRoP: Hierarchical Privacy-Preserving Route Planning for Smart Cities

111:19Fig. 11. Distribution of Optimal Route Approximation
results for different Shortcut Connection methods

Fig. 12. Comparison of total Route Errors for different Shortcut Connection methods

Fig. 13. Distribution of Pre-Computation Times fordifferent Shortcut Connection methods

Fig. 14. Distribution of Optimal Route Approximation results using APR-D, EPR-D, and HPRoP

maximizes optimal route approximation while minimizing both route completion time and routeerrors. Fig. 11 shows the resulting distribution of optimal route approximation values for 4,000
successful test routes under different methods. Surprisingly, Same Parent Shortcuts have an almost
negligible effect on optimal route approximation, with N-hop Neighbor Shortcuts being a more
effective way to increase the said metric. However, Same Parent Shortcuts were highly effective inpreventing the occurrence of broken routes, reducing the error count to 21. Further investigationof these remaining errors showed that they were caused by choosing the same vertex as 𝑠 and 𝑑which results in failure as no routing can be done by the algorithm. In short, for all 4,000 test routes,
Same Parent Shortcuts seem to eliminate all occurrences of true broken routes — i.e., where thehighest level partitions containing 𝑠 or 𝑑 could not be reached. This also validates the hypothesisthat broken routes are caused by a lack of reachability at the final partition level that can containmore than 4 child partitions due to the deliberate choice to set ℓ𝑡ℎ𝑟𝑒𝑠ℎ𝑜𝑙𝑑 = 3 mentioned in Sec. 6.2.
Meanwhile, using 1-hop Neighbor Shortcuts drastically improves the results of the 75-th percentile
from 𝛼 (𝑟 ∗ ) ≈ 1.54 to 𝛼 (𝑟 ∗ ) ≈ 1.28, but anything beyond 2-hop Neighbor Shortcuts is seen to have
gradually diminishing returns. Finally, the overhead caused by the additional shortcut connections
is evaluated based on the pre-processing time metric in Sec. 7.2. Fig. 13 shows that both methods
increase the per partition pre-processing time to about ∼ 1.5 seconds once 1-Hop Neighbor Shortcuts
are introduced but stabilizes around this value even as the number of hops are further increased. In
ACM Trans. Cyber-Phys. Syst., Vol. 6, No. 4, Article 111. Publication date: October 2023.

111:20

Tiausas, et al.

Fig. 15. Distribution of Route Privacy Φ(𝑄 ∗ ) results for APR-D, EPR-D, and HPRoP

contrast, the effect of Same Parent Shortcuts on pre-processing time is minimal, amounting to anincrease of ∼ 0.1 seconds on average. Thus, both methods are equally viable in terms of this metric.
Table 5. Summary of Results for different Shortcut Connection Configurations

0-hop

Normal1-hop 2-hop

Min
25%
50%
75%
Max

1.0
1.160
1.314
1.590
16.256

1.0
1.062
1.141
1.287
5.210

1.0
1.017
1.079
1.202
5.371

1.0
1.003
1.052
1.156
5.371

Min
25%
50%
75%
Max

Per-Partition Routes Calculation Time (in seconds)
0.04
0.11
0.19
0.19
0.08
0.11
0.19
0.16
0.58
1.88
3.33
0.24
0.75
1.92
0.20
1.43
2.49
4.41
0.47
1.51
2.90
0.28
1.60
3.36
5.70
1.30
1.74
3.47
1.27
3.17
5.78
10.55
3.15
3.37
6.75

0.19
3.48
4.75
6.03
11.44

Total

231.0

Route Errors (per 4,000 successful routes)
52.0
30.0
24.0
21.0
21.0

21.0

3-hop

With Same Parent Shortcuts
0-hop 1-hop 2-hop 3-hop

Optimal Route Approximation
1.0
1.0
1.0
1.0
1.018 1.003
1.133
1.060
1.080 1.052
1.270
1.138
1.202 1.156
1.510
1.288
5.371 5.371 15.424 5.210

21.0

Table 5 summarizes the results discussed so far. Based on these, it was decided to use 2-hop
Neighbor Shortcuts with Same Parent Shortcuts as the representative configuration for HPRoP as it
offers good optimal route approximation and short pre-computation times with minimal errors.
7.3.2 Optimal Route Approximation. The performance of HPRoP, APR-D, and EPR-D in terms of
optimal route approximation is shown in Fig. 14. As expected, EPR-D achieves a constant optimalroute approximation value of 𝛼 (𝑟 ∗ ) = 1.0 since it always produces exact shortest paths. APR-D
produced routes with 𝛼 (𝑟 ∗ ) ≈ 1.44 for the 75-th percentile despite operating only over the partition
graph. HPRoP produced even better routes with 𝛼 (𝑟 ∗ ) ≈ 1.20 for the 75-th percentile, whereas
APR-D was only able to achieve this for the 25-th percentile of all results. Additionally, HPRoP
achieves much better worst-case routes than APR-D.
7.3.3 Endpoint Location Privacy. Endpoint Location Privacy Ω(𝑠, 𝑑) describes how well the exact𝑠, 𝑑 is kept private as described in Sec. 5.1. Since Inertial Flow partitioning was used, evaluation
results showed that all three approaches were able to achieve an average endpoint location privacy
ACM Trans. Cyber-Phys. Syst., Vol. 6, No. 4, Article 111. Publication date: October 2023.

HPRoP: Hierarchical Privacy-Preserving Route Planning for Smart Cities

111:21

Fig. 16. Visualization of Queried Partitions for APR-Dijkstra (Center), EPR-Dijkstra (Right) and HPRoP (Left)for the same route. Numbers indicate partitions that were queried multiple times.

of Ω(𝑠, 𝑑) = 0.999982. Thus, each route is indistinguishable from approximately 99% of all otherroutes between the same partitions, making all three approaches equally viable.
7.3.4 Route Privacy. Route Privacy Φ(𝑄 ∗ ) describes how well a route is kept private based on how
many other routes share a query sequence similar to its own as described in Sec. 5.2. To evaluate
this, a lookup table for the routes between each 𝑠, 𝑑 ∈ 𝑉𝑥 such that 𝑠 ≠ 𝑑 was done separately for
EPR-D, APR-D, and HPRoP to account for their unique querying behaviors as shown in Fig. 16.
Fig. 15 shows a comparison of the route privacy distributions across all three approaches. EPR-D
showed the worst route privacy, achieving Φ(𝑄 ∗ ) > 0 only for the 25-th percentile of all results.
APR-D performed only slightly better with Φ(𝑄 ∗ ) > 0 for about 50% of all results, while achievingΦ(𝑄 ∗ ) ≥ 0.5 for only 25% of them. This is expected since both have no inherent privacy mechanisms,
yet this does illustrate that APR-D is still better than EPR-D in terms of route privacy. HPRoP,
in contrast, has route privacy of Φ(𝑄 ∗ ) ≥ 0.80 for the 50-th percentile of all results, while alsoachieving Φ(𝑄 ∗ ) ≥ 0.50 for the 75-th percentile, surpassing both EPR-D and APR-D. However,further analysis of the routes showed that the worst-case route privacy (i.e. Φ(𝑄 ∗ ) = 0.0) still
happens for ∼ 12.2% of all test routes. This suggests that HPRoP does not fully guarantee routeprivacy for all cases although this can be increased further by adding more dummy queries.
Additionally, the relationship between optimal route approximation 𝛼 (𝑟 ∗ ) and route privacy
metric Φ(𝑄 ∗ ) was also analyzed for HPRoP. This was done to determine whether some tradeoff exists between the two metrics. The results in Fig. 17 show that majority of the routes have𝛼 (𝑟𝑠,𝑑 ) < 1.2 across widely-varying levels of route privacy. This suggests that the two metrics havelittle effect on one another, and performing a simple Pearson correlation confirms that there is only
a weak positive correlation (𝜌 ≈ 0.104) between the two.
7.3.5 Route Completion Time. Obtaining a route using any of the three algorithms (APR-D, EPR-D,and HPRoP) requires the client to make multiple PIR queries to the RPS. Thus, route completiontime is highly dependent on how many such queries need to be made, and is equivalent to thetotal processing overhead for an RPS. In this work, it is calculated based on projections derived
from the preliminary experiments on SealPIR database retrieval times mentioned at the end of
1Sec. 5.1. The empirically derived value of roughly 45000≈ 2.22 × 10−5 seconds per record is thenused to calculate the route completion times which are shown in Fig. 19. Note that we opted to use
projections here instead of simulating the actual results as the latter would take a prohibitively longtime to conclude in the case of EPR-D (and, to a lesser extent, APR-D). For instance, APR-D requires∼ 214 queries on average which is expected to take 5.55 minutes (333.26 seconds) per route. EPR-D
is even worse, requiring ∼ 4, 958 queries on average which would take at least 2.15 hours (7,731.47
ACM Trans. Cyber-Phys. Syst., Vol. 6, No. 4, Article 111. Publication date: October 2023.

111:22

Tiausas, et al.

Fig. 17. Distribution of Optimal Route Approximation and Route Privacy results using HPRoP for 4,000 testroutes. Note that both axes were reoriented to show the best results on the lower left.

Fig. 18. Distribution of the required number ofqueries for route completion

Fig. 19. Distribution of total PIR retrieval times inseconds

seconds) just to complete a single route. Both are clearly impractical from the perspective of any
modern RPS. This is in contrast to HPRoP which requires significantly less queries on average (at∼ 25 queries) and takes only 23.55 seconds per route. This is because HPRoP’s algorithm bypasses
the need to explore large sections of the partition and road network graph as it already starts witha very coarse route between the origin and destination partitions at the lowest level to guide its
route search. APR-D and EPR-D, in contrast, explore outwards from the origin, checking every
unexplored partition or vertex on the way as per Dijkstra’s algorithm.
7.3.6 Memory Usage. Memory usage depends on the size of the route databases maintained byeach partition, which is very important in a distributed environment with resource-constrained
devices. Fig. 20 shows the distribution of per partition memory usage across the three approaches.
APR-D and HPRoP calculate and store a similar number of routes, thus requiring an allocation ofaround 20-160 MB per partition. EPR-D has a significantly smaller memory footprint at around0.5-4 MB per partition because it essentially stores a next-hop matrix instead. In practice, however,
the memory usage of all three approaches are well within the capabilities of standard edge servers.
7.3.7 Pre-processing Time. The pre-processing time metric is total time needed to build eachpartition’s database during the pre-processing phase, which determines how often it can be updated
ACM Trans. Cyber-Phys. Syst., Vol. 6, No. 4, Article 111. Publication date: October 2023.

HPRoP: Hierarchical Privacy-Preserving Route Planning for Smart Cities

Fig. 20. Distribution of Per-Partition Memory Usage(in MB) for the different approaches

111:23Fig. 21. Distribution of Per-Partition Pre-processing
Time results (in seconds) for the different approaches

during operation. As shown in Fig. 21, EPR-D require less than ≤ 0.5 seconds per partition on
average since it only needs to calculate the routes inside each partition, while APR-D requires ≤ 1.5
seconds since it also needs to calculate routes to immediately neighboring partitions in addition.
Meanwhile, HPRoP needs to calculate routes inside each partition, routes to neighboring partitions,and routes to other partitions under the same parent. This results in slightly longer pre-processing
times at 1-5 seconds per partition. Regardless, the pre-processing time for all three approaches areclearly fast enough to accommodate frequent updates even in under dynamic road conditions.
8

CONCLUSION

In this work, the Hierarchical Privacy-Preserving Route Planning (HPRoP) approach was proposed
which combines Inertial Flow partitioning, Private Information Retrieval (PIR), and Edge Computing
techniques along with a novel hierarchical route planning heuristic algorithm to produce routes
that can adequately approximate the actual shortest paths while also providing endpoint location
privacy and route privacy. HPRoP reliably produced routes with an optimal route approximationof 𝛼 (𝑟 ∗ ) ≤ 1.2, while also achieving near-optimal endpoint location privacy at Ω(𝑠, 𝑑) ≈ 1.0 andgood route privacy at Φ(𝑄 ∗ ) ≥ 0.5. In terms of performance, HPRoP has a route completion time ofaround 23.55 seconds on average which is reasonable for a privacy-preserving RPS. It’s viability for
deployment in a distributed/edge-based smart city context were also shown through its relatively
small memory footprint (20-160 MB for each partition’s database), and short pre-processing times(2-5 seconds per partition) which are well within the capabilities of conventional edge servers.
In addition, although most modern route planning algorithms can also use PIR, we didn’t use
them as the basis of our approach due to several reasons. For instance, bounded-hop techniquessuch as two-hop labelling [9] are the fastest known class of routing algorithms but they requirecomputing and storing prohibitively large indices for city-sized road networks which becomes evenworse in combination with PIR. Separator-based techniques such as Customizable Route Planning(CRP) [11] and goal-directed techniques such as ALT (based on A*) [18] and Arc Flags [20] have very
long precomputation times, making them infeasible to use with dynamic road networks havingedge weights that need to be updated frequently. The hierarchical technique called Contraction
Hierarchies (CH) [16] has none of the aforementioned problems but still presents a potential routeprivacy risk since it must explicitly query the partitions along the actual shortest path multiple
times to obtain the final path. Nevertheless, it is a good routing algorithm to consider for future
PIR-based RPS work.
Aside from the experiments presented in Sec. 7, we also conducted tests on how well HPRoP
generalizes to other road networks, but the results are omitted for conciseness. In particular, it wastested on three other large cities — New York, Shanghai, and Tokyo — by obtaining 4,000 test routes
ACM Trans. Cyber-Phys. Syst., Vol. 6, No. 4, Article 111. Publication date: October 2023.

111:24

Tiausas, et al.

and examining the optimal route approximation distribution. For 75% of all routes, the optimalroute approximation was at 𝛼 (𝑟 ∗ ) ≤ 1.20 for New York, 𝛼 (𝑟 ∗ ) ≤ 1.23 for Shanghai, and 𝛼 (𝑟 ∗ ) ≤ 1.24
for Tokyo. This indicates that HPRoP generalizes somewhat, but further research is still required.
In the future, we also plan to refine HPRoP’s route planning algorithm to further improve optimalroute approximation and reduce route completion times by exploring more efficient data structures
for route information, and improve route privacy by considering out-of-order query execution.
ACKNOWLEDGMENTS
This work was supported by R&D for Trustworthy Networking for Smart and Connected Communities, Commissioned Research of National Institute of Information and Communications Technology(NICT), JSPS KAKENHI Grant Numbers JP21H03431 and JP19H05665, and National Science Foundation through award numbers 1647015, 1818901, CNS-2030611, CNS-1818942, SaTC-2030624,
SaTC-2030611.
REFERENCES[1] 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 2021. 3918–3929.
[2] Sebastian Angel, Hao Chen, Kim Laine, and Srinath Setty. 2018. PIR with compressed queries and amortized query
processing. In 2018 IEEE symposium on security and privacy (SP). IEEE, 962–979.
[3] Ugur Ilker Atmaca, Carsten Maple, Gregory Epiphaniou, and Mehrdad Dianati. 2021. A privacy-preserving route
planning scheme for the Internet of Vehicles. Ad Hoc Networks 123 (2021), 102680.
[4] Barnana Baruah and Subhasish Dhal. 2022. A security and privacy preserved intelligent vehicle navigation system.
IEEE Transactions on Dependable and Secure Computing (2022).
[5] Amos Beimel, Yuval Ishai, and Tal Malkin. 2000. Reducing the servers computation in private information retrieval:
PIR with preprocessing. In Advances in Cryptology—CRYPTO 2000: 20th Annual International Cryptology Conference
Santa Barbara, California, USA, August 20–24, 2000 Proceedings 20. Springer, 55–73.
[6] Melissa Chase and Seny Kamara. 2010. Structured encryption and controlled disclosure. In Advances in CryptologyASIACRYPT 2010: 16th International Conference on the Theory and Application of Cryptology and Information Security,
Singapore, December 5-9, 2010. Proceedings 16. Springer, 577–594.
[7] Benny Chor and Niv Gilboa. 1997. Computationally private information retrieval. In Proceedings of the twenty-ninth
annual ACM symposium on Theory of computing. 304–313.
[8] Yu-Li Chou, H Edwin Romeijn, and Robert L Smith. 1998. Approximating shortest paths in large-scale networks with
an application to intelligent transportation systems. INFORMS journal on Computing 10, 2 (1998), 163–179.
[9] Edith Cohen, Eran Halperin, Haim Kaplan, and Uri Zwick. 2003. Reachability and distance queries via 2-hop labels.
SIAM J. Comput. 32, 5 (2003), 1338–1355.
[10] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. 2009. Introduction to algorithms. MITpress.
[11] Daniel Delling, Andrew V Goldberg, Thomas Pajor, and Renato F Werneck. 2017. Customizable route planning in road
networks. Transportation Science 51, 2 (2017), 566–591.
[12] Daniel Delling, Andrew V Goldberg, Ilya Razenshteyn, and Renato F Werneck. 2011. Graph partitioning with natural
cuts. In 2011 IEEE International Parallel & Distributed Processing Symposium. IEEE, 1135–1146.
[13] Junfeng Fan and Frederik Vercauteren. 2012. Somewhat practical fully homomorphic encryption. Cryptology ePrint
Archive (2012). https://eprint.iacr.org/2012/144[14] Farhad Farokhi, Iman Shames, and Karl H Johansson. 2020. Private routing and ride-sharing using homomorphic
encryption. IET Cyber-Physical Systems: Theory & Applications 5, 4 (2020), 311–320.
[15] Sébastien Gambs, Marc-Olivier Killijian, and Miguel Núñez del Prado Cortez. 2010. Show me how you move and I willtell you who you are. In Proceedings of the 3rd ACM SIGSPATIAL International Workshop on Security and Privacy in GIS
and LBS. 34–41.
[16] Robert Geisberger, Peter Sanders, Dominik Schultes, and Christian Vetter. 2012. Exact routing in large road networks
using contraction hierarchies. Transportation Science 46, 3 (2012), 388–404.
[17] Esha Ghosh, Seny Kamara, and Roberto Tamassia. 2021. Efficient graph encryption scheme for shortest path queries.
In Proceedings of the 2021 ACM Asia Conference on Computer and Communications Security. 516–525.
[18] Andrew V Goldberg and Chris Harrelson. 2005. Computing the shortest path: A search meets graph theory.. In SODA,
Vol. 5. Citeseer, 156–165.
ACM Trans. Cyber-Phys. Syst., Vol. 6, No. 4, Article 111. Publication date: October 2023.

HPRoP: Hierarchical Privacy-Preserving Route Planning for Smart Cities

111:25[19] 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).
[20] Moritz Hilger, Ekkehard Köhler, Rolf H Möhring, and Heiko Schilling. 2009. Fast point-to-point shortest pathcomputations with arc-flags. The Shortest Path Problem: Ninth DIMACS Implementation Challenge 74 (2009), 41–72.
[21] 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
VNIS’94-1994 Vehicle Navigation and Information Systems Conference. IEEE, 291–296.
[22] George Rosario Jagadeesh, Thambipillai Srikanthan, and KH Quek. 2002. Heuristic techniques for accelerating
hierarchical routing on road networks. IEEE Transactions on intelligent transportation systems 3, 4 (2002), 301–309.
[23] Sungwon Jung and Sakti Pramanik. 2002. An efficient path computation model for hierarchically structured topographical road maps. IEEE Transactions on Knowledge and Data Engineering 14, 5 (2002), 1029–1046.
[24] Meng Li, Yifei Chen, Shuli Zheng, Donghui Hu, Chhagan Lal, and Mauro Conti. 2020. Privacy-preserving navigation
supporting similar queries in vehicular networks. IEEE Transactions on Dependable and Secure Computing 19, 2 (2020),
1133–1148.
[25] Yangfan Liang, Yining Liu, and Brij B Gupta. 2022. PPRP: preserving-privacy route planning scheme in VANETs. ACM
Transactions on Internet Technology 22, 4 (2022), 1–18.
[26] Chang Liu, Liehuang Zhu, Xiangjian He, and Jinjun Chen. 2018. Enabling privacy-preserving shortest distance queries
on encrypted graph data. IEEE Transactions on Dependable and Secure Computing 18, 1 (2018), 192–204.
[27] Samir Jordan Menon and David J Wu. 2022. Spiral: Fast, high-rate single-server PIR via FHE composition. In 2022 IEEE
Symposium on Security and Privacy (SP). IEEE, 930–947.
[28] Kyriakos Mouratidis. 2013. Strong location privacy: A case study on shortest path queries. In 2013 IEEE 29th International
Conference on Data Engineering Workshops (ICDEW). IEEE, 136–143.
[29] Muhammad Haris Mughees, Hao Chen, and Ling Ren. 2021. OnionPIR: Response efficient single-server PIR. In
Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. 2292–2306.
[30] Vincent Primault, Antoine Boutet, Sonia Ben Mokhtar, and Lionel Brunie. 2018. The long road to computational
location privacy: A survey. IEEE Communications Surveys & Tutorials 21, 3 (2018), 2772–2793.
[31] Michael O Rabin. 2005. How to exchange secrets with oblivious transfer. Cryptology ePrint Archive (2005).
[32] Peter Sanders and Christian Schulz. 2012. Distributed evolutionary graph partitioning. In 2012 Proceedings of the
fourteenth workshop on algorithm engineering and experiments (ALENEX). SIAM, 16–29.
[33] Aaron Schild and Christian Sommer. 2015. On balanced separators in road networks. In International Symposium on
Experimental Algorithms. Springer, 286–297.
[34] Christian Sommer. 2016. All-pairs approximate shortest paths and distance oracle preprocessing. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer
Informatik.
[35] David J Wu, Joe Zimmerman, Jérémy Planul, and John C Mitchell. 2016. Privacy-preserving shortest path computation.
arXiv preprint arXiv:1601.02281 (2016).
[36] Andrew Chi-Chih Yao. 1986. How to generate and exchange secrets. In 27th annual symposium on foundations ofcomputer science (Sfcs 1986). IEEE, 162–167.
[37] Can Zhang, Liehuang Zhu, Chang Xu, Kashif Sharif, Chuan Zhang, and Ximeng Liu. 2020. PGAS: Privacy-preserving
graph encryption for accurate constrained shortest distance queries. Information Sciences 506 (2020), 325–345.
[38] Lei Zhang, Jing Li, Songtao Yang, and Bin Wang. 2017. Privacy preserving in cloud environment for obstructed shortest
path query. Wireless Personal Communications 96, 2 (2017), 2305–2322.
[39] 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
Transactions on Mobile Computing (2021).

Received XX January XXXX; revised XX XXXX XXXX; accepted XX XXXX XXXXACM Trans. Cyber-Phys. Syst., Vol. 6, No. 4, Article 111. Publication date: October 2023.