Location-of-interest vs. Current-location Privacy in Multi-hop Communication

Location-of-interest vs. Current-location Privacy in Multi-hop Communication RYAN VOGT, IOANIS NIKOLAIDIS, and MARIO A. NASCIMENTO, University of Alberta, Canada Consider a standard multi-hop wireless radio network in which nodes relay messages for one another. While the contents of messages may be sensitive and thus encrypted, the very fact that two radios communicated can leak sensitive information about both the physical location of the origin and the physical location of the destination. We investigate the trade-off between protecting the privacy of a user’s current location and the privacy of their location of interest, and how the user should choose dummy destinations to obfuscate their queries.

arXiv:2610.29772v1 [cs.CR] 21 Oct 2026

CCS Concepts: • Security and privacy → Privacy protections; Pseudonymity, anonymity and untraceability; Mobile and wireless security; Privacy-preserving protocols; • Networks → Network privacy and anonymity. Additional Key Words and Phrases: wireless networks, multi-hop routing, eavesdropping attacks, node mobility

1

Introduction

We consider the problem of location privacy in multi-hop wireless communication. In multi-hop wireless communication, a transmission originates at a node, is forwarded by some number of intermediate nodes (the relays) and is received by a destination node. Such networks form the basis of many tactical radio systems used by ground forces, where individual radios relay traffic for one another over ranges that exceed direct line-of-sight or single-hop connectivity. In these environments, the mere fact that two radios exchanged traffic can reveal the physical locations of both the originator and the destination, even when message payloads are protected by strong encryption. Our basic assumption is that: the sequence of relayed transmissions of a message, from origin to destination, reveals a purposeful interaction between the two endpoints; that interaction maps onto the real world, and reveals a purposeful interaction between the physical locations of the two endpoints; and, the two locations and the fact that they communicated is considered sensitive information. This assumption is warranted for environments in which an adversary can intercept wireless transmissions at multiple locations (including, in the extreme, across the entire deployment). The eavesdropping adversary is defined more precisely in Section 3. The key observation is that the eavesdropping scenario remains applicable under any link-level or end-to-end encryption that could be applied to the messages. The location of the origin and the location of the destination can be inferred from the pattern of relays, independent of encryption. We refer to messages introduced by an originator as queries, to capture the fact that each message results in a reply from the destination back to the origin. This model abstracts a broad category of tactical interactions, ranging from request/response exchanges for situational data or fire-support requests, to simple acknowledged command traffic. The problem that we study is the privacy of the two locations in question for the user: the user’s current location (the physical location of the origin) and their location of interest (the physical location, or approximate area, of the destination). We emphasize that the problem studied is not the privacy of the contents of the query and the reply, but instead the privacy of the physical locations of the endpoints. Our contribution is a method inspired by 𝑘-anonymity [34] that can be used to obfuscate the user’s location of interest: the user issues not one query to their location of interest, but rather 𝑘 queries to a diverse set of locations. The trade-off to this approach, aside from the energy and bandwidth cost of the additional 𝑘 − 1 queries, is that the additional traffic originating from the user’s current location facilitates an eavesdropping adversary determining that Authors’ Contact Information: Ryan Vogt, rvogt@ualberta.ca; Ioanis Nikolaidis, nikolaidis@ualberta.ca; Mario A. Nascimento, mario.nascimento@ ualberta.ca, University of Alberta, Department of Computing Science, Edmonton, Alberta, Canada.

1

2

Ryan Vogt, Ioanis Nikolaidis, and Mario A. Nascimento

location. Our contribution is the study of the trade-off between protecting the privacy of the user’s current location and the privacy of their location of interest, and how the user should choose the 𝑘 − 1 dummy destinations to obfuscate the real physical location of interest. It is important to note that in our scenario, the user trusts their own radio. However, the user does not trust the network, as there may be compromised radios. Additionally, our approach does not require that intermediate radios run any specialized software or privacy protocols. The multiple queries are initiated solely from the user’s radio. In that regard, it is fundamentally different from onion-routing approaches such as Tor [8]. Onion routing is expensive in computational and energy cost on resource-constrained tactical radios, and critically requires a network specifically designed to support it. Our scheme works on any multi-hop radio network that can already forward ordinary messages. We begin in Section 2 by discussing related work. We present our adversary model and assumptions in more detail in Section 3. In Section 4, we present formal metrics for measuring the privacy of each of: the user’s current location, their location of interest, and (more broadly) their area of interest. We then discuss how a user should choose their 𝑘 − 1 dummy locations of interest to query in Section 5, followed by a discussion of the related “partition” and “partitioning” problems in Section 6. We show the results of our 𝑘-query scheme in a featureless, uniform environment in Section 7, before adding mobility data drawn from an urban mobility simulator in Section 8. In Section 9 we conclude and discuss future work. 2

Related Work

The relation between privacy and mobility in multi-hop wireless networks has been studied for some time. The literature is spread over a number of application domains, sometimes published as related to Mobile Ad-Hoc Networks (MANETs), or specific Wireless Sensor Networks (WSNs), or in more general settings. For example, Hong et al. [16] examined how anonymous communication in MANETs is affected by node movement, and Andersson et al. [1] outlined general requirements for privacy in MANETs. Gruteser and Grunwald [13] studied spatial cloaking so that users remain anonymous when accessing location-based services, while Gedik and Liu [10] examined how a 𝑘-anonymity approach can be realized for location-based services. Mobility patterns extracted from cell-phone records have also been shown to identify individuals [39, 43]. The impact of compromised nodes on privacy has been investigated as well, for example by Pinto et al. [28] which introduced the idea of routing around known compromised nodes to preserve privacy. A significant body of work on source-location privacy in WSNs focuses on modifying the network itself. Misra and Xue [24] show how clusters of nodes can generate and share pseudonyms when communicating with a sink. Their idea was extended by Ouyang et al. [26] to handle compromised shared keys. These schemes, however, address only node-to-sink traffic and are not applicable when nodes must communicate with one another to route user queries. Ozturk et al. [27] and Kamat et al. [20] introduced phantom routing, in which each epoch’s data first follows a random directed walk away from the source before being forwarded to the sink. A similar approach is that of Yang et al. [41] but under a global eavesdropper. A related line of work examines an adversary that moves toward the receiver of sensor traffic [18]. These approaches assume a mobile adversary that physically tracks a continuous stream of packets, and they require changes to the routing protocol. Subsequent evaluations have shown that phantom routing’s protection can degrade substantially under realistic network sizes and configurations [14]. Client-side dummy generation has long been used to achieve 𝑘-anonymity for location-based services without a trusted third party. Kido et al. [22] introduced the idea of generating 𝑘 − 1 dummy locations at the client so that a server cannot distinguish the real location. Later work refined dummy selection to improve entropy and geographic

Location-of-interest vs. Current-location Privacy in Multi-hop Communication

3

dispersion [25, 40]. These techniques, however, assume a central server that receives the set of locations – they do not address the path-consistency attacks that arise when the same queries must be routed across a multi-hop radio network under partial observation by an eavesdropper or compromised nodes. Even protocols explicitly designed for anonymity remain vulnerable to traffic analysis. Liu et al. [23] demonstrated that a passive global adversary can recover end-to-end flows and paths in anonymous MANETs by correlating inter-arrival times. Stronger anonymity mechanisms for MANETs, such as the ALARM framework [7], rely on heavy cryptographic primitives and protocol changes that are costly for resource-constrained tactical radios. Onion-routing approaches [8, 11] similarly require a network specifically designed to support them and incur substantial computational and energy overhead on intermediate nodes. The largest difference between these existing lines of work and our approach is that we focus on an environment in which the user trusts their own radio but does not trust the network (compromised radios or eavesdroppers may be present). The multiple queries are initiated solely from the user’s radio, without specialized software or privacy protocol required at intermediate nodes. Consequently the scheme works on any multi-hop radio network that can already forward ordinary messages. This source-only design avoids the fragility of network-level routing modifications while still accounting for the path information an eavesdropper or compromised nodes can observe.

3

Adversary Model and Assumptions

We consider an adversary who can compromise individual nodes in a multi-hop wireless network. There are no physical or topological restrictions on which nodes the adversary may compromise, hence, any subset of the nodes may be under adversarial control. The adversary is incorporeal in the sense that it does not need to move through the deployment. Hence, once a node is compromised, the adversary instantly obtains all information known to that node. Specifically, a compromised node yields to the adversary any cryptographic keys it holds and the full contents of every message it routes or overhears (whether or not those messages are encrypted under keys the adversary has obtained). Because the wireless medium is shared, a compromised node may also observe transmissions from honest nodes within its communication range. Interference or collisions, however, may cause a transmission to be missed, so the absence of a received message is not reliable evidence that a nearby node was uninvolved. Consequently, the adversary treats only the set of compromised nodes that did not participate in a given query as nodes that are known not to have routed that query. When a user issues 𝑘 queries, we assume the adversary knows the value of 𝑘. This holds even if the adversary does not overhear every query. This is realistic because the entropy of a user-chosen 𝑘 is small relative to the size of the network – an adversary that observes only a subset of the queries can still bound the number of missing queries tightly. For the purpose of analysis and simulation we adopt two simplifying assumptions about the user’s local link. First, we treat the user as interacting directly with the network node 𝐶 that is closest to the user’s physical location. In practice the user would employ a handheld radio that communicates with 𝐶. The additional 2𝑘 transmissions on that last hop (the 𝑘 queries outbound and the 𝑘 replies inbound) do not alter the asymptotic privacy metrics and would only add unnecessary complexity. Second, we assume that the link between the user’s radio and 𝐶 uses sufficiently low power that it is not overheard by any other node unless 𝐶 itself is compromised. Both assumptions are standard in the source-location privacy literature and isolate the privacy effects that arise from multi-hop routing inside the network. Under these conditions the adversary’s goal is to infer the user’s current location 𝐶 and real location of interest 𝐿 from the partial route information obtained from compromised nodes and from overheard transmissions. The precise

4

Ryan Vogt, Ioanis Nikolaidis, and Mario A. Nascimento

definitions of current-location and location-of-interest privacy, and the algorithmic approach an adversary can take to attack them, are presented in the next section.

4

Privacy Metrics

We begin by defining our notation. The network consists of a set N of nodes, where |N | = 𝑛. The user will issue 𝑘 queries, 𝑄𝑖 , each directed to a location 𝐿𝑖 , where L = {𝐿1, 𝐿2, . . . , 𝐿𝑘 } ⊆ N . One node, 𝐿 ∈ L, is the user’s real location of interest, and the remaining 𝑘 − 1 nodes are dummy locations of interest. However, some of the nodes in the network may be compromised by the adversary, and those nodes are able to overhear communication on the shared wireless medium. Formally, the adversary attempts to decide on the current location (CL) and location of interest (LOI) of the user using the information overheard. To study how well this 𝑘-anonymity scheme preserves the privacy of the user’s LOI and CL, we require formal methods to measure the privacy levels that result from any given set of 𝑘 queries. In the following section, we define the metrics used to determine how well the user’s CL-privacy and LOI-privacy are protected. We follow that up with a discussion of the closely related concept of the privacy of the user’s area of interest (AOI) in Section 4.2.

4.1

Privacy of the Current Location and Location of Interest How much information a user’s queries leak about the user’s current location (CL) and location of interest (LOI) depends on how much information the adversary is able to overhear during the relaying of the queries. To determine the CLprivacy and LOI-privacy that result from a set of queries, we will simulate the user issuing queries while malicious nodes attempt to ascertain the origin and real destination of those queries. This section demonstrates how an adversary could use the information captured to narrow down the possible locations where the user could be. Central to the technique of narrowing down possible loca-

Fig. 1. The possible routes from the westernmost central node to the easternmost central node if fixed shortest-path routing is used (solid lines) or if random shortest-path routing is used (solid and dashed lines).

tions is the concept of a possible route. In the network, which we assume to be connected, there will be a routing algorithm capable of routing messages from any source node to any destination node. Consider a route R = (𝑁 1, 𝑁 2, . . . , 𝑁𝑙 ),

which is a sequence of 𝑙 nodes. R is a possible route from 𝑁 1 to 𝑁𝑙 if it is possible that the routing algorithm used in the network could have routed a message from 𝑁 1 to 𝑁𝑙 along the path 𝑁 1, 𝑁 2, . . . , 𝑁𝑙 . We will consider two routing algorithms: fixed shortest-path routing and random shortest-path routing. Both guarantee that any message from 𝑁 1 to 𝑁𝑙 will arrive in the fewest possible hops. In random shortest-path routing, each node maintains a table indexed by the destination of a message, containing all possible next hops that the message could take to arrive in the fewest hops. When a message arrives at a node 𝑁𝑖 destined for node 𝑁𝑙 , 𝑁𝑖 will look into its table at index 𝑁𝑙 , and randomly choose one of the entries as the next hop. In fixed shortest-path routing, each node stores only a single next-hop choice for each possible destination. There is exactly one possible route from 𝑁 1 to 𝑁𝑙 when fixed shortest-path routing is used, but there can be many possible routes between 𝑁 1 and 𝑁𝑙 with random shortest-path

Location-of-interest vs. Current-location Privacy in Multi-hop Communication

𝐶

The current location (CL) of the user, 𝐶 ∈ N

𝐶∗

The adversary’s final guess as to the current location of the user

C

The set of possible current locations of the user, as determined by the adversary

𝑘

The total number of queries sent by the user, where 𝑘 − 1 are to dummy locations of interest and one is to the real LOI

𝐿

The user’s real location of interest (LOI)

𝐿∗

The adversary’s final guess as to the user’s real location of interest

K

The set of query destinations known to the adversary, i.e., K ⊆ L

L = {𝐿1, . . . , 𝐿𝑘 }

The 𝑘 locations queried by the user, with 𝐿 ∈ L

L𝑁

The set of possible locations queried by the user, as determined by the adversary, under the assumption that 𝐶 = 𝑁 for some 𝑁 ∈ C

MAOI , MCL, MLOI

The measures of the user’s AOI-, CL-, and LOI-privacy respectively

𝑛

The number of nodes in the network

N = {𝑁 1, . . . , 𝑁𝑛 }

The nodes in the network, with |N | = 𝑛

PG (condition)

A global, aggregate probability over all users that the given condition is true; for example, PG (𝐶 = 𝑁 | 𝐶 ∈ C) is the probability that any user’s current location is 𝑁 , given that their current location is known to be in C

Q = {𝑄 1, . . . , 𝑄𝑘 } R𝑖 = 𝑁𝑖,1, . . . , 𝑁𝑖,𝑙𝑖

5

The 𝑘 queries sent by the user

The route taken by query 𝑄𝑖 , transmitted through 𝑙𝑖 nodes

𝜎 (L, N )

A measure of how physically dispersed the elements of L are over the network N

