To allow efficient search over encrypted data in the database, we sometimes often use Encrypted Search Algorithms (ESAs) (e.g., Searchable Encryption, ORAMs, functional encryption, property-preserving encryption). However, all of them are seeking trade-offs between leakage, expressiveness and efficiency.

The authors in Revisiting Leakage Abuse Attacks considers the ESA as a composition of two algorithms: SETUP and SEARCH, and accordingly, the leakage comes from two sources: leakage at setup time and at query time. Attacks include File injection attack (IKK), Inference attacks against property-preserving encryption (e.g., OPE, DTE) by NKW (CCS 15.), as wel las ORAMs (Generic attacks on secure outsourced databases).

Threat Model

• The adversarial models can often be categorized as snapshot adversary that only has access to the encrypted document collections while persistent adversary can access the encrypted data and the transcript of the query operations.
• The target of the adversary can be divided into two: data-recovery and query-recovery.
• The auxiliary information consists of sample-data that is close to the original distribution of the data collection with regard to statistical metrics (e.g., statistical distance, KL-divergence); known-query attacks require knowledge of a subset of the queries. known-data attacks require knowing the subset of the data collection.

Note that Sample-Data Attacks are often referred to as Inference Attacks while Known-Data Attacks are often referred to as Leakage-Abuse Attacks.