Hiding query access patterns in range queries using private information retrieval and oblivious ram

Official URL: http://risc01.sabanciuniv.edu/record=b1615044 (Table of Contents)

This work addresses the problem of hiding query access patterns in privacypreserving range queries while guaranteeing data and query con dentiality. We propose two methods, which are based on Private Information Retrieval (PIR) and Oblivious RAM (ORAM) techniques, respectively. For the PIR based search operation, we introduce a new scheme based on Lipmaa's computationally-private information retrieval (CPIR) method. We reduce the computation cost of CPIR by reducing the number of modular exponentiation operations, employing shallow trees and utilizing multi-exponentiation techniques. Furthermore, we improved the performance of CPIR by applying parallel algorithms. For the ORAM based method, we adapted Stefanov's Path ORAM method to the privacy-preserving range search. Our analyses show that, in terms of communication cost, CPIR provides better bandwidth usage especially in large database sizes, while in computational cost, Path ORAM based method performs better due to the negligible cost of server operations. The results imply that, despite some advantageous qualitative aspects of CPIR and its highly parallel implementation, it is still an expensive scheme in terms of computation complexity in comparison with Path ORAM for hiding query access patterns in privacy preserving range queries.