U

The set of queries with destinations unknown to the adversary, i.e., U⊆Q Table 1. Table of notation

routing. An example in Figure 1 shows one possible route from the westernmost central node to the easternmost central node if fixed shortest-path routing is used, but three possible paths if random shortest-path routing is used. Recall that the user employs a mobile device to communicate with a nearby node, in order to route queries through the network to the LOIs. The user sends the 𝑘 queries, denoted Q = {𝑄 1, 𝑄 2, . . . , 𝑄𝑘 }, to the closest node, 𝐶. As simplifying assumptions, we assume both that the user knows the closest node, and that the mobile device and 𝐶 communicate using low-power communication. That is, the adversary will only overhear communication between the mobile device and 𝐶 if 𝐶 is compromised. We also assume that the adversary knows 𝑘 — the implication being that if the adversary overhears fewer than 𝑘 of the user’s queries, the adversary knows how many queries were not overheard. Each 𝑄𝑖 takes a route R𝑖 through the network, starting at 𝐶 and ending at 𝐿𝑖 . Denote R𝑖 as a sequence of nodes with length 𝑙𝑖 ,
R𝑖 = 𝑁𝑖,1, 𝑁𝑖,2, . . . , 𝑁𝑖,𝑙𝑖 , where 𝑁𝑖,1 = 𝐶 and 𝑁𝑖,𝑙𝑖 = 𝐿𝑖 . The goals of the adversary are to determine 𝐶 and to determine the real location of interest, i.e., to determine 𝐿.

6

Ryan Vogt, Ioanis Nikolaidis, and Mario A. Nascimento

While our 𝑘-anonymity scheme can be built over any existing query mechanism, we assume that query and reply messages are designed to maximize privacy. Specifically, a query message that is being routed from 𝐶 to 𝐿𝑖 cannot contain references to 𝐶, nor can a reply; otherwise, the adversary could easily determine 𝐶 (note, though, that even if a reference to 𝐶 were contained in queries and replies, this scheme could still be used to preserve the privacy of the user’s location of interest, just not their current location). Query messages contain four pieces of information in addition to the query itself: a unique query identifier for 𝑄𝑖 ; the destination 𝐿𝑖 (which may be the real location of interest or a dummy one); the identifier for the node currently transmitting the query, 𝑁𝑖,𝑗 ; and, the next hop in the route, 𝑁𝑖,𝑗+1 . When node 𝑁𝑖,𝑗+1 receives the query, it remembers the previous node in the route for query 𝑄𝑖 , 𝑁𝑖,𝑗 . Replies to the query message contain only the query identifier for 𝑄𝑖 . When node 𝑁𝑖,𝑗+1 receives a reply to the query, to be routed back to 𝐶, 𝑁𝑖,𝑗+1 uses its memory to identify 𝑁𝑖,𝑗 as the next hop in the reply path, and sends the reply to 𝑁𝑖,𝑗 (without unnecessary information such as the identity of 𝑁𝑖,𝑗 or 𝑁𝑖,𝑗+1 ). However, we assume the worst case: the adversary is able to determine which node is transmitting a reply message if that reply is overheard. If a query message for query 𝑄𝑖 is overheard and the header can be decrypted by the adversary (e.g., if a compromised node is routing the query, or if a global encryption key is used for all transmissions in the network), the adversary learns one of the LOIs, 𝐿𝑖 . Additionally, the adversary learns one hop that the query took along the route from 𝐶 to 𝐿𝑖 : 𝑁𝑖,𝑗 and 𝑁𝑖,𝑗+1 , for 1 ≤ 𝑗 < 𝑙𝑖 , where 𝑗 and 𝑙𝑖 are unknown to the adversary. That is, the adversary learns two consecutive elements in the route, but neither their position in the route nor the length of the route. If a reply message for query 𝑄𝑖 is overheard, the adversary learns only a single node that was involved in the route: 𝑁𝑖,𝑗 , for 1 < 𝑗 ≤ 𝑙𝑖 , again with unknown 𝑗 and 𝑙𝑖 . The adversary can also construct a list of nodes that were certainly not involved in routing 𝑄𝑖 . Because the adversary has complete knowledge of every message that was routed through compromised nodes in the user’s network, the adversary knows which compromised nodes were not involved in routing 𝑄𝑖 . An additional consideration for the adversary is that the malicious nodes could monitor all communication by honest nodes in their communication range. An adversary may conclude that if a malicious node that is monitoring an honest node within its range did not hear the honest node produce any traffic regarding query 𝑄𝑖 , then the honest node must not have been involved in routing 𝑄𝑖 . However, the malicious node may not have heard a message transmitted by the honest node due to interference or a collision. As such, we assume that the adversary will restrict the list of nodes that certainly were not involved with query 𝑄𝑖 to the set of compromised nodes in the network that did not route 𝑄𝑖 . The key insight for the adversary, having collected information on the routes of the queries, is that if no possible route from a node 𝑁 to the known destination of 𝑄𝑖 , 𝐿𝑖 , is consistent with the known information about 𝑄𝑖 , then 𝑁 could not have been the origin of the query. Formally, a route R = {𝑁 1, 𝑁 2, . . . 𝑁𝑙 } from 𝑁 to 𝐿𝑖 is consistent with that information, assuming the destination 𝐿𝑖 of 𝑄𝑖 is known, if: (1) R is a possible route from 𝑁 to 𝐿𝑖 (i.e., 𝑁 1 = 𝑁 , 𝑁𝑙 = 𝐿𝑖 , and the routing algorithm could have used this route); (2) For every query message about 𝑄𝑖 decrypted by the adversary, sent by 𝑁𝑖,𝑗 to 𝑁𝑖,𝑗+1 , there is some 𝑘 < 𝑙 such that 𝑁𝑘 = 𝑁𝑖,𝑗 and 𝑁𝑘+1 = 𝑁𝑖,𝑗+1 ; (3) For ever query message about 𝑄𝑖 overheard but not decrypted by the adversary, sent by 𝑁𝑖,𝑗 to an unknown destination, there is some 𝑘 < 𝑙 such that 𝑁𝑘 = 𝑁𝑖,𝑗 ; (4) For every reply message about 𝑄𝑖 overheard by the adversary, sent by 𝑁𝑖,𝑗 , there is some 𝑘 > 1 such that 𝑁𝑘 = 𝑁𝑖,𝑗 ; and, (5) No node that is known not to have routed 𝑄𝑖 appears in R.

Location-of-interest vs. Current-location Privacy in Multi-hop Communication

7

A simple example of the insight provided to the adversary from determining whether or not possible routes are consistent with known information is illustrated in Figure 2. In the illustrated example, there are two malicious nodes, one of which routed a query to the LOI and another that did not. Using this information, the adversary can narrow down the potential set of current locations of the user. There is a second insight, about queries for which the adversary does not know the destination. The adversary may still know some information about such a 𝑄𝑖 (e.g., non-decrypted query messages, overheard reply messages, or knowledge about compromised nodes that did not route 𝑄𝑖 ). Denote D as a set of possible destinations for the queries with unknown destinations. Specifically, let D be the set of all nodes in N that are not compromised and are not the destination of a query with a known destination. Let U be the set of queries for which the destination is unknown to the adversary, where 0 ≤ |U| ≤ 𝑘. If it is not possible to assign a unique destination from D to each query in U, in such a way as to ensure that there is a possible route from node 𝑁 to the destination of each query in U that is consistent with all of the known information about that query, then 𝑁 cannot be the origin of the user’s queries. Using the pseudo-code algorithm presented in Algorithm 1 and Algorithm 2, an adversary can narrow down

Did route query

Did not route query

the possible current locations of the user. Additionally, each assignment of potential destinations to the queries that is consistent with the information known by the adversary represents all the possible query destinations for each possible current location. The pseudocode returns a set C, representing all possible current locations for the user, and sets L N for each 𝑁 ∈ C, representing all the possible locations of interest (i.e., query destinations) for the user if they are indeed at current location 𝑁 .

Possible CLs

Algorithm 1 begins, assuming that the user’s current location is not compromised, by considering all honest nodes as potential current locations on line 4. However, any honest nodes from which queries consistent with the adversary’s

Fig. 2. The westernmost (blue) node is one of the queried locations, and knowledge of which malicious (red) nodes did and did not route the query to the LOI allows the adversary to narrow down the user’s potential current locations.

known information could not have been sent are removed as potential current locations on line 10. Potential query destinations from each potential current location obviously includes all known destinations, as computed on line 18. However, the adversary must compute potential destinations for queries with unknown destinations as well, as done on lines 13–17. The pseudocode presented in Algorithm 2 illustrates the most natural way of thinking about how the adversary can use information gained about queries with unknown destinations. The adversary considers all possible assignments of destinations to all queries with unknown locations on line 4, adding any possible destinations to the pool of potential destinations for the current locations on 7. If there are no possible assignments of destinations to queries with unknown destinations, the potential current location is removed from the pool of current location possibilities by a return of False to Algorithm 1. However, the naïve implementation of this pseudocode would be highly inefficient. The following1 lemma allows the adversary to implement the algorithm far more efficiently.

1 All proofs requiring more than a few lines are collected in Appendix B.

8

Ryan Vogt, Ioanis Nikolaidis, and Mario A. Nascimento

Algorithm 1 Pseudocode for finding all possible current locations and locations of interest for the user. 1: function Narrow-Possible-CLs-And-LOIs 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19:

if the node 𝐶 with which the user is communicating is compromised then return C = {𝐶} , L𝐶 = {𝐿1, . . . , 𝐿𝑘 } Nhonest ← {𝑁 ∈ N | 𝑁 is not compromised} C ← Nhonest L𝑁 ← {} ∀ 𝑁 ∈ C for all queries 𝑄𝑖 for which the destination is known do for all 𝑁 ∈ C do if Possible-Consistent(𝑁 , 𝑄𝑖 ) = False then Remove 𝑁 from C K ← {𝐿𝑖 | 𝐿𝑖 is known} U ← {𝑄𝑖 | 𝐿𝑖 is unknown} if |U| > 0 then D ← Nhonest \ K for all 𝑁 ∈ C do if Analyse-Unknown(𝑁 , L𝑁 , D, U) = False then Remove 𝑁 from C L𝑁 ← L𝑁 ∪ K ∀ 𝑁 ∈ C return C, {L𝑁 | 𝑁 ∈ C}

20: function Possible-Consistent(src, Q) 21: 22: 23: 24: 25:

𝐿 ← the destination of query 𝑄 if ∃ a possible route from src to 𝐿, consistent with everything known about 𝑄 then return True else return False

Algorithm 2 A naïve implementation of the analysis of queries with unknown destinations 1: function Analyse-Unknown(𝑁 , L𝑁 , D, U) 2: 3: 4: 5: 6: 7: 8:

foundAssignment ← False D|
for D ′ ← each of the || U | choices of |U| destinations from D do ′ for all |D |! assignments of nodes in D ′ as destinations for U do if Possible-Consistent(𝑁 , 𝑄) = True ∀ 𝑄 ∈ U then foundAssignment ← True L𝑁 ← L𝑁 ∪ D ′ return foundAssignment

Lemma 4.1. Given a family of sets of integers, {S1, . . . , S𝑚 } where S𝑖 ⊆ Z, we call a set G𝑚 = {𝑔1, . . . , 𝑔𝑚 } a sampling ′ = {G | G is a sampling}, i.e., G ′ is a set of sets, where each if 𝑔𝑖 ∈ S𝑖 for all 1 ≤ 𝑖 ≤ 𝑚, and 𝑔𝑖 ≠ 𝑔 𝑗 for all 𝑖 ≠ 𝑗. Let G𝑚 𝑚 𝑚 𝑚 ′ is a set of 𝑚 unique integers, with each integer coming from a different one of the S , 1 ≤ 𝑖 ≤ 𝑚. Then either G𝑚 ∈ G𝑚 𝑖 ′ = ∅ or G𝑚

Ø ′ G𝑚 ∈ G𝑚

G𝑚 =

Ø

S𝑖 .

1≤𝑖 ≤𝑚

Given a potential current location 𝑁 ∈ C and queries with unknown destinations U, we can compute potential destinations S1, . . . , S| U | for each of the queries. We can then test if it is possible to choose a unique destination for

Location-of-interest vs. Current-location Privacy in Multi-hop Communication

9

each query, i.e., choose 𝑠𝑖 ∈ S𝑖 with 𝑠𝑖 ≠ 𝑠 𝑗 for all 𝑖 ≠ 𝑗, where 1 ≤ 𝑖, 𝑗 ≤ |U|. If it is possible to choose even a single set of unique destinations, then Lemma 4.1 tells us that the set of all potential destinations for all the queries with unknown destinations is ∪1≤𝑖 ≤ | U | S𝑖 , i.e., no potential destinations can be excluded. Testing whether it is possible to choose a unique destination from each S𝑖 can be accomplished by creating a graph 𝐺 = ⟨(𝑋, 𝑌 ), 𝐸⟩, where 𝑋 contains a vertex for each of the |U| sets S𝑖 , 𝑌 contains a vertex for each potential destination in ∪1≤𝑖 ≤ | U | S𝑖 , and 𝐸 contains an edge between the vertex in 𝑋 representing S𝑖 and the vertex in 𝑌 representing 𝑠 if and only if 𝑠 ∈ S𝑖 . It is possible to choose a unique destination from each S𝑖 if and only if there is a bipartite matching on 𝐺 of size |U|, and testing for a bipartite matching is a well-studied problem [6, pp. 664–669]. A revised, efficient algorithm for analyzing queries with unknown destinations is illustrated as Algorithm 3. Algorithm 3 An efficient implementation of the analysis of queries with unknown destinations 1: function Analyse-Unknown(𝑁 , L𝑁 , D, U) 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14:

S𝑖 ← {} ∀ 1 ≤ 𝑖 ≤ |U| for all 𝑈𝑖 ∈ U do for all 𝐷 ∈ D do if Possible-Consistent-Assume(𝑁 , 𝐷, 𝑈𝑖 ) then Add 𝐷 to S𝑖 𝑋 ← a vertex for each S𝑖 , 1 ≤ 𝑖 ≤ |U| 𝑌 ← a vertex for each destination in ∪1≤𝑖 ≤ | U | S𝑖 𝐸 ← edges between vertex representing S𝑖 and vertex representing 𝐷 iff 𝐷 ∈ S𝑖 if there exists a bipartite matching of size |U| on 𝐺 = ⟨(𝑋, 𝑌 ), 𝐸⟩ then L𝑁 ← L𝑁 ∪ S1 ∪ . . . ∪ S| U | return True else return False

15: function Possible-Consistent-Assume(src, 𝐿, Q) 16: 17: 18: 19: 20:

