Location-based Services (LBSs) provide valuable services, with convenient features for mobile users. However, the location and other information disclosed through each query to the LBS erodes user privacy. This is a concern especially because LBS providers can be honest-but-curious, collecting queries and tracking users' whereabouts and infer sensitive user data. This motivated both centralized and decentralized location privacy protection schemes for LBSs: anonymizing and obfuscating LBS queries to not disclose exact information, while still getting useful responses. Decentralized schemes overcome disadvantages of centralized schemes, eliminating anonymizers, and enhancing users' control over sensitive information. However, an insecure decentralized system could create serious risks beyond private information leakage. More so, attacking an improperly designed decentralized LBS privacy protection scheme could be an effective and low-cost step to breach user privacy. We address exactly this problem, by proposing security enhancements for mobile data sharing systems. We protect user privacy while preserving accountability of user activities, leveraging pseudonymous authentication with mainstream cryptography. We show our scheme can be deployed with off-the-shelf devices based on an experimental evaluation of an implementation in a static automotive testbed. Additional Key Words and Phrases: Location privacy, honest-but-curious, pseudonymous authentication A Location-based Service (LBS) query targets a location/region and expresses one or more specific user interests; the LBS server responds with the most up-to-date relevant information, e.g., the latest menu of a restaurant, movies at a cinema, remaining parking slots at a shopping mall, or traffic conditions in the area. During this process, users' current or future whereabouts and interests are disclosed to the LBS server through their queries. All submitted information is deemed necessary to best serve users, and the LBS server is entrusted with rich data. However, many studies [5, 15, 62] reveal that service providers can be honest-but-curious, aggressively collecting information to profile users, e.g., identifying home or working places or inferring interests for commercial purposes. LBS privacy is studied extensively. Location k-anonymity [16] ensures that at least k − 1 other users are involved in an obfuscated region, R, used as the querier's location. Therefore, even in the presence of a local observer in R, the query cannot be linked to a certain user; the LBS server only learns the querier is one among k users in R. Protection can be achieved by centralized schemes [16, 45, 46] that introduce an anonymizer, a proxy between users and the LBS server, which anonymizes user queries before sending them to the LBS server. However, the assumed anonymizer trustworthiness merely "shifts" the trust from the LBS server to the anonymizer, holding rich information the same way that the LBS server would. Simply put, an anonymizer could be itself honest-but-curious. Decentralized approaches [19, 53] can eliminate the need for an anonymizer and protect user privacy in a collaborative manner: for example, form an obfuscated area with k users within each other's communication range [19] . However, if such k users are too close, e.g., in a church, a shopping mall, or a cinema, such symbolic "addresses" can still be disclosed. Thus, it is hard to define how large k should be to ensure an appropriate level of protection. An alternative collaborative privacy protection approach is to pass/share LBS-obtained information among users, to decrease exposure to the LBS server [31, 55] . The sharing approach requires 1 arXiv:2001.07583v2 [cs.CR] 22 Jan 2020 nodes to cache information received from the LBS and pass it to neighbors when requested. Moreover, sharing (and thus reduced exposure to the LBS server) is orthogonal to location obfuscation; the two could complement each other. Nonetheless, opening up the system functionality is a double-edged sword: sharing reduces user exposure to the curious provider (LBS or anonymizer) but it also exposes her to possibly faulty, misbehaving or curious peers. In fact, studies on peer-to-peer (P2P) systems [32, 40, 63] show that insecure decentralized schemes face serious problems: sensitive information could be exposed to peers and malicious nodes could pass on bogus data. Signed LBS server responses can be self-verifiable when passed to peers [55] and partially address the second above-mentioned concern regarding malicious nodes. However, queries and cached information from different users could be diverse, making it necessary to share one or multiple complete LBS-obtained responses (each with a signature attached), even though only a subset of each LBS-obtained response might be needed by the querying peer. For example, the query could be What is the menu of restaurant A? and How many parking spaces are available at B? while another node could query What are the opening hours of restaurant A? and What stores are in shopping mall B? It is not straightforward to decide whether the peer responses include information as if the the response were directly obtained from the LBS server, thus, guaranteeing quality of service. Even though nodes can assess the completeness of gathered peer responses [44] and wait until the required completeness is met, peer responses equivalent to an LBS response can be hard to achieve; and, in any case, incur significant delays and overhead, i.e., redundant cryptographic fields and information. Last but not least, peer queries, openly submitted to nodes' neighborhood, could expose users to other nodes and passive eavesdroppers. These challenges are addressed here by our security architecture for secure and resilient decentralized/collaborative privacy protection for LBSs. We propose new components orthogonal to the LBS functionality. We leverage pseudonymous authentication to provide privacy-enhancing message authentication and integrity for communication with other users/peers and with infrastructure entities. We also leverage proactive caching of Point of Interest (POI) data (e.g., for a region) by a small fraction of users (termed serving nodes) that serve others, sharing the cached POI data. This ensures that peer responses can provide the same quality as direct LBS responses without extra communication incurred by using an obfuscated area. This also enables cross-checking multiple peer responses to the same query, to detect false responses from malicious nodes. The burden is balanced among users through a periodical randomized role assignment by the infrastructure. While users benefit from the information sharing system, our scheme minimizes their exposure to the LBS server and limits exposure to curious serving nodes (thanks to encrypted querying and serving node communication). Our evaluation shows both effective exposure reduction and highly successful valid POI provision in a realistic intelligent transportation setting, even with a very high (in practice) fraction (e.g., 20 %) of curious or malicious nodes. The contributions of this paper are: (1) use of pseudonymous authentication for privacy-preserving user authentication, (2) privacy-enhancing randomized serving node assignment and encrypted P2P query-response exchange, (3) cross-checking of P2P responses and privacy-preserving proactive LBS response validation, (4) qualitative and extensive quantitative simulation-based security and privacy analyses, (5) comparison to the state-of-the-art, MobiCrowd [55], in terms of achieved privacy and security, and efficiency (notably, communication overhead), and (6) experimental evaluation leveraging a field-operational-test grade automotive communication testbed, emulating real-world conditions. The rest of the paper is organized as follows: We discuss related work in Sec. 2. We outline the system and adversarial models, as well as requirements in Sec. 3. Then, we present the proposed scheme in Sec. 4. We provide a qualitative security and privacy analysis in Sec. 5.1, followed by an 2 extensive quantitative simulation-based evaluation in Sec. 5.2. We show experimental evaluation results with our scheme implemented on an automotive testbed, and discuss design choices for its deployment in real-world scenarios (Sec. 6) before we conclude (Sec. 7). User queries, including user locations and interests, are essential information for LBSs to best serve users; this very same information can also be used to breach user privacy. Queries from the same user can be linked and eventually used to reconstruct user traces and infer user activities, e.g., home or work addresses. Anonymization or pseudonymization, i.e., removal of user identities or their replacement with pseudonymous identities, prevents the LBS server from correlating real user identities with queries. The LBS server only sees a pool of user queries without any information that immediately identifies the querying users. However, studies have shown that simply removing identities from frequent queries could not prevent tracking and even profiling (e.g., inferring real names) of specific users [24, 26, 28] . Location obfuscation: Location obfuscation uses cloaked areas or perturbed locations to represent actual user locations. Cloaked areas [4, 9] can be used so that the LBS server only learns the area the user is in and then responds with the information that pertains to the whole area. However, a determined attacker could learn which users are located in this area. If, in an arguably rare situation, the user is the only one included in this area, the attacker can easily link the query with the only user "seen" in this area. Location k-anonymity [23, 37] is used to form an obfuscated area involving at least k users, so that the user would not stand out from the obfuscated area. However, merely using k-anonymity could not guarantee an area constructed based on k users large enough to hide symbolic address (e.g., church, shopping mall and gas station). Therefore, in densely populated areas, the perturbed/obfuscated region should be large enough so that all nodes within the area are not closely gathered. At the same time, the quality of the LBS response would be affected if the location in the query is not accurate enough. Thus, it is hard to define how large should k be to ensure an appropriate level of privacy protection. Geo-indistinguishability [1, 3, 13] uses perturbed locations to represent user locations, adding Laplacian noise to user locations based on the required degree of privacy. This trades off accuracy of POI data for higher privacy. Both approaches could fail to protect node privacy when multiple queries can be correlated [1, 56] . Moreover, schemes based on k-anonymity can be vulnerable to the so-called center of Anonymized Spatial Region (ASR) attack: the probability of the requesting node being the node closest to the center of ASR is larger than 1/k [19, 33] . Such an attack can be prevented by applying a k-anonymity algorithm to one of the neighbors. These neighbors are discovered by applying the k-anonymity algorithm to itself. This generates a cloaked region that is not necessarily centered around oneself. Centralized and decentralized approaches: Both centralized and decentralized variants of the above-mentioned privacy enhancing techniques were proposed. Centralized approaches introduce a Trusted Third Party (TTP) that acts as a so-called anonymizer for the queries sent to the LBS server. The anonymizer could find k − 1 nearest neighbors of the querying user and send the queries from all k users to the LBS server [4] . The anonymizer can also remove user identities from the queries before sending them to the LBS server, while keeping information that matches user identities and queries locally, so that it can appropriately respond to each user the needed information. However, there can be an inherent controversy here: we assume the LBS server is honest-but-curious, but the anonymizer could be honest-but-curious too. The (centralized) anonymizer could collect user queries and use the information the same way the LBS server would. Decentralized approaches thwart honest-but-curious infrastructure by relying on users. To achieve k-anonymity with decentralized schemes, users can search for k − 1 neighbors in an ad-hoc network and use the area including these k users as the cloaked area [10,
Beyond the scope of this paper, SECMACE can be highly beneficial in other application domains, e.g., secure and privacy-preserving LBS provision REF .
Resilient Privacy Protection for Location-Based Services through Decentralization
ACM Transactions on Privacy and Security (TOPS), 22(4), 21:1-36, 2019
Computer Science