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

[img]PDF - Registered users only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: http://dx.doi.org/10.1007/978-3-662-53357-4_17


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
ID Code:30197
Deposited By:Erkay Savaş
Deposited On:13 Nov 2016 14:06
Last Modified:13 Nov 2016 14:06

Repository Staff Only: item control page