Assume, just for now, that the destination of 𝑄 is 𝐿 if ∃ a possible route from src to 𝐿, consistent with all known/assumed about 𝑄 then return True else return False

Given the adversary’s ability to narrow down the user’s possible current locations to a set C and possible locations of interest to a set L𝑁 for each 𝑁 ∈ C, a simple yet expressive way to measure the security of a user’s location of interest and current location is the probability that the adversary will guess the LOI and CL incorrectly, respectively. As a simple example, if the adversary knows the value of 𝑘 (a necessary assumption to make, as it is unsafe to assume otherwise), and if the adversary overhears all 𝑘 queries in a uniform, featureless environment (i.e., all 𝑛 potential query destinations in the network are equally probable destinations), then the user’s resulting LOI-privacy will be 𝑘 𝑘−1 , because the adversary can merely guess at random that one of the 𝑘 destinations is the correct one. More formally, we begin by assuming the adversary knows — from a global, aggregate perspective — the probability that a given node in the network is a user’s current location, and the probability that each node is a user’s location of interest given a known current location. We denote these probabilities as PG (𝐶 = 𝑁 ) and PG (𝐿 = 𝑀 | 𝐶 = 𝑁 ) respectively. For now, we assume that PG (𝐶 = 𝑁 ) = PG (𝐿 = 𝑀 | 𝐶 = 𝑁 ) = 𝑛1 for all nodes 𝑁 and 𝑀 in the network. We will revisit this assumption in Section 8.

10

Ryan Vogt, Ioanis Nikolaidis, and Mario A. Nascimento

First, the adversary corrects the probability of each node being the current location, based on the set of possible current locations. That is, the adversary computes  PG (𝐶 = 𝑁 )   if 𝑁 ∈ C Í  𝑃 ∈ C PG (𝐶 = 𝑃) PG (𝐶 = 𝑁 | 𝐶 ∈ C) =   0 if 𝑁 ∉ C  for each 𝑁 ∈ C. From the computation of this corrected probability, we naturally get the formal definition of CL-privacy, which is the probability of the adversary incorrectly guessing the user’s current location. Define 𝐶 ∗ = arg max {PG (𝐶 = 𝑁 | 𝐶 ∈ C)} , 𝑁 ∈C

i.e., 𝐶 ∗ is the adversary’s best guess as to the user’s current location. The formal definition of CL-privacy can then be stated as MCL = 1 − PG (𝐶 = 𝐶 ∗ | 𝐶 ∈ C) . The user’s LOI-privacy is computed in a similar fashion: the probability that the adversary incorrectly guesses the user’s actual location of interest. First, note that the user’s actual location of interest may be a destination of one of the 𝑘 queries where the destination is known to the adversary (e.g., if a compromised node routed the query), or it may be the destination of a query where the destination is unknown to the adversary. Based on the value of PG (𝐿 = 𝑀 | 𝐶 = 𝑁 ), an adversary may actually guess that the user’s real location of interest is a location that is not known to be a query destination, if the adversary does not know the destination of all 𝑘 queries. To account for this possibility, we first need to apply a “corrective weight” to the probability that a given location 𝑀 ∈ N is the user’s real LOI, assuming that another location 𝑁 ∈ N is their current location. Let K be the set of all query destinations that are known to the adversary (i.e., K ⊆ L), then denote   1      𝜒 (𝑁 , 𝑀) = 0   𝑘 − |K |     |L𝑁 | − |K |

if 𝑀 ∈ K if 𝑀 ∉ K and |L𝑁 | = |K | otherwise.

Using 𝜒 as a corrective weight, we can compute the weighted probability that 𝑀 is the user’s location of interest, given that 𝑁 is their current location and their location of interest is in L𝑁 , as  PG (𝐿 = 𝑀 | 𝐶 = 𝑁 ) · 𝜒 (𝑁 , 𝑀)   Í  𝑃 ∈ L𝑁 PG (𝐿 = 𝑃 | 𝐶 = 𝑁 ) · 𝜒 (𝑁 , 𝑃) 𝜙 (𝑁 , 𝑀) =   0 

if 𝑀 ∈ L𝑁 𝑖 𝑓 𝑀 ∉ L𝑁 ,

for each 𝑁 ∈ C and 𝑀 ∈ L𝑁 . We subsequently define 𝜓 (𝑁 , 𝑀) as the probability that both 𝑁 is the current location and 𝑀 is the real location of interest. Namely: 𝜓 (𝑁 , 𝑀) = PG (𝐶 = 𝑁 | 𝐶 ∈ C) · 𝜙 (𝑁 , 𝑀) . We assume that the goal for the adversary is to choose the most likely real LOI, independent of the adversary’s guess about the user’s current location (we return to this assumption shortly). In this case, the adversary would compute the probability that a node 𝑀 is the user’s real location of interest over all possible current locations as ∑︁ 𝜔 (𝑀) = 𝜓 (𝑁 , 𝑀) , 𝑁 ∈C

Location-of-interest vs. Current-location Privacy in Multi-hop Communication

11

for all possible LOIs 𝑀 (i.e., for any 𝑀 ∈ ∪𝑁 ∈ C L𝑁 ). The adversary then guesses the real LOI as 𝐿 ∗ = arg max𝑀 𝜔 (𝑀). As such, the user’s resulting LOI-privacy is MLOI = 1 − 𝜔 (𝐿 ∗ ) . Given the above definitions, it is worth stating two consequences, posed as the following lemmas. Lemma 4.2. If the adversary knows that any user’s real location of interest is in fact their current location, i.e., PG (𝐿 = 𝑁 | 𝐶 = 𝑀) =

  0   1 

if 𝑁 ≠ 𝑀 if 𝑁 = 𝑀 ,

then MCL = MLOI . Lemma 4.3. If the user’s current location is compromised, then MCL = 0 and MLOI = 1 − max PG (𝐿 = 𝑀 | 𝐶 = 𝐶 ∗ and 𝐿 ∈ L) . 𝑀∈L

Consider a uniform, featureless environment — that is, an environment in which, from any current location, the probability of each location being any user’s real LOI is 𝑛1 . If the user’s current location is compromised in a uniform, featureless environment, then MLOI = (𝑘 − 1)/𝑘 . Previously, we assumed that the adversary would guess the user’s current location and real location of interest independently of one another (i.e., a best attempt to get at least one, if not both, of those two locations correct). In some contexts, however (e.g., intercepting a user who is moving from their current location to a location of interest), it might be in the interest of the adversary to choose the most likely ⟨𝐶 ∗, 𝐿 ∗ ⟩ pair. That is, the adversary wants to maximize their chances of guessing both the user’s CL and LOI simultaneously correctly. Such an adversary would choose 𝐶 ∗ and 𝐿 ∗ as arg max ⟨𝐶 ∗ ,𝐿∗ ⟩ 𝜓 (𝐶 ∗, 𝐿 ∗ ) , and the computation of the user’s CL- and LOI-privacy would remain the same as MCL = 1 − PG (𝐶 = 𝐶 ∗ | 𝐶 ∈ C) and MLOI = 1 − 𝜔 (𝐿 ∗ ) respectively. For the purposes of this paper, however, we restrict our investigation to an adversary who guesses the user’s current location and location of interest independently, as such an adversary is stronger. 4.2

Privacy of the Area of Interest

If it is equally probable that any of the 𝑘 queried nodes is the real LOI (i.e., in the featureless environment), then the adversary cannot learn which of the 𝑘 nodes queried is the real LOI. Given this assumption, what is actually meant when we discuss protecting the privacy of the user’s LOI? Consider the two scenarios in Figure 3. In both cases, the user’s real LOI is the starred node in the northeast, and 𝑘 − 1 = 3 dummy LOIs are chosen to disguise the real LOI. However, in Figure 3a, all four LOIs are clustered in the east. While an adversary who overhears these queries would not know which node is of interest to the user, it would be obvious that the user is interested in the eastern region of the network. In Figure 3b, the four LOIs are dispersed throughout the network, obfuscating the area of the network in which the user is interested. We need to define a measure of how dispersed the 𝑘 LOI choices are. That is, we want to measure how well-protected the privacy of the user’s area of interest (AOI) is.

12

Ryan Vogt, Ioanis Nikolaidis, and Mario A. Nascimento

(a) A poor choice.

(b) A good choice.

Fig. 3. A comparison of two choices for 𝑘 − 1 = 3 dummy LOIs (dark nodes) given one fixed real LOI (starred node).

(b) A choice of LOIs that disperses the LOIs across the entire network.

(a) A choice of LOIs that results in two clusters.

Fig. 4. A comparison of two choices for 𝑘 = 3 LOIs in a five-node network.

To measure how well the set L of 𝑘 LOIs preserves the user’s AOI-privacy, we define a function 𝜎 (L, N ) to measure how dispersed the LOIs are over the network N . To allow for comparisons of different methods of choosing the dummy LOIs over networks with different topologies, we normalize the score returned by 𝜎. Let 𝜎min (𝑘, N ) and 𝜎max (𝑘, N )
be the minimal and maximal values returned by 𝜎, over all 𝑛𝑘 possible sets of 𝑘 LOIs. The normalized measure of AOI-privacy is defined as    if 𝜎min (𝑘, N ) = 𝜎max (𝑘, N ) 1  MAOI (L, N ) = 𝜎 (L, N ) − 𝜎min (𝑘, N )   otherwise. 𝜎  max (𝑘, N ) − 𝜎min (𝑘, N ) The function 𝜎 must have the property that it returns large values for sets L with minimal clustering of the LOIs, and small values otherwise. Ideally, it is also easy to compute on the user’s low-powered, mobile device prior to issuing a query. Next, we discuss some alternatives for 𝜎. 4.2.1 Variance-Based 𝜎. One straightforward approach is to compute a variance-like quantity for the positions of the nodes in L, measuring the squared distance between LOIs: 𝜎 (L, N ) =

𝑘 −1 ∑︁ 𝑘 ∑︁

D 𝐿𝑖 , 𝐿 𝑗

2

,

𝑖=1 𝑗=𝑖+1

where D is the Euclidean distance between two nodes. However, this definition of 𝜎 does not penalize clustering properly. Consider the examples in Figure 4. The choice of dummy LOIs in Figure 4a has two of the LOIs clustered together. In Figure 4b the three LOIs are dispersed evenly. However, the 𝜎 value for the first choice is higher. This result is similar to how the variance for the data set {1, 2, 5} is higher than the variance for the data set {1, 3, 5}.

Location-of-interest vs. Current-location Privacy in Multi-hop Communication

(a) A choice of LOIs with significant overlap among the circles.

13

(b) A choice of LOIs with minimal overlap among the circles.

Fig. 5. A comparison of two choices for 𝑘 = 4 LOIs in a network, each surrounded by a circle with a fixed, arbitrary radius.

4.2.2 Union of Circles 𝜎. Another approach is to determine how much overlap exists among the regions around each LOI. Specifically, one can draw a circle of radius 𝑟 around each LOI and let 𝜎 be the area of the union of the 𝑘 circles. The more clustered the LOIs, the more overlap there would be among the circles, resulting in a smaller area. An example is presented in Figure 5. With 𝑘 clustered LOIs, shown in Figure 5a, there is significant overlap among the circles, unlike with the non-clustered choice shown in Figure 5b. One way to choose 𝑟 is to define 𝑑 as the maximum distance between any two nodes in N , then set 𝑟 = 𝑑2 . This definition ensures that there is no overlap between the regions of the two nodes that are farthest apart, but the regions surrounding any two nodes that are closer together will overlap. Alternately, 𝑟 could be chosen as the maximal size such that 𝑘 nodes could be chosen from N with no overlap among the 𝑘 associated circles. While this 𝜎 properly penalizes clustering, it is unclear what an ideal value for 𝑟 would be. Ultimately, we do not investigate this issue further, because this 𝜎 is unnecessarily computationally expensive, compared to the other 𝜎 alternatives mentioned subsequently. Note, however, that there are known methods for computing the area of the union of circles, including an O (𝑘 2 ) deterministic algorithm and an O (𝑘) Monte Carlo algorithm [33]. 4.2.3 Minimal Pairwise Distance 𝜎. A simple computation that penalizes two LOIs being close together is to measure the minimal distance between any two LOIs. Formally, let 
𝜎 (L, N ) = min D 𝐿𝑖 , 𝐿 𝑗 , 𝑗≠𝑖

where D is the Euclidean distance between two nodes. The closer the two closest 𝐿𝑖 become, the lower the value of 𝜎. Unfortunately, while this approach properly punishes having two queried nodes close together, it does not distinguish between a mediocre situation (e.g., having two of the 𝐿𝑖 close together) and a bad situation (e.g., having all of the 𝐿𝑖 close together). Consider the situation in Figure 6. In Figure 6a, the situation is not ideal: two of the LOIs are close together; that said, it is not a terrible physical distribution of the queried location. Figure 6b, on the other hand, illustrates a far worse situation, in which all of the LOIs are clustered. In both cases, however, the value of 𝜎 (L, N ) will be the same: the distance between the two closest nodes (i.e., the two nodes in the upper right).

14

Ryan Vogt, Ioanis Nikolaidis, and Mario A. Nascimento

(a) A mediocre choice with two LOIs close together.

(b) A bad choice with all of the LOIs close together.

Fig. 6. A comparison of two choices for 𝑘 = 4 LOIs in a network, both having at least two LOIs close together.

4.2.4 Sum of Minima 𝜎. Measuring the sum of minimum distances from each LOI to any other LOI penalizes clustering properly and is easy to compute. Formally, let 𝜎 (L, N ) =

𝑘 ∑︁


min D 𝐿𝑖 , 𝐿 𝑗 , 𝑗≠𝑖

𝑖=1

where D is again the Euclidean distance between two nodes. That is, the farther away each of the 𝐿𝑖 are from each other, the higher the value of 𝜎. Returning to the five-node examples in Figure 4, this 𝜎 returns a higher value in the scenario where the LOIs are non-clustered; and, it can be computed quickly, given the location of every node in L. This 𝜎 function is essentially a more expressive version of the minimal-pairwise-distance version of 𝜎, in that it not only properly punishes clustering, but also properly distinguishes between mediocre and bad distributions of queried locations.

Considering these four possible 𝜎 functions, we use the sum of minima function for most of this paper (it will be noted explicitly when one of the other 𝜎 functions is used). We chose this 𝜎 function since we assume that the user, prior to issuing any set of 𝑘 queries, will want to precompute the AOI-privacy that will result from the queries using a mobile device with limited processing power. If processing power were not a concern, the union of circles metric could be used instead (though how to best choose the radius of the circles used in the computation remains an open question). 5

Choosing the Dummy LOIs

