20 20

Transactions on
Data Privacy
Foundations and Technologies


Articles in Press

Accepted articles here

Latest Issues

Year 2018

Volume 11 Issue 3
Volume 11 Issue 2
Volume 11 Issue 1

Year 2017

Volume 10 Issue 3
Volume 10 Issue 2
Volume 10 Issue 1

Year 2016

Volume 9 Issue 3
Volume 9 Issue 2
Volume 9 Issue 1

Year 2015

Volume 8 Issue 3
Volume 8 Issue 2
Volume 8 Issue 1

Year 2014

Volume 7 Issue 3
Volume 7 Issue 2
Volume 7 Issue 1

Year 2013

Volume 6 Issue 3
Volume 6 Issue 2
Volume 6 Issue 1

Year 2012

Volume 5 Issue 3
Volume 5 Issue 2
Volume 5 Issue 1

Year 2011

Volume 4 Issue 3
Volume 4 Issue 2
Volume 4 Issue 1

Year 2010

Volume 3 Issue 3
Volume 3 Issue 2
Volume 3 Issue 1

Year 2009

Volume 2 Issue 3
Volume 2 Issue 2
Volume 2 Issue 1

Year 2008

Volume 1 Issue 3
Volume 1 Issue 2
Volume 1 Issue 1

Volume 11 Issue 2

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


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.

* Corresponding author.

Follow us


ISSN: 1888-5063; ISSN (Digital): 2013-1631; D.L.:B-11873-2008; Web Site: http://www.tdp.cat/
Contact: Transactions on Data Privacy; Vicenç Torra; U. of Skövde; PO Box 408; 54128 Skövde; (Sweden); e-mail:tdp@tdp.cat
Note: TDP's web site does not use cookies. TDP does not keep information neither on IP addresses nor browsers. For the privacy policy access here.


Vicenç Torra, Last modified: 05 : 40 August 26 2018.