Efficient and Privacy-Preserving Ridesharing Organization for Transferable and Non-Transferable Services

Ridesharing allows multiple persons to share one vehicle for their trips instead of using multiple vehicles. Ridesharing can reduce the number of vehicles in the street, which consequently can reduce air pollution, traffic congestion, and transportation cost. However, ridesharing organization requires passengers to report sensitive location information about their trips to a trip organizing server (TOS) which creates a serious privacy issue. The existing ridesharing organization schemes are neither flexible nor scalable in the sense that they require a driver and a rider to have exactly the same trip to share a ride, and they are inefficient if applied to large geographic areas. In this paper, we propose two efficient privacy-preserving ridesharing organization schemes for Non-transferable Ridesharing Service (NRS) and Transferable Ridesharing Service (TRS). In NRS, a rider shares a ride from his/her trip's start to the destination with only one driver, whereas, in TRS, a rider can transfer between multiple drivers while en route until he reaches his destination. In the proposed schemes, the ridesharing area is divided into a number of small geographic areas, called cells, and each cell has a unique identifier. Each driver/rider should encrypt his/her trip's data with modified kNN encryption scheme, and send an encrypted ridesharing offer/request to the TOS. In NRS scheme, Bloom filters are used to represent the trip information compactly before encryption. Then, the TOS can measure the similarity of the encrypted trips to organize shared rides without revealing either the users' identities or the locations. In TRS scheme, drivers report their encrypted routes, and then the TOS builds a directed graph that is passed to a modified version of Dijkstra's shortest path algorithm to search for an optimal path for rides that can achieve a set of preferences prescribed by the riders. Although TRS can be used to organize non-transferable trips, performance evaluation shows that NRS requires less communication overhead than TRS. Our formal privacy proof and analysis demonstrate that the proposed schemes can preserve users privacy and our experimental results using routes extracted from real maps show that the proposed schemes can be used efficiently for large cities.