# Equivalence-based Security for Querying Encrypted Databases: Theory and Application to Privacy Policy Audits

arXiv: https://arxiv.org/abs/1508.02448 · HTML: https://mlsanity.com/paper/1508.02448/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Aug 2015.

## Built on by (most cited first, 1 of 1)

- [Syntax Is Easy, Semantics Is Hard: Evaluating LLMs for LTL Translation](https://mlsanity.com/paper/2604.07321/) (2026)

## Abstract (arXiv)

Motivated by the problem of simultaneously preserving confidentiality and usability of data outsourced to third-party clouds, we present two different database encryption schemes that largely hide data but reveal enough information to support a wide-range of relational queries. We provide a security definition for database encryption that captures confidentiality based on a notion of equivalence of databases from the adversary's perspective. As a specific application, we adapt an existing algorithm for finding violations of privacy policies to run on logs encrypted under our schemes and observe low to moderate overheads.