Cryptanalysis of a Privacy-Preserving Ride-Hailing Service from NSS 2022
Srinivas Vivek · 2025
Read Cryptanalysis of a Privacy-Preserving Ride-Hailing Service from NSS 2022 by Srinivas Vivek (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-16744.txt.
Introduction
Srinivas Vivek, writing alone, breaks a privacy-preserving ride-hailing design that was presented at NSS 2022 by Xie and co-authors. Ride-hailing services match riders with drivers. Privacy-preserving versions try to hide the locations of both sides from the service provider while still making matches.
Vivek shows a passive attack against that design. By only watching normal protocol traffic, the provider can fully recover the location of the rider and of the responding drivers in every request. The attack is cheap to run, and its cost does not grow with the security parameter. The result is a warning that the earlier scheme's privacy promise does not hold.
Catalog record
| CREATOR | Srinivas Vivek |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 13 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-16744
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Cryptanalysis of a Privacy-Preserving Ride-Hailing Service from NSS 2022 Srinivas Vivek Abstract Ride-Hailing Services (RHS) match a ride request initiated by a rider with a suitable driver responding to the ride request. A Privacy-Preserving RHS (PP-RHS) aims to facilitate ride matching while ensuring the privacy of riders’ and drivers’ location data w.r.t. the Service Provider (SP). At NSS 2022, Xie et al. proposed a PP-RHS. In this work, we demonstrate a passive attack on their PP-RHS protocol. Our attack allows the SP to completely recover the locations of the rider as well as that of the responding drivers in every ride request. Further, our attack is very efficient as it is independent of the security parameter. ide-Hailing Services, Privacy, Attack. 1 Introduction Ride-Hailing Services (RHS) such as Uber, Ola, Lyft, Didi, etc. have become very popular in recent times. While traditional RHSs need access to the location data and other personal information of riders and drivers to determine ride matching and other related services, this set up also entails privacy risks for rider and drivers. Recent years have witnessed many Privacy-Preserving Ride-Hailing Service (PP-RHS)/ Privacy-Preserving Ride-Sharing Service (PP-RSS) proposals where the main aim of such protocols is to offer ride-matching service by a Service Provider (SP) like in a traditional RHS protocol. Additionally, a PP-RHS is also expected to (at least) ensure the privacy of location data of riders and users from the eyes of the SP, and from each other as well (see [ PDJ+17 , PDE+17 ] , [ LJFX19 , YSJ+19 , WZL+18 , HLF+21 , YJZ+19 , XGJ21 ] , and references there in). Recent works [ Viv23 , MV22b , MV22a , Viv21 , KV21 , KMV21 ] have also exposed serious privacy leakages in some of the above mentioned PP-RHS/ PP-RSS protocols. For example, the works [ MV22b , KV21 ] demonstrate how a rider could passively deduce location information of the drivers who respond to its ride request and not just of the driver eventually selected to offer the ride in the ORide PP-RHS protocol [ PDE+17 ] . However, the SP would continue to not be able to learn any location information as it would be working only with homomorphically encrypted data. Needless to say, the above cited attacks differ in technical details to account for varied designs of the underlying protocols potentially employing different cryptographic primitives. PP-RHS Protocol from [ XCG+22 ] . The privacy-preserving ride-hailing service proposed by Xie et al. [ XCG+22 ] was designed to offer private ride matching. The protocol enabled the SP to privately compute the distance between the rider (a.k.a. passenger) and the responding drivers (a.k.a. taxis) but without the SP actually learning the location coordinates of riders and drivers. The location coordinates of the drivers are encoded using the Road Network Embedding (RNE) technique [ SKS02 ] . This technique enables us to encode the topology of the road network into a high dimensional vector while still allowing the calculation of the actual road distance merely by computing the difference between the two RNE-encoded vectors and then finding the maximum amongst them. For every ride request by a rider, the driver with the least distance to the rider is chosen among the responding drivers. Threat model in [ XCG+22 ] . In [ XCG+22 , Section 4.2] , the authors describe the adversarial model under which they argue about the security of their protocol. The SP is assumed to be honest-but-curious , i.e., the SP performs its computation as part of the protocol correctly but may be eager to learn riders’ and drivers’ location information from the protocol transcript it possesses. Further, it is assumed that the riders and drivers behave responsibly in the sense that they keep their secret keys secure. Security claim in [ XCG+22 ] . The authors claim that SP will not be able to learn any information about the RNE location coordinates of riders and drivers. Their argument is based on the security of two PRFs whose output is used to mask the actual RNE coordinates. See [ XCG+22 , Section 6] for their security analysis. Our contribution : We demonstrate that the above security claim by the authors of [ XCG+22 ] is incorrect . Precisely, we exhibit a passive attack on the PP-RHS protocol from [ XCG+22 ] where an honest-but-curious SP can completely recover the RNE coordinates (and eventually the actual locations) of the rider and all the responding drivers in every ride request. Note that the authors of [ XCG+22 ] had incorporated specific security features into their design that would thwart an attack similar to the one in [ Viv23 ] on the protocol of [ XGJ21 ] . This includes limiting the total amount of data received by the SP by limiting the ride matching to a single zone, matching rides in the same time slot and by limiting the number of driver ciphertexts by implicit matching of the ciphertexts. Our main observation is that in spite of the above countermeasures, the decrypted data that the SP currently sees is enough to mount the attack of [ Viv23 ] . 2 PP-RHS Protocol from [ XCG+22 ] We briefly recall the protocol from [ XCG+22 ] . For brevity, we only recap those details that are necessary to describe our attack. See [ XCG+22 , Section 5] for all the details. The RNE encoding of a rider/driver’s location node u is denoted as E(u)=(E_{1}(u),E_{2}(u),\ldots,E_{n}(u)), where n is a chosen parameter and each E_{i}(u) is an unsigned integer. Let P be the (passenger) rider requesting a ride and T_{k} be the k th (taxi) driver who responds to this ride request. The RNE distance between P and T_{k} is calculated as \max_{i=1}^{n}|E_{i}(u_{P})-E_{i}(u_{T_{k}})|. For efficiency, each coordinate E_{i}(u_{P}) of the rider is further decomposed into m many blocks [E_{i}(u_{P})]_{j} (for j=0,1,2,\ldots,m-1 ) of l many bits each. The typical values are l=1 , l=2 or l=4 . Hence, E_{i}(u_{P})=\sum_{j=0}^{m-1}[E_{i}(u_{P})]_{j}\cdot(2^{l})^{j}. Let us denote the l -bit block weight (2^{l})^{j} in the above equation as w_{j} . To facilitate ride matching on encrypted location blocks, instead of directly encrypting the blocks [E_{i}(u_{P})]_{j} , what are actually encrypted are the following weighted differences between [E_{i}(u_{P})]_{j} and every l -bit value q : [E_{i}(u_{P})]_{j,q}=\left(q-[E_{i}(u_{P})]_{j}\right)\cdot w_{j}, where q\in\{0,1,\ldots,2^{l}-1\} . Let [E^{\prime}_{i}(u_{P})]_{j,q} denote the encryption of [E_{i}(u_{P})]_{j,q} . It is computed as [E^{\prime}_{i}(u_{P})]_{j,q}=(C_{1},C_{2}), where C_{1}=\left(\;\text{tag}_{i,j,q},F(H(\kappa_{1},q||i||j||z||s),\gamma_{j})\;\right), and C_{2}=F(H(\kappa_{2},q||i||j||z||s),\gamma_{j})\;\oplus\;((q-[E_{i}(u_{P})]_{j})\cdot w_{j}). In the above two equations, \text{tag}_{i,j,q} is an identifier (which in turn could be computed from other components), || and \oplus are the concatenation and the xor operators, respectively. H and F are PRFs, \gamma_{j} is a random nonce that is common for all the 2^{l} ciphertexts corresponding to the block [E_{i}(u_{P})]_{j} . The secret keys \kappa_{1} and \kappa_{2} are shared among riders and drivers, and it is distributed by an independent and trusted key manager . The rider sends these ciphertexts in a randomly permuted order to SP for eventual ride matching. Let u_{T_{k}} denote the location of the k th responding driver {T_{k}} for the ride request of the rider P . Let the corresponding decomposition of the i th coordinate of the RNE encoding E(u_{T_{k}}) be E_{i}(u_{T_{k}})=\sum_{j=0}^{m-1}[E_{i}(u_{T_{k}})]_{j}\cdot(2^{l})^{j}. Unlike the case