|
PATCONFDB: Design and Evaluation of Access Pattern Confidentiality-Preserving Indexes
Alexander Degitz(a), Hannes Hartenstein(a),(*)
Transactions on Data Privacy 11:2 (2018) 81 - 109
Abstract, PDF
(a) Institute of Telematics, Karlsruhe Institute of Technology (KIT), Germany.
e-mail:alexander.degitz @partner.kit.edu; hannes.hartenstein @kit.edu
|
|
Abstract
When sensitive data is outsourced to an untrustworthy cloud storage provider, encryption techniques can be used to enforce data confidentiality. Ideally, such encryption techniques should not only enforce the confidentiality of data at rest but also the confidentiality of data accesses, as database access patterns can leak information about the database's contents. Oblivious RAM (ORAM) approaches were proposed to hide access patterns, but they currently support a very limited set of database query operations. In this paper, we propose PATCONFDB that supports database query functionalities and hides query access patterns. PATCONFDB represents a construction based on ORAM schemes: when an index (B-tree) is outsourced, multiple ORAM instances are used to maintain access pattern confidentiality. PATCONFDB can make use of up-to-date ORAM schemes, for example an implementation of Burst ORAM is used to significantly boost the performance of accesses. We compare PATCONFDB with a shuffled B-tree protocol, provide a discussion on security properties, and give recommendations of which protocol to use in which usage scenario. We provide a rigorous efficiency evaluation to determine the storage and network overhead as well as query latency. In particular, we show that PATCONFDB with ORAM-based schemes like Burst ORAM only causes a marginal latency overhead when evaluating equality conditions on databases of up to 10 million records. However, the network overhead still remains a challenge.
|