Given the metrics necessary to measure how well a set of 𝑘 queries preserves the privacy of the user’s area of interest (AOI) and current location (CL), we now investigate how the user should choose the 𝑘 − 1 dummy locations of interest (LOIs) to query, given one real LOI. Regardless of how the dummy LOIs are chosen, recall our assumption that, from the point of view of the adversary, it is equally probable that any of the 𝑘 queried nodes is the real LOI. Any implementation of 𝑘-anonymity for network queries must take into account real-life limitations. For example, if troops using a military network queried one node at a location of strategic importance and 𝑘 − 1 nodes at strategically irrelevant positions, the adversary could guess the real LOI with high probability. Another situation that could leak the real LOI is if the user issues multiple queries to the real LOI. Any algorithm used to choose the 𝑘 − 1 dummy LOIs based on the real LOI is required to choose the same 𝑘 − 1 dummy LOIs each time the user issues a real query. Otherwise, if the user first queries the 𝑘 nodes in L1 then later issues queries to the 𝑘

Location-of-interest vs. Current-location Privacy in Multi-hop Communication

(a) The 𝑘 = 3 nodes that were actually queried by the user.

15

(b) The nodes that would have been chosen as L were the westernmost node the real LOI.

Fig. 7. An example of the 𝜎-maximizing choice function leaking the real LOI.

nodes in L2 ≠ L1 , and if the adversary can correctly guess that the user was issuing repeat queries to the same node (it is overly optimistic to assume otherwise), the adversary would learn that the real LOI is in L1 ∩ L2 . Let F be the choice function that takes the real LOI 𝐿 and returns a set L of 𝑘 LOIs to query, with 𝐿 ∈ L. If F is deterministic, repeat queries are of no concern, since F (𝐿) = L for each call to F (𝐿). If F is a random function, taking 𝐿 and a random seed 𝑠𝐿 as parameters and using a cryptographically secure pseudo-random number generator [2] to choose the dummy LOIs, the user should encapsulate F in a deterministic function. For example, the user could call F′ (𝐿) = F (𝐿, 𝑠𝐿 ), where 𝑠𝐿 = PRF (𝑠, 𝐿) is computed using a stored secure seed (i.e., a key), 𝑠, and pdeudorandom function PRF. The pseudorandom function could be as simple as a cryptographic hash function, e.g., SHA-2 [4], on the concatenation of 𝑠 and 𝐿, i.e., PRF (𝑠, 𝐿) = SHA-2-256 (𝑠 ◦ 𝐿), with ◦ representing concatenation. Alternately, a more robust approach could use a key-derivation function (KDF) as the pseudorandom function [5]. It is not only multiple queries to the real LOI that pose a problem; even a single set of 𝑘 queries could leak the real LOI. Knowledge of how F works could be sufficient for the adversary to determine the real LOI, given the set L of all 𝑘 nodes queried. Consider a deterministic F that takes the real LOI 𝐿 and returns a list L that contains 𝐿 and the 𝑘 − 1 dummy LOIs, such that 𝜎 (L, N ) is maximized over all possible choices of 𝑘 − 1 dummy LOIs. This function, which maximizes the user’s AOI-privacy, may leak the user’s real LOI. Consider the example in Figure 7. If the 𝑘 = 3 nodes illustrated in Figure 7a are queried, the adversary would know that the interior LOI is the real LOI. Were the westernmost node the real LOI, the central node and the easternmost node would have been chosen by F as the dummy LOIs, as illustrated in Figure 7b, to maximize 𝜎. Similarly, the easternmost node could not be the real LOI. For F not to leak information in this fashion, F must generate a set L ⊆ N that is closed under F. For a deterministic F, this closure requirement means: if F (𝐿) = L for some 𝐿 ∈ N , then F (𝐿𝑖 ) = L for all 𝐿𝑖 ∈ L. The closure requirement for a non-deterministic F is more complex. We assume that the random seed 𝑠 passed to F is secret; because the seed must remain secret, it must be sufficiently long (e.g., 256 bits) to prevent exhaustive search of the seed space by the adversary. As such, the adversary cannot compute F (𝐿𝑖 , 𝑠) for every 𝐿𝑖 ∈ L. What the adversary can do is estimate probabilities. Define P (F, L, 𝐿𝑖 ) as the proportion of all seeds in the seed space for which F will generate L, given 𝐿𝑖 and a seed as arguments. Given L, the adversary can estimate P (F, L, 𝐿𝑖 ) for each 𝐿𝑖 ∈ L by running F (𝐿𝑖 , 𝑠 test ) with a large number of different test seed values. The adversary can then predict that the largest estimate corresponds to the most likely real LOI. That is, if 𝐿max = arg max𝐿𝑖 ∈ L {P (F, L, 𝐿𝑖 )}, then 𝐿max has the highest probability of having generated L, and hence is the most likely real LOI. Based on this attack, the closure property necessary for a non-deterministic F is: if F (𝐿, 𝑠) = L for some 𝐿 ∈ N and seed 𝑠, then P (F, L, 𝐿) = P (F, L, 𝐿𝑖 ) for all 𝐿𝑖 ∈ L. The simplest method of fulfilling the closure requirement is to generate an unbiased random partitioning of the network. When the user wishes to query a real LOI, the dummy LOIs also queried are the other nodes in the real LOI’s partition. Note that the size of the partitions, while obviously based on the LOI-privacy requirements of the user, may not be able to be uniform. For example, a network of 50 nodes cannot be divided into partitions each of size 𝑘 = 3.

16

Ryan Vogt, Ioanis Nikolaidis, and Mario A. Nascimento Lemma 5.1. Any network with 𝑛 ≥ 3 nodes can be partitioned such that each partition contains 3–5 nodes. Proof. By induction. For 𝑛 ∈ [3, 5], use a single partition of size 𝑛. Assuming you can partition a network of size

𝑛 = 3𝑗 + 𝑘, where 𝑗 ≥ 0, 𝑘 ∈ [3, 5], you can partition a network of size 𝑛 + 3 = 3( 𝑗 + 1) + 𝑘 by using an additional partition of size 3.

□

Because of Lemma 5.1, we will use partitions of sizes 3-5 whenever the need for partitioning a network arises throughout this paper. We further investigate the problem of generating partitions and partitionings on networks in the next section. 6

The Partition and Partitioning Problems

The goal of maximizing the minimal distance between nodes in a partition, introduced in Section 4.2, as well as the requirement to partition the nodes in a network discussed in Section 5, give rise to two optimization problems. We refer to these problems as the partition problem and the partitioning problem. For this section alone, for simplicity, we will consider the “minimal pairwise distance” definition of 𝜎 presented in Section 4.2. That is, in both problems, you are given a set of distinct points 𝑆 in R2 , with |𝑆 | ≥ 2. We define the “goodness” of any subset 𝑇 ⊆ 𝑆 as G(𝑇 ) = min {D(𝑥, 𝑦) | 𝑎, 𝑏 ∈ 𝑇 , 𝑎 ≠ 𝑏} , where D is Euclidean distance in R2 . In other words, G(𝑇 ) is the minimal Euclidean distance between any two points in 𝑇 . We also extend the notion of goodness to multiple subsets as G(𝑇1, . . . ,𝑇𝑛 ) = min {G(𝑇1 ), . . . , G(𝑇𝑛 )} . Or, in other words, the goodness of a set of subsets is only as good as the goodness of the worst subset. In the partition optimization problem, you are given a set of points 𝑆 in R2 and an integer 2 ≤ 𝑘 ≤ |𝑆 |. The goal is to find the subset 𝑇 of 𝑆 with |𝑇 | = 𝑘 that maximizes G(𝑇 ). This problem is equivalent to maximizing the area of interest (AOI) privacy in a single set of queries to 𝑘 nodes (under the “minimal pairwise distance” definition of 𝜎). In the partitioning optimization problem, you are given a set of distinct points 𝑆 in R2 and two integers 𝑘 min and 𝑘 max such that 2 ≤ 𝑘 min ≤ 𝑘 max ≤ |𝑆 |. The goal is to partition 𝑆 into subsets 𝑇1, . . . ,𝑇𝑚 with 𝑘 min ≤ |𝑇𝑖 | ≤ 𝑘 max for all 𝑖, such that G(𝑇1, . . . ,𝑇𝑚 ) is maximized. Here, partitioning into subsets has the usual meaning: 𝑇𝑖 ∩ 𝑇 𝑗 = ∅ for all 𝑖 ≠ 𝑗, and ∪𝑖𝑇𝑖 = 𝑆. This problem is equivalent to maximizing the AOI-privacy over all the partitions in the partitioning of a network (again, under the “minimal pairwise distance” definition of 𝜎). We begin with decision variants of these two problems on a graph (as opposed to in R2 ): • Partition-Graph: You are given a graph 𝐺 = ⟨𝑉 , 𝐸⟩, 𝑘 ∈ Z ≥ 2, and 𝑑 ∈ Z ≥ 1. Is there a subset 𝑆 ⊆ 𝑉 with |𝑆 | = 𝑘 such that the shortest path between any two elements in 𝑆 has length at least 𝑑? • Partitioning-Graph: You are given a graph 𝐺 = ⟨𝑉 , 𝐸⟩, 𝑘 min ∈ Z and 𝑘 max ∈ Z with 1 ≤ 𝑘 min ≤ 𝑘 max ≤ |𝑉 |, and 𝑑 ∈ Z ≥ 1. Can the vertices of 𝐺 be partitioned into disjoint sets 𝑇1, . . . ,𝑇𝑚 such that 𝑘 min ≤ |𝑇𝑖 | ≤ 𝑘 max and the shortest path between any two vertices in 𝑇𝑖 has length at least 𝑑, for all 𝑖? In Appendix A we prove that both problems are NP-complete. Furthermore, the partition optimization problem is known to be NP-hard on R2 as well as on graphs [38]. We additionally conjecture the following: Conjecture 6.1. The partitioning optimization problem is NP-hard on R2 .

Location-of-interest vs. Current-location Privacy in Multi-hop Communication

17

While we do not have a proof that this problem is NP-hard on R2 , we also have no reason to doubt as much. The related problem of partitioning points on Z2 into a given number of partitions (with no size restrictions) such that the points within any given partition are a minimum distance apart is believed to be NP-hard [19], and another related problem of painting colours onto aircraft to maximize the distance between similar colours is also believed to be hard [30]. A formal proof that the partitioning problem is NP-hard on R2 remains an open problem. The partition optimization problem can be solved in O (𝑛 log 𝑛) time, where |S| = 𝑛, if we restrict the problem to the case of 𝑘 = 2 [17]. The solution is based on performing a Graham scan [12] to find the convex hull of the points S and determining the two furthest points from each other on the hull [36]. The partition optimization problem, for any fixed value of 𝑘, can be solved in polynomial time. That is because the number of candidate solutions is O (𝑛𝑘 ), where |S| = 𝑛, which is polynomial for a fixed 𝑘. 6.1

Greedy Partition Approximation

We present here a Θ(1) greedy approximation algorithm to the partition problem, based on private communication with Har-Peled and Sidiropoulos [15]: (1) Pick 𝑥 1 to be an arbitrary node in the network; then, (2) Inductively, given 𝑋𝑖 = {𝑥 1, . . . , 𝑥𝑖 }, 𝑖 < 𝑘, pick node 𝑥𝑖+1 ∉ 𝑋𝑖 such that min (D(𝑥 1, 𝑥𝑖+1 ), . . . , D(𝑥𝑖 , 𝑥𝑖+1 )) is maximized. The algorithm is a simple loop that, in each iteration, considers Θ(𝑛) nodes to be the next possible node added to the partition — doing so would require only a single distance computation between the node under consideration and the most recent node added to the partition, possibly causing the minimal distance to any node in the partition to be updated for the node under consideration. The loop iterates 𝑘 − 1 times, so clearly this algorithm can be implemented in O (𝑛𝑘) time with O (𝑛) memory. This approximation algorithm is similar to one proposed by Ravi et al. [29] for the maximal minimum facility dispersion problem. A version for facility dispersion on continuous graphs was proposed by Tamir [35]. For the convenience of the reader, we have included an original proof that the algorithm in indeed a Θ(1) approximation — in fact, a 2-approximation — for the partition problem. Lemma 6.2. Let 𝑋 = {𝑥 1, . . . , 𝑥𝑘 } be the partition returned by the greedy algorithm, with minimal pairwise distance 𝑑 ′ . Let 𝑌 = {𝑦1, . . . , 𝑦𝑘 } be an optimal solution to the partition problem. Let 1 < 𝑠 ≤ 𝑘 be the smallest integer such that there exists 𝑡 < 𝑠 where D(𝑥𝑠 , 𝑥𝑡 ) = 𝑑 ′ . Then, for all 𝑦 ∈ 𝑌 , there exists an 𝑥 𝑦 ∈ 𝑋𝑠 −1 = {𝑥 1, . . . , 𝑥𝑠 −1 } such that D(𝑦, 𝑥 𝑦 ) ≤ 𝑑 ′ . Proof. Let 𝑦 be an arbitrary node of the optimal solution 𝑌 with a distance greater than 𝑑 ′ from every node in 𝑋𝑠 −1 . However, the node chosen by the greedy algorithm as 𝑥𝑠 has the greatest minimal distance to any node in 𝑋𝑠 −1 , namely 𝑑 ′ , which is a contradiction.

□

Theorem 6.3. The greedy algorithm is a 2-approximation for the partition problem. The greedy algorithm and its proof in Theorem 6.3 generalize to choosing points to maximize the minimal pairwise distance over any continuous convex space in R2 . 6.2

Divide-and-Conquer Partitioning

In this section, we present a divide-and-conquer algorithm for effectively solving the partitioning problem. The idea underlying the algorithm is first to compute the number of nodes that will be assigned to each partition within the

18

Ryan Vogt, Ioanis Nikolaidis, and Mario A. Nascimento

