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

Tillem, Gamze (2015) Hiding query access patterns in range queries using private information retrieval and oblivious ram. [Thesis]

[thumbnail of GamzeTillem_10086239.pdf] PDF
GamzeTillem_10086239.pdf

Download (615kB)

Abstract

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.
Item Type: Thesis
Subjects: Q Science > QA Mathematics > QA076 Computer software
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: IC-Cataloging
Date Deposited: 06 Jun 2017 14:51
Last Modified: 26 Apr 2022 10:09
URI: https://research.sabanciuniv.edu/id/eprint/32307

Actions (login required)

View Item
View Item