  Ride Hailing Services (RHS) have become a popular means of transportation,
and with its popularity comes the concerns of privacy of riders and drivers.
ORide is a privacy-preserving RHS proposed in 2017 and uses Somewhat
Homomorphic Encryption (SHE). In their protocol, a rider and all drivers in a
zone send their encrypted coordinates to the RHS Service Provider (SP) who
computes the squared Euclidean distances between them and forwards them to the
rider. The rider decrypts these and selects the optimal driver with least
Euclidean distance. In this work, we demonstrate a location-harvesting attack
where an honest-but-curious rider, making only a single ride request, can
determine the exact coordinates of about half the number of responding drivers
even when only the distance between the rider and drivers are given. The
significance of our attack lies not in inferring location of the optimal driver
(which is anyway sent to the rider in clear after ride establishment) but in
inferring locations of other drivers in the zone, who aren't (supposed to be)
revealed to the rider as per the protocol. We validate our attack by running
experiments on zones of varying sizes in arbitrarily selected big cities. Our
attack is based on enumerating lattice points on a circle of sufficiently small
radius and eliminating solutions based on conditions imposed by the application
scenario. Finally, we propose a modification to ORide aimed at thwarting our
attack and show that this modification provides sufficient driver anonymity
while preserving ride matching accuracy.