partitioning. The algorithm then finds a partition of size 𝑘, where 𝑘 is the largest number of nodes that have to be assigned to any partition (up to a maximum of 𝑘 = 𝜇). This partition could be found as an optimal partition via brute-force, or via a Monte Carlo algorithm (in our implementation, we use a Monte Carlo algorithm that generates 𝜋 random partitions and chooses the best one). The nodes in this partition serve as seeds that form the basis of subnets of the network. Each node in the network is assigned to the subnet of its closest seed, and the number of nodes to be assigned to each partition are divided evenly among the subnets. The algorithm then continues recursively on each subnet, until the maximal number of nodes to be assigned to each partition in a given subnet is only one — at this point, each node in the subnet is assigned at random to one of the partitions requiring a node from that subnet. The algorithm is formalized in Algorithm 4, with the entire process repeating 𝛼 times and the best partitioning out of all of those being returned on line 14. The integer division that begins the Divide-And-Conqer() function is just to divide the number of nodes that will be in each partition as equally as possible. First, we compared the divide-and-conquer algorithm to a randomized partitioning algorithm and to a brute-force search that finds an optimal partitioning. The randomized algorithm is formalized as Algorithm 5. It uses the same integer division technique to equally divide the partition sizes as the divide-and-conquer algorithm, starting on line 3; however, once the partition sizes are equally distributed, it assigns random unassigned nodes to each partition to fill that partition, on line 18. The entire process of creating a partitioning randomly is repeated 𝛼 times, as with the divide-and-conquer algorithm, and the best partitioning is returned. For the randomized algorithm, we ran 1000 trials using 𝛼 = 1000. The same number of trials were used for the divide-and-conquer algorithm, with 𝛼 = 1000, 𝜋 = 10, and 𝜇 = 3. Fewer trials were needed for the brute-force approach; we ran 25 trials just to get an accurate timing. The experiment was performed on a 9x5 grid of nodes, and the results are summarized in Figure 10. The running times, measured on a 2.93 GHz Core i7 with 8 GB of RAM running OS X 10.8.4, illustrate that the divide-and-conquer partitioning algorithm is orders of magnitude faster than a brute-force search. While it is slower than a randomized approach, the divide-and-conquer algorithm also returned significantly better results than the random algorithm. 30

2.5

25

2.0

Score 1.0

π=1 π = 10 π = 100

20

Time (ms)

π=1 π = 10 π = 100

1.5

15

10 0.5

0.0

5

1

10

100

α

1000

0

1

10

100

1000

α

Fig. 8. The effect of the 𝛼 and 𝜋 parameters on the score and running time of the divide-and-conquer partitioning algorithm on a grid topology.

The effect of the variables 𝛼 (the number of Monte Carlo attempts run for the entire partitioning algorithm) and 𝜋 (the number of partitions generated each time seeds are needed) is highlighted in Figure 8. We modified the values of 𝛼 and 𝜋, while running the divide-and-conquer partitioning algorithm on the same 9x5 grid. For each ⟨𝛼, 𝜋⟩ pair, we ran 1000 trials. Unsurprisingly, increasing the values of 𝛼 and 𝜋 increases the average quality of the partitioning that is chosen in the end. However, as evidenced by the running time graph, increasing 𝜋 to large values can increase

Location-of-interest vs. Current-location Privacy in Multi-hop Communication

19

Algorithm 4 The divide-and-conquer algorithm for solving the partitioning problem 1: function Divide-And-Conqer(N, 𝑘 min , 𝑘 max , 𝛼, 𝜋, 𝜇) 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14:

Preconditions: 1 ≤ 𝑘 min ∈ Z ≤ 𝑘 max ∈ Z ≤ |N |, 𝛼 ∈ Z ≥ 1, 𝜋 ∈ Z ≥ 1, 𝜇 ∈ Z ≥ 2 numPartitions ← |N |/𝑘 min if numPartitions · 𝑘 max < |N | then error Impossible to generate partitions minSize ← |N |/numParititons numLarger ← |N | − (minSize · numPartition) numInPart [𝑖] ← minSize + 1 ∀ 0 ≤ 𝑖 < numLarger numInPart [𝑖] ← minSize ∀ 𝑛𝑢𝑚𝐿𝑎𝑟𝑔𝑒𝑟 ≤ 𝑖 < numPartitions for 𝑖 ← 0 to 𝛼 − 1 do Assign 𝑁 to no partition ∀ 𝑁 ∈ N Divide-And-Conqer-X(N, numInPart, numPartitions, 𝜋, 𝜇) 𝑝 [𝑖] ← the current partitioning return the best partitioning out of 𝑝 [0], . . . , 𝑝 [𝛼 − 1]

15: procedure Divide-And-Conqer-X(N, numInPart, numPartitions, 𝜋, 𝜇) 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43:

numSubnets ← min (𝜇, max (numInPart [1], . . . , numInPart [numPartitions])) if numSubnets = 1 then for all partitions 𝑃 with numInPart [𝑃] = 1 do Assign a random unassigned node in N to partition 𝑃 return subnet [𝑖] ← {} ∀ 0 ≤ 𝑖 < numSubnets capacity [𝑖] ← 0 ∀ 0 ≤ 𝑖 < numSubnets nDist [𝑖] [ 𝑗] ← 0 ∀ 0 ≤ 𝑖 < numSubnets, 0 ≤ 𝑗 < numPartitions seeds ← Monte-Carlo-Partition(N, numSubnets, 𝜋) for all 𝑁 ∈ N do if ∃ 𝑖 such that seeds[𝑖] = 𝑁 then index ← 𝑖 else 𝑑 ← the minimal distance from 𝑁 to any element in seeds indices ← {𝑖 | D (𝑁 , seeds[𝑖]) = 𝑑 } index ← a uniform random element of indices Add 𝑁 to subnet [index] capacity [index] ← capacity [index] + 1 onSubnet ← 0 for onPartition ← 0 to numPartitions − 1 do for 𝑖 ← 1 to numInPart [onPartition] do while capacity [onSubnet] = 0 do onSubnet ← (onSubnet + 1) mod numSubnets nDist [onSubnet] [onPartition] ← nDist [onSubnet] [onPartition] + 1 capacity [onSubnet] ← capacity [onSubnet] − 1 onSubnet ← (onSubnet + 1) mod numSubnets for 𝑖 ← 0 to numSubnets − 1 do Divide-And-Conqer-X(subnet [𝑖], nDist [𝑖], numPartitions, 𝜋, 𝜇)

44: function Monte-Carlo-Partition(N, 𝑘, 𝜋) 45:

return the best partition of size 𝑘 on N , from 𝜋 randomly generated partitions

⊲ Integer division

⊲ Integer division ⊲ Arrays indexed from 0

20

Ryan Vogt, Ioanis Nikolaidis, and Mario A. Nascimento

Algorithm 5 The random algorithm for solving the partitioning problem 1: function Random-Partitioning(N, 𝑘 min , 𝑘 max , 𝛼)

Preconditions: 1 ≤ 𝑘 min ∈ Z ≤ 𝑘 max ∈ Z ≤ |N |, 𝛼 ∈ Z ≥ 1 numPartitions ← |N |/𝑘 min if numPartitions · 𝑘 max < |N | then error Impossible to generate partitions minSize ← |N |/numParititons numLarger ← |N | − (minSize · numPartition) numInPart [𝑖] ← minSize + 1 ∀ 0 ≤ 𝑖 < numLarger numInPart [𝑖] ← minSize ∀ 𝑛𝑢𝑚𝐿𝑎𝑟𝑔𝑒𝑟 ≤ 𝑖 < numPartitions for 𝑖 ← 1 to 𝛼 do Assign 𝑁 to no partition ∀ 𝑁 ∈ N Random-Partitioning-X(N, numInPart, numPartitions) 𝑝 [𝑖] ← the current partitioning return the best partitioning out of 𝑝 [0], . . . , 𝑝 [𝛼 − 1]

2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14:

⊲ Integer division

⊲ Integer division ⊲ Arrays indexed from 0

15: procedure Random-Partitioning-X(N, numInPart, numPartitions)

for onPartition ← 0 to numPartitions − 1 do for 𝑖 ← 1 to numInPart [onPartition] do Assign a random unassigned node in N to partition onPartition

16: 17: 18:

3

35 30

Score

25

Time (ms)

π=1 π = 10 π = 100

2

π=1 π = 10 π = 100

20 15

1 10 5

0

1

10

100

Attempts

1000

0

1

10

100

1000

Attempts

Fig. 9. The effect of the 𝛼 and 𝜋 parameters on the score and running time of the divide-and-conquer partitioning algorithm on a randomized topology.

the running time significantly, for comparably little payoff in the average quality of the partitioning found (relative to increasing 𝛼). We confirmed these results by re-running the experiment, but generating a new random topology for each trial. Each random topology was generated by placing nodes uniformly at random in a 10x10 area, measured in an arbitrary unit of length. To account for the variance in topology, we increased the number of trials for each ⟨𝛼, 𝜋⟩ pair to 5000. The results on the random topology, illustrated in Figure 9, are comparable to those seen on the grid topology. Based on these results, we recommend using a value of 𝜋 = 10, with the 𝛼 value based on both the size of the network and the necessity of a higher-scoring result (we chose to use 𝛼 = 1000 for the remainder of this section). The 𝜇 parameter is simply a safeguard for when the individual partitions in a partitioning contain a large number of nodes. If this were the case, the size of the partition used as a seed would be very large. If the seed partition is

Location-of-interest vs. Current-location Privacy in Multi-hop Communication

21

Score Time

2.0 4

10000

Score Time

1

Score

Score

10

10

Time (ms)

2

Time (ms, log-scale)

100

0

1.5

1000

3

15

1.0

5 0.5

1

Random

Brute-force

Divide-and-conquer

0.1

0.0

2

3

4

5

0

µ

Fig. 10. A comparison of the scores of the partitioning computed by three different partitioning algorithms, and the running time of each.

Fig. 11. The effect of 𝜇, the maximal partition seed size, on the final score and running time of the divide-and-conquer partitioning algorithm.

sufficiently large, relative to the size of the network (i.e., if there are a small number of large partitions), the divide-andconquer algorithm would nearly degenerate into a randomized partitioning. In most cases, the value of 𝜇 can be safely ignored (i.e., set 𝜇 = ∞). As illustrated in Figure 11, the 𝜇 parameter had no significant effect on the final score, and the individual trial run times are so variable that 𝜇 had no overall significant effect on the running time of the algorithm. We recommend using 𝜇 = 3 for safety’s sake; however, if the usage case precludes large individual partitions, the 𝜇 parameter can be entirely ignored. 7

Experimental Results in a Uniform Environment

We begin our experiments on the 𝑘-anonymity scheme in a featureless environment, devoid of any statistics learned from observing human mobility. The network is a 10x10 grid of nodes placed unit-distance apart, and for all nodes 𝑁 1 and 𝑀 in the network PG (𝐶 = 𝑁 ) = PG (𝐿 = 𝑀 | 𝐶 = 𝑁 ) = 100 . The user’s current location is chosen proportional to

PG (𝐶 = 𝑁 ) (i.e., uniformly at random, for now), the user’s real location of interest to be queried is chosen proportional to PG (𝐿 = 𝑀 | 𝐶 = 𝑁 ) (i.e., also uniformly at random for the moment), and the 𝑘 − 1 dummy queried locations are always chosen uniformly at random. Since each trial of an experiment will observe the effect on the user’s CL-privacy and LOI-privacy from a single set of 𝑘 queries being issued, we do not need to generate a partitioning of the network in the implementation of the experiment. However, it should be noted that this behaviour is equivalent to generating a uniform random partitioning, then querying a partition of size 𝑘. Because we wish to observe correlations between, e.g., AOI-privacy and CL-privacy, using a random partitioning scheme (as opposed to the partitioning scheme discussed in Section 6.2) is preferred because it gives us the widest range of results. In our first experiment, message headers between nodes are encrypted using a global key that has been compromised by the adversary. The adversary has compromised 10 of the nodes in the network, and is using them to eavesdrop on communications. The user issues 𝑘 = 3 queries into the network from their current location, and the adversary attempts to determine the user’s current location and real location of interest. Figure 12 plots the user’s resulting CL-privacy and LOI-privacy from issuing a single set of 𝑘 queries — each point on the scatterplot represents one of the 1000 trials performed. Unsurprisingly, there is a significant correlation (𝑃 < 0.0001)

22

Ryan Vogt, Ioanis Nikolaidis, and Mario A. Nascimento

between the user’s resulting LOI-privacy and CL-privacy, in that high CL-privacy is essential to achieving high LOIprivacy. After all, the more information the adversary gains from overhearing some or all of a set of 𝑘 queries, the better able the adversary is to determine both the user’s current location and location of interest. Interestingly, LOI-privacy in the featureless environment is essentially an “all or nothing” measure, in that the user achieves near-perfect LOI-privacy, i.e., approximately |Nhonest | − 1 89 = , |Nhonest | 90 or near-minimal LOI-privacy, i.e., approximately 𝑘 −1 2 = . 𝑘 3 However, the scatterplot is somewhat misleading: for example, the cluster of points in the upper-right of the graph do not all have LOI-privacy of 89 90 ; many have LOI-privacy slightly below that perfect measure. That is, the adversary was always able to deduce, even in tiny measure, locations that could not have been queried. However, in the featureless environment, there is no information for the adversary to work with regarding location popularities, significantly handicapping the adversary who is unable to overhear or deduce all of the queried locations. Of more interest to a user, however, might be what changes they can make in order to increase the privacy 1.0

of their current location and location of interest. The most 0.8

obvious change that the user can make is to adjust 𝑘, the

CL-privacy

number of queries that they send. We repeated the previous 0.6

experiment, this time adjusting 𝑘 ∈ [2, 5]. As illustrated in Figure 13, lower values of 𝑘 resulted in significantly higher

0.4

CL-privacy, as the adversary has fewer query message with 0.2

0.0 0.0

which to “triangulate” the user. On the other hand, higher values of 𝑘 resulted in significantly higher LOI-privacy, as 0.2

0.4

0.6

0.8

1.0

LOI-privacy

it becomes less likely that the adversary will guess the correct queried location as the user’s real location of interest.

Fig. 12. The user’s CL-privacy and LOI-privacy over 1000 trials with 𝑘 = 3.

Each increment of 𝑘 resulted in a significant change to both privacy metrics (𝑃 < 0.05), as determined by a oneway ANOVA test with Bonferroni’s multiple comparison

test [32] on each pair of incremental 𝑘 values (i.e., from 𝑘 = 2 to 𝑘 = 3, from 𝑘 = 3 to 𝑘 = 4, and from 𝑘 = 4 to 𝑘 = 5), thus indicating a clear trade-off between the user’s ability to protect the privacy of their current location and the privacy of their location of interest. Another parameter within the user’s control is their AOI-privacy, which is determined by how well-dispersed their 𝑘 queries are physically around the network. Figure 14 shows the user’s CL- and LOI-privacy, relative to their chosen AOI-privacy over 1000 trials. While there is a significant correlation (𝑃 < 0.0001) between between the user’s AOI-privacy and their LOI-privacy, it is not large (𝑅 2 = 0.0158). While that may seem surprising, given that the two are conceptually similar measures of how well protected the identity of the user’s real query destination is, that lack of large correlation just indicates that how physically spread out the 𝑘 destinations are is not the most important factor in helping the adversary narrow down the real location of interest. There is also no large correlation (𝑃 < 0.01, 𝑅 2 < 0.01) between a user’s AOI-privacy and their CL-privacy. Intuitively, one might think that the more dispersed the 𝑘 queries

1.0

1.0

0.8

0.8

LOI-privacy

CL-privacy

Location-of-interest vs. Current-location Privacy in Multi-hop Communication

0.6

0.4

