Generic Attacks on Secure Outsourced Databases

TLDR

Secure outsourced database protocols range from fully homomorphic encryption to searchable symmetric encryption, yet attacks exploiting auxiliary information can compromise confidentiality. We aim to formally understand the efficiency/privacy trade‑off inherent in outsourced database systems, independent of specific implementations. We propose abstract models of outsourced storage that capture access‑pattern and communication‑volume leakage as the two fundamental sources of information loss. Our analysis shows that every examined outsourced database system leaks either access patterns or communication volume.

Abstract

Recently, various protocols have been proposed for securely outsourcing database storage to a third party server, ranging from systems with "full-fledged" security based on strong cryptographic primitives such as fully homomorphic encryption or oblivious RAM, to more practical implementations based on searchable symmetric encryption or even on deterministic and order-preserving encryption. On the flip side, various attacks have emerged that show that for some of these protocols confidentiality of the data can be compromised, usually given certain auxiliary information. We take a step back and identify a need for a formal understanding of the inherent efficiency/privacy trade-off in outsourced database systems, independent of the details of the system. We propose abstract models that capture secure outsourced storage systems in sufficient generality, and identify two basic sources of leakage, namely access pattern and ommunication volume. We use our models to distinguish certain classes of outsourced database systems that have been proposed, and deduce that all of them exhibit at least one of these leakage sources.