Secure Data Outsourcing: Access Pattern Confidentiality in Outsourced Databases

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 parts of the database's contents. Encryption techniques like Oblivious RAM (ORAM) or dynamically shuffled B-trees were proposed to hide access patterns, but are computationally expensive and create a large overhead of network traffic. Furthermore, they currently support a very limited set of database search operations.

In this talk, I will give an overview of current protocols for secure data outsourcing like shuffled B-tree and Oblivious RAM approaches, and I will introduce our proposed protocols SECURUS and PATCONFDB.

SECURUS is a protocol that optimizes the query times on encrypted index structures for database outsourcing based on the security needs of users by using the optimal encryption technique (deterministic, order-preserving, homomorphic, etc…) and outsourcing technique (data partitioning, index separation, etc…) for every index.

PATCONFDB is a protocol for database outsourcing that obfuscates access patterns to the database through the use of ORAM approaches. It provides fast range and prefix selections for databases while being agnostic to the type of underlying ORAM approach.