0.2

0.0 0.0

23

0.6

0.4

0.2

0.2

0.4

0.6

0.8

0.0 0.0

1.0

0.2

0.4

AOI-privacy

0.6

0.8

1.0

AOI-privacy

Fig. 14. The user’s CL-privacy and LOI-privacy, as the user’s AOI-privacy is varied, over 1000 trials with 𝑘 = 3.

are, the more opportunity there would be for the adversary to overhear queries and triangulate the user’s location. While that is probabilistically true, as indicated by the low 𝑃 value, it is not a largely meaningful factor to the adversary, as indicated by the low 𝑅 2 value. To confirm these results, we studied a metric related to AOI-privacy, more closely related to the number of opportu1.0

nities the adversary will have to intercept user queries. That 0.8

take (i.e., the number of query message transmissions between unique pairs of nodes), which the user is able to control based on the chosen nodes to query. Figure 15 shows

Privacy measure

metric is the number of unique hops the user’s 𝑘 queries

k=2 k=3 k=4 k=5

0.6

0.4

the user’s CL- and LOI-privacy, relative to the number of 0.2

distinct hops taken by their query messages over 1000 trials. Again, the number of distinct hops taken by the user’s

0.0

CL-privacy

LOI-privacy

queries is significantly negatively correlated with both the user’s resulting CL-privacy (𝑃 = 0.0097) and their resulting LOI-privacy (𝑃 < 0.0001). However, once again, the 𝑅 2

Fig. 13. The user’s CL-privacy and LOI-privacy, as the number of queries 𝑘 is varied, over 1000 trials.

values are low: 𝑅 2 = 0.0067 and 𝑅 2 = 0.0318 respectively. In other words, the user’s control over how dispersed their queries are will, probabilistically, influence their CL- and LOI-privacy, but blind luck based on query routing near compromised nodes is a much more important factor. There are numerous other factors, potentially beyond the control of users of the network, that affect the adversary’s success as well. One critical factor for the adversary is how many nodes are compromised in the network. The more nodes that are compromised, the more likely it is that the adversary will be able to intercept queries, learning the locations queried and facilitating the computation of the user’s current location. This result is depicted in Figure 16, showing the predictable result that increasing the number of nodes compromised by the adversary decreases both the user’s CL- and LOI-privacy. Note, however, that Figure 16 illustrates the same trend first illustrated in Figure 13: increasing the privacy constant 𝑘 — a constant that is entirely under the control of the user — decreases the user’s

Ryan Vogt, Ioanis Nikolaidis, and Mario A. Nascimento

1.0

1.0

0.8

0.8

LOI-privacy

CL-privacy

24

0.6

0.4

0.2

0.0

0.6

0.4

0.2

0

10

20

30

0.0

40

0

10

20

Distinct hops

30

40

Distinct hops

Fig. 15. The user’s CL-privacy and LOI-privacy, as the number of distinct hops in the queries issued by the user is varied, over 1000 trials with 𝑘 = 3.

1.0

1.0

0.8

1 compromised 3 compromised 5 compromised 10 compromised 15 compromised

0.6

0.4

0.2

0.0

LOI-privacy

CL-privacy

0.8

1 compromised 3 compromised 5 compromised 10 compromised 15 compromised

0.6

0.4

0.2

2

3

4

5

k

0.0

2

3

4

5

k

Fig. 16. The user’s CL-privacy and LOI-privacy, as the number of nodes compromised by the adversary varies, over 1000 trials.

CL-privacy but increases the user’s LOI-privacy, illustrating the trade-off between a user protecting the privacy of their current location and that of their location of interest. A property that may or may not be under the control of the user is the type of encryption used in communication between nodes. Recall that the query proper can be encrypted end-to-end between the user and the queried node using any number of available cryptographic techniques. The query itself is not at issue. The issue at hand is what information the adversary can glean from decrypting the information contained in the headers of overheard messages. So far, we have assumed that transmissions between the nodes in the network are encrypted using a global key. Should any node be compromised, the adversary learns the global key; then, if any query transmission is overheard, the adversary learns the destination of that query, as well as two nodes along the path to that destination (the transmitter and the intended recipient of the transmission). However, it is possible that transmissions between nodes are encrypted using link keys — that is, every pair of nodes in transmission range of each other share a unique symmetric key. In this case, an overheard query per se reveals to the adversary only a single node — the transmitter — in the path from the user’s current location to the queried location (we must assume that the adversary can determine which node transmitted the query based on metrics such as signal strength, timing, etc. [3]). It is only if a compromised node is the recipient of the transmission that the adversary learns the ultimate destination of the query (and, obviously, the recipient of the transmission). A comparison of the user’s CL- and LOI-privacy based on whether global keys or link keys are used is

1.0

1.0

0.8

0.8

0.6

Global key Link keys No broadcast

0.4

0.2

0.0

LOI-privacy

CL-privacy

Location-of-interest vs. Current-location Privacy in Multi-hop Communication

25

0.6

Global key Link keys No broadcast

0.4

0.2

2

3

4

5

0.0

2

k

3

4

5

k

Fig. 17. The user’s CL-privacy and LOI-privacy, as the type of broadcast encryption varies, over 1000 trials.

illustrated in Figure 17; for the purposes of comparison, an environment in which there is no broadcast transmission (e.g., optical or wired communication [42]), and thus the adversary learns nothing unless a compromised node is the recipient or transmitter of a message, is also included. Each increase in “broadcast security” resulted in a significant increase (𝑃 < 0.05) to the user’s CL-privacy, as determined by a one-way ANOVA test with Bonferroni’s multiple comparison test on each incremental pair (i.e., from a global key to link keys, and from link keys to a non-broadcast environment). The first increment illustrates the value to the adversary of being able to learn more nodes along the communication path and the ultimate destination of the communication, for the purposes of inferring from where the initial query could have come. The second increment illustrates the ultimate value to the adversary of overhearing anything at all. On the other hand, the first increment in “broadcast security” resulted in a significant increase to the user’s LOI-privacy (𝑃 < 0.05), but the move from link keys to a non-broadcast environment did not (𝑃 > 0.10). In other words, being able to decipher the ultimate destination of an overheard query that a compromised node is not routing is helpful to an adversary in determining the user’s location of interest, but an overheard query where the adversary cannot decrypt the final destination is practically meaningless towards that goal. Similar to the type of encryption used in the network, the type of routing used also may or may not be under the control of the user. Here we compare the two types of routing described in Section 4.1: fixed shortest-path and random shortest-path routing. In both cases, a query sent from the user’s current location to the query destination will arrive in the fewest number of hops possible; however, in fixed shortest-path routing, a query sent between those two locations will always take the same path, whereas in random shortest path routing it could potentially take many different paths. The results are illustrated in Figure 18. Switching to random shortest-path routing significantly improved the user’s CL-privacy, as the adversary could not ascertain the origin of a query as easily from an overheard message. Obviously, when using a global encryption key, the type of routing used had no effect on the user’s LOI-privacy. However, the question remains: if link keys were used instead of a global key, creating a situation in which the adversary could overhear query messages but not learn their destination, would implementing random shortest-path routing increase the user’s LOI-privacy by making it more difficult for the adversary to narrow down possible destinations for overheard messages? We repeated the previous experiment, this time using link keys; the results are presented in Figure 19. Again, there was no distinction between the LOI-privacy results whether fixed shortest-path or random shortest-path routing were used — in essence, being able to easily guess potential destinations for overheard but non-decrypted packets is not highly important to the adversary.

26

Ryan Vogt, Ioanis Nikolaidis, and Mario A. Nascimento

1.0

1.0

Fixed shortest path Random shortest path

0.8

LOI-privacy

CL-privacy

0.8

0.6

0.4

0.6

0.4

0.2

0.2

0.0

Fixed shortest path Random shortest path

2

3

4

0.0

5

2

3

4

5

k

k

Fig. 18. The user’s CL-privacy and LOI-privacy, as the routing algorithm used in the network varies, over 1000 trials with a global key.

1.0

1.0

Fixed shortest path Random shortest path

0.8

LOI-privacy

CL-privacy

0.8

0.6

0.4

0.6

0.4

0.2

0.2

0.0

Fixed shortest path Random shortest path

2

3

4

0.0

5

2

3

4

5

k

k

Fig. 19. The user’s CL-privacy and LOI-privacy, as the routing algorithm used in the network varies, over 1000 trials with link keys.

8

Experimental Results with Mobility

Until now, we have run experiments in a uniform, featureless environment, in which for all nodes 𝑁 and 𝑀 in the network PG (𝐶 = 𝑁 ) = PG (𝐿 = 𝑀 | 𝐶 = 𝑁 ) = | N1 | . However, for a real network in an urban environment, some nodes will be located at more population locations than other nodes. To generate such a rich environment, we use DBS3 [37] as the mobility simulator and the maps of part of downtown Edmonton, Canada and of Fira, Greece shown in Figures 20 and 21. The two maps are, respectively, a highly organized grid, and a more organic pattern evolved from terrain constraints. We placed nodes centred on both maps in a grid pattern with 100 m spacing, yielding 112 nodes on the Edmonton map and 84 nodes on the Fira map. On both maps, we initialized a 10-million-agent simulation, and computed the closest node to each agent. We then set PG (𝐶 = 𝑁 ) =

𝜈 0 (𝑁 ) 10000000

for each 𝑁 ∈ N , where 𝜈 0 (𝑁 ) is the number of agents for whom 𝑁 is the closest node at time zero. We also set PG (𝐿 = 𝑀 | 𝐶 = 𝑁 ) = PG (𝐶 = 𝑀) for each 𝑀 ∈ N . In other words, the probability that a node is either the current location or the location of interest is proportional to the amount of pedestrian traffic near it. As before, the user’s current

Location-of-interest vs. Current-location Privacy in Multi-hop Communication

27

location is chosen proportional to PG (𝐶 = 𝑁 ), the user’s real location of interest to be queried is chosen proportional to PG (𝐿 = 𝑀 | 𝐶 = 𝑁 ), and the 𝑘 − 1 dummy queried locations are chosen uniformly at random. partitioning scheme).

Fig. 20. The map of downtown Edmonton. Fig. 21. The map of Fira.

To determine how beneficial this statistical data is to an adversary, we compared the statistically rich environments of Edmonton and Fira to otherwise equivalent environments in which PG (𝐶 = 𝑁 ) = PG (𝐿 = 𝑀 | 𝐶 = 𝑁 ) = | N1 | for all nodes 𝑁 , 𝑀 ∈ N . As in the previous section, message headers between nodes are encrypted using a global key that has been compromised by the adversary. The adversary has compromised 10 of the nodes in the network, and is using them to eavesdrop on communications. The user issues queries into the network from their current location, and the adversary attempts to determine the user’s current location and real location of interest. Because of the higher variance LOI-privacy results in the statistically rich environment, we increased the number of trials from 1000 (used in the previous section) to 5000. The results of this experiment are illustrated for the Edmonton map in Figure 22 and for the Fira map in Figure 23. As evident from those graphs, both the user’s CL- and LOI-privacy fell considerably when this additional statistical data was available to the adversary. Notably, LOI-privacy was more seriously affected than CL-privacy by this additional information, because the random partitioning scheme potentially resulted in low-probability LOIs being grouped with the user’s real LOI. Also, note that both privacy measures were affected more seriously in Fira, which is more complex from a Space Syntax standpoint, and has more popular central thoroughfares.

1.0

1.0

0.8

LOI-privacy

CL-privacy

0.6

0.4

0.2

0.0

Uniform Mobility-biased

Uniform Mobility-biased

0.8

0.6

0.4

0.2

2

3

4

k

5

0.0

2

3

4

5

k

Fig. 22. The user’s CL-privacy and LOI-privacy, in statistically rich versus uniform environments, over 5000 trials in Edmonton.

28

Ryan Vogt, Ioanis Nikolaidis, and Mario A. Nascimento

1.0

1.0

0.8

LOI-privacy

0.8

CL-privacy

Uniform Mobility-biased

Uniform Mobility-biased

0.6

0.4

0.2

0.0

0.6

0.4

0.2

2

3

4

0.0

5

2

k

3

4

5

k

Fig. 23. The user’s CL-privacy and LOI-privacy, in the statistically rich versus uniform environments, over 5000 trials in Fira.

Another situation that could possibly benefit the adversary is if the adversary knows that the user is walking from their current location to their location of interest in the near future. In this way, the user’s current location would affect the probabilities that the various nodes in the network are the user’s real location of interest, i.e., PG (𝐿 = 𝑀 | 𝐶 = 𝑁 ) for 𝑁 , 𝑀 ∈ N . To generate this even richer world, we advanced the 10-million-agent simulation to some time 𝑡 ≥ 0. Keeping PG (𝐶 = 𝑁 ) =

𝜈 0 (𝑁 ) , 10000000

we now set 𝜈𝑡 (𝑁 , 𝑀) 𝜈 0 (𝑁 ) for each 𝑁 , 𝑀 ∈ N , where 𝜈𝑡 (𝑁 , 𝑀) is the number of agents for whom 𝑁 is the closest node at time zero and 𝑀 is the PG (𝐿 = 𝑀 | 𝐶 = 𝑁 ) =

closest node at time 𝑡. To motivate that this additional short-time-horizon information could assist the adversary, consider an adversary who, in the absence of any network communication, wants to predict the user’s location at some time 𝑡 ≥ 0. Lacking any information about the user to utilize, the adversary would just guess the most popular location on the map is the user’s location, guessing successfully with probability max𝑁 ∈ N PG (𝐶 = 𝑁 ). Compare that adversary to one who wants to predict the user’s location at time 𝑡 ≥ 0, but also has access to an oracle that reveals the user’s location at time 𝑡 = 0. Such an adversary could successfully predict that user’s location with probability  ∑︁  PG (𝐶 = 𝑁 ) · max PG (𝐿 = 𝑀 | 𝐶 = 𝑁 ) . 𝑁 ∈N

𝑀∈N

These two adversaries are compared on the Edmonton map in Figure 24 and on the Fira map in Figure 25. The more complex Fira map with few thoroughfares leads to a higher baseline success rate for the adversary without an oracle than in Edmonton, and the natural inclination of pedestrians to move towards and stay on those thoroughfares results in the oracle-possessing adversary’s success rate declining towards the baseline more quickly than in Edmonton. However, in either case, the adversary with the oracle has a clear advantage over the adversary without the oracle up to a time threshold of 𝑡 ≈ 10–15 (where 𝑡 is measured in minutes). To further investigate this concept of a time threshold, we reran the previous 𝑘-query experiment on the Edmonton and Fira maps. This time, however, we assumed that the user is travelling from their current location to their location

Location-of-interest vs. Current-location Privacy in Multi-hop Communication

1.0

Probability of guessing user's location

