Location privacy via actively secure private proximity testing

We present a solution which improves the level of privacy possible in location based services (LBS). A core component of LBS is proximity testing of users. Alice wants to know if she is near to Bob (or generally some location). The presented solution support private proximity testing and is actively secure meaning it prevents a number of attacks possible in existing protocols for private proximity testing. We demonstrate that the improved security provided only implies a factor of two penalty on execution time compared to an existing passively secure protocol. We also provide a security analysis and discuss the relevance of secure multiparty computation for location based services.