A comparative evaluation of private information retrieval techniques in location-based services

Private Information Retrieval (PIR) schemes offer privacy to Internet users by protecting the contents of their queries from the servers that they use. As the problem of user data collected by various services is becoming an issue of increasing concern, the functionality offered by such schemes is gaining a lot of attention. There are various PIR methods that ensure privacy, ranging from information-theoretic secure solutions that require multiple non-colluding servers, to hardware implementations based on secure trusted components. In this paper, we focus on computational PIR (cPIR) techniques which ensure privacy while using only one server and no dedicated hardware modules. Privacy is achieved with the help of encryption that relies on mathematical problems that are computationally intractable. We present an overview of the available cPIR techniques, we identify the major challenges of implementing such schemes, and we evaluate their relative performance. We provide an in-depth analysis of the strengths and weaknesses of cPIR solutions, and present scenarios where each technique is best suited.