Probability of guessing user's location

1.0

0.8

If location at time 0 is known If no location is known 0.6

0.4

0.2

0.0

29

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

0.8

If location at time 0 is known If no location is known 0.6

0.4

0.2

0.0

15

0

1

2

3

4

5

Time (minutes)

Fig. 24. The success rate of an adversary predicting a user’s location at time 𝑡 ≥ 0 with and without an oracle revealing the user’s location at time 𝑡 = 0, in Edmonton.

1.0

8

9

10

11

12

13

14

15

1.0

k=2 k=3 k=4 k=5

0.8

LOI-privacy

CL-privacy

7

Fig. 25. The success rate of an adversary predicting a user’s location at time 𝑡 ≥ 0 with and without an oracle revealing the user’s location at time 𝑡 = 0, in Fira.

k=2 k=3 k=4 k=5

0.8

0.6

0.4

0.2

0.0

6

Time (minutes)

0.6

0.4

0.2

0

1

2

3

4

5

6

7

8

9

Time (minutes)

10

11

12

13

14

15

0.0

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

Time (minutes)

Fig. 26. The user’s CL-privacy and LOI-privacy, when the user queries their location of interest at varying times before arriving at it, over 5000 trials in Edmonton.

of interest — i.e., we used the richer definition of PG (𝐿 = 𝑀 | 𝐶 = 𝑁 ), for some chosen time threshold 𝑡 between when the user sends their 𝑘 queries and when they arrive at their real location of interest. The resulting CL- and LOI-privacy for the user in Edmonton, over varying time thresholds, is illustrated in Figure 26; the results of the same experiment in Fira are in Figure 27. Counter-intuitively, for small 𝑡 values, the user’s CL-privacy is higher than at larger 𝑡 values. Consider the case where, for 𝑡 = 0, one of the queried locations is guaranteed to be the user’s current location, effectively decrementing 𝑘 from the point of view of the adversary’s ability to intercept the user’s messages. Assuming that the user’s CL-privacy has plateaued by 𝑡 = 15 (based on the oracle experiment), we performed a one-way ANOVA test with Bonferroni’s multiple comparison test between the user’s CL-privacy at 𝑡 = 15 and each previous time (i.e., comparing 𝑡 = 0 to 𝑡 = 15, 𝑡 = 1 to 𝑡 = 15, etc.). In Edmonton using 𝑘 = 3, there was no significant difference (𝑃 > 0.05) in the CL-privacy at any time 4 ≤ 𝑡 ≤ 14 and the CL-privacy at 𝑡 = 15. Similarly, in Fira using 𝑘 = 3, there was no significant difference (𝑃 > 0.05) in the CL-privacy at time 3 ≤ 𝑡 ≤ 14 and the CL-privacy at 𝑡 = 15. Based on these results, we conclude that any benefit

30

Ryan Vogt, Ioanis Nikolaidis, and Mario A. Nascimento

1.0

0.6

0.4

0.2

0.0

k=2 k=3 k=4 k=5

0.8

LOI-privacy

0.8

CL-privacy

1.0

k=2 k=3 k=4 k=5

0.6

0.4

0.2

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

0.0

Time (minutes)

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

Time (minutes)

Fig. 27. The user’s CL-privacy and LOI-privacy, when the user queries their location of interest at varying times before arriving at it, over 5000 trials in Fira.

to the user’s CL-privacy from a small 𝑡 threshold from query to arrival has vanished by 4 and 3 minutes respectively on the Edmonton and Fira maps when 𝑘 = 3. Regarding the LOI-privacy results, recall from Section 7 the fundamental trade-off between the privacy of the user’s current location and that of their location of interest: as 𝑘 increases, the user’s LOI-privacy increases at the cost of their CL-privacy. However, recall Lemma 4.2, which states that when the adversary knows the user’s current location is their real location of interest (e.g., in this experiment when 𝑡 = 0), the resulting CL- and LOI-privacies are identical. This apparent paradox is visible in the LOI-privacy graphs wherein the lines representing the various 𝑘 values cross as 𝑡 increases, before plateauing. These graphs tell us that, when the adversary knows that the user’s real LOI is at or near their current location, the LOI-privacy metric is really measuring the privacy of the user’s current location. Similar to the ANOVA and Bonferroni results on CL-privacy, there was no significant difference (𝑃 > 0.05) between the user’s LOI-privacy at any time 10 ≤ 𝑡 ≤ 14 and at time 𝑡 = 15 in Edmonton using 𝑘 = 3; the same holds true in Fira using 𝑘 = 3 for any time 6 ≤ 𝑡 ≤ 14. From these results, we can conclude that if a user is travelling from their current location to their real location of interest, they should send their 𝑘 queries long enough in advance of embarking to mitigate any advantage the adversary has in predicting the user’s real LOI. How long is “long enough” will depend on the map in question and the number of queries sent. However, “long enough” in our experiments was a surprisingly short period of time for movement at pedestrian mobility speeds, e.g., a mere 𝑡 = 10 minutes when using 𝑘 = 3 on the Edmonton map. 9

Conclusions

In this paper, we presented a user-controlled methodology for preserving the privacy of the user’s location of interest in a wireless multi-hop network: issuing 𝑘 queries instead of just one. This methodology does not require any special security measures in the network itself (as opposed to, e.g., onion routing). There is a direct trade-off between preserving the privacy of the user’s location of interest and the privacy of their current location, controlled by the user’s choice of the security constant 𝑘, i.e., the number of queries sent by the user. The presence of user mobility data, reflecting the popularity of different locations, gives the adversary a significant advantage in determining a user’s current location and location of interest, relative to an adversary operating in a featureless, uniform environment. It is even more difficult for users moving from their current location to their location

Location-of-interest vs. Current-location Privacy in Multi-hop Communication

31

of interest to preserve their privacy; however, those users can mitigate this advantage of the adversary by leaving a long enough time between their query and their arrival at the location of interest. Future work on this scheme should seek network partitioning schemes that yield guarantees of area-of-interest privacy and/or location-of-interest privacy while still satisfying the closure requirement. In particular, satisfying the closure condition in the presence of unequal location popularities will be a substantial challenge. Acknowledgments This work was supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery Grant program. Ryan Vogt was also supported by an Alberta Innovates / iCore scholarship. References [1] Christer Andersson, Leonardo A. Martucci, and Simone Fischer-Hübner. 2005. Requirements for Privacy-Enhancements in Mobile Ad Hoc Networks. In Proceedings of the 3rd German Workshop on Mobile Ad-Hoc Networks. [2] Lenore Blum, Manuel Blum, and Michael Shub. 1986. A Simple Unpredictable Pseudo-Random Number Generator. SIAM J. Comput. 15, 2 (May 1986), 364–383. [3] Mohamed Salah Bouassida, Gilles Guette, Mohamed Shawky, and Bertrand Ducourthial. 2009. Sybil Nodes Detection Based on Received Signal Strength Variations within VANET. International Journal of Network Security 9, 1 (July 2009), 22–33. [4] John Bryson and Patrick Gallagher. 2012. Secure Hash Standard (SHS). FIPS 180-4. [5] Lily Chen. 2009. Recommendation for Key Derivation Using Pseudorandom Functions (Revised). NIST Special Publication 800-108. [6] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2001. Introduction to Algorithms (second ed.). The MIT Press. [7] Karim El Defrawy and Gene Tsudik. 2007. ALARM: Anonymous location-aided routing in suspicious MANETs. In Proceedings of the IEEE International Conference on Network Protocols (ICNP). 304–313. doi:10.1109/ICNP.2007.4375857 [8] Roger Dingledine, Nick Mathewson, and Paul Syverson. 2004. Tor: The Second-Generation Onion Router. In Proceedings of the 13th USENIX Security Symposium. 303–320. [9] Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York. [10] Buğra Gedik and Ling Liu. 2004. A Customizable 𝑘 -Anonymity Model for Protecting Location Privacy. In The 24th International Conference on Distributed Computing Systems. 620–629. [11] David Goldschlag, Michael Reed, and Paul Syverson. 1999. Onion Routing. Commun. ACM 42, 2 (February 1999), 39–41. ˜ Graham. 1972. An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set. Inform. Process. Lett. 1 (1972), 132–133. [12] R.L. [13] Marco Gruteser and Dirk Grunwald. 2003. Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking. In Proceedings of the 1st international conference on mobile systems, applications and services. [14] Chen Gu, Matthew Bradbury, Arshad Jhumka, and Matthew Leeke. 2015. Assessing the performance of phantom routing on source location privacy in wireless sensor networks. In Proceedings of the IEEE Pacific Rim International Symposium on Dependable Computing (PRDC). 99–108. doi:10.1109/PRDC.2015.9 [15] Sariel Har-Peled and Anastasios Sidiropoulos. 2013. Clustering problem. Private communication. [16] Xiaoyan Hong, Jiejun Kong, and Mario Gerla. 2006. Mobility changes anonymity: new passive threats in mobile ad hoc networks. Wireless Communications and Mobile Computing 6 (2006), 281–293. [17] Jerzy W. Jaromczyk and Pawel Gburzynski. 2012. Pozdrowienia z Ciechanowa. Private communication. [18] Ying Jian, Shigang Chen, Zhan Zhang, and Liang Zhang. 2007. Protecting Receiver-Location Privacy in Wireless Sensor Networks. In Proceedings of the 26th IEEE International Conference on Computer Communications. 1955–1963. [19] David S. Johnson. 1982. The NP-Completeness Column: An Ongoing Guide. Journal of Algorithms 3 (1982), 182–195. [20] Pandurang Kamat, Yanyong Zhang, Wade Trappe, and Celal Ozturk. 2005. Enhancing Source-Location Privacy in Sensor Network Routing. In Proceedings of the 25th IEEE International Conference on Distributed Computing Systems. 599–608. [21] Richard M. Karp. 1972. Reducibility Among Combinatorial Problems. In Complexity of Computer Computations: Proceedings of a Symposium on the Complexity of Computer Computations, Raymond Edward Miller and James W. Thatcher (Eds.). Plenum Press, New York, 85–103. [22] Hidetoshi Kido, Yutaka Yanagisawa, and Tetsuji Satoh. 2005. An anonymous communication technique using dummies for location-based services. In Proceedings of the IEEE International Conference on Pervasive Services (ICPS). 88–97. doi:10.1109/PERSER.2005.1506394 [23] Yunzhong Liu, Rui Zhang, Jing Shi, and Yanchao Zhang. 2010. Traffic inference in anonymous MANETs. In Proceedings of the IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON). 1–9. doi:10.1109/SECON.2010.5508238 [24] Satyajayant Misra and Guoliang Xue. 2006. Efficient anonymity schemes for clustered wireless sensor networks. International Journal of Sensor Networks 1, 1/2 (2006), 50–63.

32

Ryan Vogt, Ioanis Nikolaidis, and Mario A. Nascimento

[25] Ben Niu, Qinghua Li, Xiaoyan Zhu, Guohong Cao, and Hui Li. 2014. Achieving 𝑘 -anonymity in privacy-aware location-based services. In Proceedings of the IEEE Conference on Computer Communications (INFOCOM). 754–762. doi:10.1109/INFOCOM.2014.6848002 [26] Yi Ouyang, Zhengyi Le, Yurong Xu, Nikos Triandopoulos, Sheng Zhang, James Ford, and Fillia Makedon. 2007. Providing Anonymity in Wireless Sensor Networks. In Proceedings of the IEEE International Conference on Pervasive Services. 145–148. [27] Celal Ozturk, Yanyong Zhang, and Wade Trappe. 2004. Source-location privacy in energy-constrained sensor network routing. In Proceedings of the 2nd ACM Workshop on Security of Ad Hoc and Sensor Networks. 88–93. [28] Pedro C. Pinto, João Barros, and Moe Z. Win. 2011. Wireless Secrecy in Large-Scale Networks. arXiv:1102.3617 [cs.IT]. ˜ Ravi, D.J. ˜ Rosenkrantz, and G.K. ˜ Tayi. 1994. Heuristic and Special Case Algorithms for Dispersion Problems. Operations Research 42, 2 [29] S.S. (March-April 1994), 299–310. ˜ [30] Capt. Ross E.Roley. 1985. Spacing Points in a Three Dimensional Convex Region for Maximum Separation: a Color-Space Application. Master’s thesis. Air Force Aerospace Medical Research Laboratory. [31] Thomas J. Schaefer. 1974. Private communication with a third-party, recited. [32] GraphPad Software. 2013. GraphPad Statistics Guide: the Bonferroni method. http://www.graphpad.com/guides/prism/6/statistics/index.htm?stat_ the_bonferroni_method.htm. [33] Paul G. Spirakis. 1983. Very Fast Algorithms for the Area of the Union of Many Circles. Technical Report 98. New York University. [34] Latanya Sweeney. 2002. 𝑘 -Anonymity: A Model for Protecting Privacy. International Journal on Uncertainty, Fuzziness and Knowledge-Based Systems 10, 5 (2002), 557–570. [35] Arie Tamir. 1991. Obnoxious Facility Location on Graphs. Society for Industrial and Applied Mathematics Journal on Discrete Mathematics 4, 4 (November 1991), 550–567. [36] Godfried Toussaint. 1983. Solving geometric problems with the rotating calipers. In Proceedings of IEEE MELECON’83. [37] Ryan Vogt, Ioanis Nikolaidis, and Pawel Gburzynski. 2012. A realistic outdoor urban pedestrian mobility model. Simulation Modelling Practice and Theory 26 (2012), 113–134. doi:10.1016/j.simpat.2012.04.006 [38] D.W. Wang and Yue-Sun Kuo. 1988. A Study on Two Geometric Location Problems. Inform. Process. Lett. 29 (1988), 281–286. [39] Stephen B. Wicker. 2012. The Loss of Location Privacy in the Cellular Age. Commun. ACM 55, 8 (August 2012), 60–68. [40] Di Wu, Yu Zhang, and Yinlong Liu. 2017. Dummy location selection scheme for 𝑘 -anonymity in location based services. In Proceedings of the IEEE Trustcom/BigDataSE/ICESS. 441–448. doi:10.1109/Trustcom/BigDataSE/ICESS.2017.269 [41] Yi Yang, Sencun Zhu, Guohong Cao, and Thomas LaPorta. 2009. An Active Global Attack Model for Sensor Source Location Privacy: Analysis and Countermeasures. Security and Privacy in Communication Networks 19 (2009), 373–393. [42] Jennifer Yick, Biswanath Mukherjee, and Dipak Ghosal. 2008. Wireless Sensor Network Survey. Computer Networks 52, 12 (August 2008), 2292–2330. [43] Lisa Zyga. 2013. Study shows how easy it is to determine someone’s identity with cell phone data. http://phys.org/news/2013-03-easy-identitycell.html.

A

