HIDING QUERY ACCESS PATTERNS IN RANGE QUERIES USING PRIVATE INFORMATION RETRIEVAL AND OBLIVIOUS RAM

Gamze Tillem
Computer Science and Engineering, MSc. Thesis, 2015

Thesis Jury

Prof. Dr. Erkay Savaş (Thesis Advisor),

Asst. Prof. Dr. Kamer Kaya,

Asst. Prof. Dr. Ahmet Onur Durahim

Date &Time: 04.08.2015 –  13:00

Place: FENS 2019

Keywords : Private Information Retrieval,  Oblivious RAM, Privacy Preserving Range Query, Data Privacy, Cryptography

Abstract

This work addresses the problem of hiding query access patterns in privacy-preserving range queries while guaranteeing data and query confidentiality. 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.