Privacy-enhanced distance computation with applications

Location privacy has been regarded as an important requirement for location-based service on mobile devices such as mobile phones, where location information might have to be protected against unauthorised or even authorised (curious-but-honest) parties in some cases. We propose a scheme, which provides a method for a location server to identify the nearest mobile object (amongst n mobile objects) to a target mobile object without revealing the location of any participant to the location server. We describe our protocol by using a practical application, where the aim is to identify a closest service vehicle among registered service vehicles to the target car which requires a service, while the locations of all participants are protected against the location server. Our scheme only requires an additive homomorphic encryption scheme without the need of fully homomorphic encryption as required by all other related schemes on location privacy.