Inference Attacks on Property-Preserving Encrypted Databases

TLDR

Encrypted database systems that support SQL over encrypted data have emerged in recent years, offering performance competitive with commercial databases amid growing cloud adoption and data breach concerns. This study investigates the concrete security of such systems by presenting attacks that recover plaintext from deterministic and order‑preserving encrypted columns using only the encrypted data and publicly available auxiliary information. The authors analyze both classic frequency‑analysis and sorting attacks and introduce new combinatorial‑optimization‑based methods to compromise deterministic and order‑preserving encryption schemes.

Abstract

Many encrypted database (EDB) systems have been proposed in the last few years as cloud computing has grown in popularity and data breaches have increased. The state-of-the-art EDB systems for relational databases can handle SQL queries over encrypted data and are competitive with commercial database systems. These systems, most of which are based on the design of CryptDB (SOSP 2011), achieve these properties by making use of property-preserving encryption schemes such as deterministic (DTE) and order- preserving encryption (OPE). In this paper, we study the concrete security provided by such systems. We present a series of attacks that recover the plaintext from DTE- and OPE-encrypted database columns using only the encrypted column and publicly-available auxiliary information. We consider well-known attacks, including frequency analysis and sorting, as well as new attacks based on combinatorial optimization.