NP-completeness Proofs Theorem A.1. Partition-Graph is NP-complete. Proof. First, we show that Partition-Graph is in NP. Consider a candidate solution. The distance between any two

vertices in the candidate solution could be established by, e.g., O (𝑘) breadth-first searches, each running in polynomial time and space. The candidate solution could then be verified by checking the distance between all pairs of vertices in the solution, requiring O (𝑘 2 ) distance lookups. Next, we perform the Turing reduction. Let A(𝐺, 𝑘, 𝑑) be an algorithm that solves Partition-Graph (i.e., returns either True or False). Now, consider the following problem: Independent-Set: You are given a graph 𝐺 = ⟨𝑉 , 𝐸⟩, 𝑘 ∈ Z ≤ |𝑉 |. Is there a subset 𝑆 ⊆ 𝑉 with |𝑆 | ≥ 𝑘 such that no two vertices in 𝑆 are joined by an edge in 𝐸? Independent-Set is known to be NP-complete [21]. Note that an independent set of size 𝑘 is equivalent to a partition of size 𝑘 with a distance of at least two hops between all pairs of vertices in the partition. Therefore, an instance ⟨𝐺, 𝑘⟩ of Independent-Set can be solved with a single call to the Partition-Graph solver, A(𝐺, 𝑘, 2).

□

Theorem A.2. Partitioning-Graph is NP-complete. Proof. First, we show that Partitioning-Graph is in NP. Consider a candidate solution. The distance between any two vertices in the graph could be established by, e.g., O (|𝑉 |) breadth-first searches, each running in polynomial time

Location-of-interest vs. Current-location Privacy in Multi-hop Communication

33

and space. The candidate solution could then be verified by checking the distance between all pairs of vertices in the same partition in the solution, requiring O (|𝑉 | 2 ) distance lookups. Next, we perform the Turing reduction. Let A(𝐺, 𝑘 min, 𝑘 max , 𝑑) be an algorithm that solves Partitioning-Graph (i.e., returns either True or False). Now, consider the following problem: Partition-Into-Triangles: You are given a graph 𝐺 = ⟨𝑉 , 𝐸⟩ where |𝑉 | = 3𝑞 for some 𝑞 ∈ Z. Can 𝑉 be partitioned into disjoint sets 𝑉1, . . . , 𝑉𝑞 , where |𝑉𝑖 | = 3 and 𝑉𝑖 forms a clique, for all 𝑖? Partition-Into-Triangles is known to be NP-complete [9, 31]. Given an instance ⟨𝐺⟩ of Partition-Into-Triangles, first construct the complement graph, 𝐺 ′ = ⟨𝑉 , 𝐸 ′ ⟩, in which two vertices are connected by an edge if and only if they were not connected by an edge in 𝐺. Note that 𝑉 on 𝐺 can be partitioned into disjoint sets 𝑉𝑖 with |𝑉𝑖 | = 3 that all form cliques, if and only if 𝑉 on 𝐺 ′ can be partitioned into disjoint sets 𝑉𝑖 with |𝑉𝑖 | = 3 that all form independent sets. Having no edges connecting the three nodes is equivalent to them being a partition of size three with a distance of at least two hops between all pairs of vertices in the partition. Therefore, calling the Partitioning-Graph solver a single time, A(𝐺 ′, 3, 3, 2), yields the solution to a Partition-Into-Triangles instance ⟨𝐺⟩.

B

□

Proofs of Lemmas and Theorems Proof of Lemma 4.1. If there is no way to choose a unique integer from each of S1, . . . , S𝑚 (including if S𝑖 = ∅ for

′ = ∅, and we are done. Assume there is a way to choose 𝑚 unique integers, one from each of the S any 𝑖), then G𝑚 𝑖

(which implies that S𝑖 ≠ ∅ for all 𝑖). The proof will be by induction on 𝑚 ∈ Z ≥ 1. ′ = {{𝑠} | 𝑠 ∈ S }, because {𝑠} is a sampling if and only if 𝑠 ∈ S . As such, If 𝑚 = 1, then G𝑚 1 1 Ø Ø Ø {𝑠} = S1 = G𝑚 = S𝑖 . ′ G𝑚 ∈ G𝑚

1≤𝑖 ≤𝑚

𝑠 ∈ S1

Assume for 𝑗 ∈ Z ≥ 1, Ø G 𝑗 ∈ G 𝑗′

G𝑗 =

Ø

S𝑖 ,

1≤𝑖 ≤ 𝑗

and let S 𝑗+1 ⊆ Z be another set of integers. If it is not possible to choose 𝑗 + 1 unique integers, one from each of ′ S1, . . . , S 𝑗+1 , then G𝑗+1 = ∅ and we are done. Assume it is possible to choose 𝑗 + 1 unique integers as described above.

If there are any elements 𝑒 ∈ S 𝑗+1 that are not contained in ∪1≤𝑖 ≤ 𝑗 S𝑖 , then a sampling G𝑗+1 could be constructed as G𝑗+1 = G𝑗 ∪ {𝑒}, for any sampling G𝑗 on S1, . . . , S 𝑗 . Hence, Ø G𝑗+1 = G 𝑗 +1 ∈ G 𝑗′ +1

Ø

S𝑖 ,

1≤𝑖 ≤ 𝑗+1

because there is guaranteed to be a sampling G𝑗+1 that contains any element of S 𝑗+1 not contained in ∪1≤𝑖 ≤ 𝑗 S𝑖 .

□

34

Ryan Vogt, Ioanis Nikolaidis, and Mario A. Nascimento Proof of Lemma 4.2. First, note that if PG (𝐿 = 𝑁 | 𝐶 = 𝑀) is as defined, then  PG (𝐿 = 𝑀 | 𝐶 = 𝑁 ) · 𝜒 (𝑁 , 𝑀)   if 𝑀 ∈ L𝑁 Í  𝑃 ∈ L𝑁 PG (𝐿 = 𝑃 | 𝐶 = 𝑁 ) · 𝜒 (𝑁 , 𝑃) 𝜙 (𝑁 , 𝑀) =   0 𝑖 𝑓 𝑀 ∉ L𝑁   1 · 𝜒 (𝑁 , 𝑀)   Í if 𝑀 ∈ L𝑁 and 𝑁 = 𝑀   1 · 𝜒 (𝑁 , 𝑀) + 𝑃 ∈ L𝑁 \{𝑀 } 0 · 𝜒 (𝑁 , 𝑃) =   0 otherwise  =

   1 if 𝑀 ∈ L𝑁 and 𝑁 = 𝑀    0 otherwise. 

We can further simplify 𝜙 by noting that if 𝑁 = 𝑀, then under our assumption about PG (𝐿 = 𝑁 | 𝐶 = 𝑀) (which implies one of the 𝑘 queried locations will always be the user’s current location), it is guaranteed that 𝑀 ∈ L𝑁 . If the adversary has compromised the user’s current location 𝐶, the adversary would process the query directed to the real location of interest (i.e., 𝐶) and add 𝐶 to L𝐶 . If the adversary has not compromised the user’s current location, then the adversary would not overhear all of the user’s 𝑘 queries, and would, for any possible current location 𝑁 , add 𝑁 to L𝑁 , since a query to a non-compromised current location always represents a possible assignment of a destination to a query with an unknown destination. As such,    1 if 𝑁 = 𝑀  𝜙 (𝑁 , 𝑀) =   0 otherwise.  Using the simplified form of 𝜙, we can simplify 𝜔 as well: ∑︁ 𝜔 (𝑀) = 𝜓 (𝑁 , 𝑀) 𝑁 ∈C

=

∑︁

PG (𝐶 = 𝑁 | 𝐶 ∈ C) · 𝜙 (𝑁 , 𝑀)

𝑁 ∈C

Í    PG (𝐶 = 𝑀 | 𝐶 ∈ C) · 1 + 𝑁 ∈ C\{𝑀 } PG (𝐶 = 𝑁 | 𝐶 ∈ C) · 0  = Í   𝑁 ∈ C PG (𝐶 = 𝑁 | 𝐶 ∈ C) · 0     PG (𝐶 = 𝑀 | 𝐶 ∈ C) if 𝑀 ∈ C  =  0 if 𝑀 ∉ C . 

if 𝑀 ∈ C if 𝑀 ∉ C

Next, observe that C ⊆ ∪𝑁 ∈ C L𝑁 , by our earlier observation that 𝑁 ∈ L𝑁 for all 𝑁 ∈ C. Therefore, max 𝑀 ∈∪𝑁 ∈C L𝑁

𝜔 (𝑀) = max 𝜔 (𝑀) , 𝑀∈C

since 𝜔 (𝑀) = 0 for any 𝑀 ∈ ∪𝑁 ∈ C L𝑁 \ C. Hence, MLOI = 1 − 𝜔 (𝐿 ∗ ) = 1 −

max

𝜔 (𝑀)

𝑀 ∈∪𝑁 ∈C L𝑁

= 1 − max 𝜔 (𝑀) = 1 − max PG (𝐶 = 𝑀 | 𝐶 ∈ C) 𝑀∈C

= MCL ,

𝑀∈C

Location-of-interest vs. Current-location Privacy in Multi-hop Communication

35

demonstrating that the two measures are equivalent when the adversary knows that the user’s current location is their real location of interest.

□

Proof of Lemma 4.3. If the node at the user’s current location 𝐶 is compromised, the adversary will “guess” with certainty that the user’s current location is 𝐶 ∗ = 𝐶 — i.e., C = {𝐶}. The adversary will also know all of the locations queried, i.e., L𝐶 = L. In this case, the user’s CL-privacy drops to MCL = 1 − PG (𝐶 = 𝐶 ∗ | 𝐶 ∈ C) =1−1=0 . The user’s LOI-privacy also drops to MLOI = 1 − 𝜔 (𝐿 ∗ ) " =1−

max 𝑀 ∈∪𝑁 ∈C L𝑁

𝜔 (𝑀) = 1 − max 𝜔 (𝑀) = 1 − max 𝑀∈L

𝑀∈L

# ∑︁

𝜓 (𝑁 , 𝑀)

𝑁 ∈C

= 1 − max 𝜓 (𝐶 ∗, 𝑀) = 1 − max [PG (𝐶 = 𝐶 ∗ | 𝐶 ∈ C) · 𝜙 (𝐶 ∗, 𝑀)] = 1 − max 𝜙 (𝐶 ∗, 𝑀) 𝑀∈L 𝑀∈L 𝑀∈L   ∗ ∗ PG (𝐿 = 𝑀 | 𝐶 = 𝐶 ) · 𝜒 (𝐶 , 𝑀) = 1 − max Í . ∗ ∗ 𝑀∈L 𝑃 ∈ L PG (𝐿 = 𝑃 | 𝐶 = 𝐶 ) · 𝜒 (𝐶 , 𝑃) Note that, with the user’s current location compromised, 𝑀 ∈ K for all 𝑀 ∈ L. Therefore, 𝜒 (𝐶 ∗, 𝑀) = 1 for all 𝑀 ∈ L. Hence,   PG (𝐿 = 𝑀 | 𝐶 = 𝐶 ∗ ) · 𝜒 (𝐶 ∗, 𝑀) MLOI = 1 − max Í ∗ ∗ 𝑀∈L 𝑃 ∈ L PG (𝐿 = 𝑃 | 𝐶 = 𝐶 ) · 𝜒 (𝐶 , 𝑃)   PG (𝐿 = 𝑀 | 𝐶 = 𝐶 ∗ ) = 1 − max Í ∗ 𝑀∈L 𝑃 ∈ L PG (𝐿 = 𝑃 | 𝐶 = 𝐶 ) = 1 − max PG (𝐿 = 𝑀 | 𝐶 = 𝐶 ∗ and 𝐿 ∈ L) . 𝑀∈L

In a uniform, featureless environment, where from any current location the probability of any location being any user’s real LOI is 𝑛1 , that computation simplifies to  PG (𝐿 = 𝑀 | 𝐶 = 𝐶 ∗ ) MLOI = 1 − max Í ∗ 𝑀∈L 𝑃 ∈ L PG (𝐿 = 𝑃 | 𝐶 = 𝐶 ) # " # " 

1

= 1 − max Í 𝑛 𝑀∈L

=1−

1 𝑃∈L 𝑛

= 1 − max 𝑀∈L

1 𝑛

𝑘 · 𝑛1

1 𝑘 −1 = , 𝑘 𝑘

thus completing the proof.

□

Proof of Theorem 6.3. Expanding on the notation from Lemma 6.2, let 𝑌 be the optimal result to an instance of the partition problem with minimal pairwise distance 𝑑. Let 𝑋 be the result from the greedy algorithm with minimal pairwise distance 𝑑 ′ , and assume 𝑑 ′ < 𝑑2 . Define, for all 𝑦 ∈ 𝑌 , C𝑠 (𝑦) as the single closest node in 𝑋𝑠 to 𝑦 (with ties in distance being broken by the index of the node in 𝑋𝑠 ). Formally, C𝑠 (𝑦) = arg min{𝑥𝑖 ∈ 𝑋𝑠 | D(𝑥𝑖 , 𝑦) is minimized} . 𝑖

36

Ryan Vogt, Ioanis Nikolaidis, and Mario A. Nascimento

By definition, |𝑋𝑠 −1 | < 𝑘 = |𝑌 |. Therefore, by the pigeon-hole principle, there must exist 𝑦𝑎 , 𝑦𝑏 ∈ 𝑌, 𝑎 ≠ 𝑏, such that C𝑠 −1 (𝑦𝑎 ) = C𝑠 −1 (𝑦𝑏 ) (which we denote as 𝑥𝑐 ). Since 𝑥𝑐 is the closest node in 𝑋𝑠 −1 to 𝑦𝑎 , and we know from Lemma 6.2 that there must exist some node 𝑥 ∈ 𝑋𝑠 −1 such that D(𝑦𝑎 , 𝑥) ≤ 𝑑 ′ , we know that D(𝑦𝑎 , 𝑥𝑐 ) ≤ 𝑑 ′ . Similarly, D(𝑦𝑏 , 𝑥𝑐 ) ≤ 𝑑 ′ . Therefore, by the triangle inequality, D(𝑦𝑎 , 𝑦𝑏 ) ≤ 2 · 𝑑 ′ < 2 ·

𝑑 =𝑑 , 2

meaning that the minimal pairwise distance in 𝑌 is less than 𝑑, which is a contradiction.

□

Related documents

• Location-of-interest vs. Current-location Privacy in Multi-hop Communication#1414377
• Delay and coding in multiple-user communications#1394396
• Privacy Issues in Location-Aware Mobile Devices#493014
• Visibility and social closeness : how information shapes beliefs, coordination, and third-party responses#398704
• Version Age-of-Information-based Semantic Secrecy Region Analysis#1144446