Hiding access patterns in range queries using private information retrieval and ORAM

Tillem, Gamze and Candan, Ömer Mert and Savaş, Erkay and Kaya, Kamer (2016) Hiding access patterns in range queries using private information retrieval and ORAM. In: International Workshops on Financial Cryptography and Data Security, Christ Church, Barbados

[thumbnail of proceedings_06.pdf] PDF
Restricted to Registered users only

Download (647kB) | Request a copy


We study the problem of privacy preserving range search that provides data, query, and response confidentiality to the users for range queries. We propose two methods based on Private Information Retrieval (PIR) and Oblivious RAM (ORAM) techniques. For PIR-based queries, Lipmaa’s computationally-private information retrieval (CPIR) scheme is employed. For the ORAM-based method, Stefanov et al.’s Path ORAM scheme is adapted to enable privacy preserving range search. Our analyses show that from the computational point of view, the ORAM-based method performs much better due to cheap server operations. However, CPIR utilizes the bandwidth better especially for large databases, its security definitions are more formal, and it is more flexible for various settings with multiple clients and/or bandwidth limitations. In this work, to make CPIR a practical alternative for large databases, we improve its performance via shared memory OpenMP and distributed memory OpenMP-MPI parallelization with a scalable data/task partitioning.
Item Type: Papers in Conference Proceedings
Uncontrolled Keywords: Privacy preserving range queries, Private information retrieval, Oblivious RAM, Data privacy, Parallel computing
Subjects: Q Science > QA Mathematics > QA075 Electronic computers. Computer science
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: Erkay Savaş
Date Deposited: 13 Nov 2016 14:06
Last Modified: 26 Apr 2022 09:24
URI: https://research.sabanciuniv.edu/id/eprint/30197

Actions (login required)

View Item
View Item