Order-Revealing Encryption: File-Injection Attack and Forward Security

Order-preserving encryption (OPE) and order-revealing encryption (ORE) are among the core ingredients for encrypted databases (EDBs). In this work, we study the leakage of OPE and ORE and their forward security. We propose generic yet powerful file-injection attacks (FIAs) on OPE/ORE, aimed at the situations of possessing order by and range queries. Our FIAs only exploit the ideal leakage of OPE/ORE (in particular, no need of data denseness or frequency). We also improve their efficiency with the frequency statistics using a hierarchical idea such that the high-frequency values will be recovered more quickly. We conduct some experiments on real datasets to test the performance, and the results show that our FIAs can cause an extreme hazard on most of the existing OPEs and OREs with high efficiency and 100% recovery rate. We then formulate forward security of ORE, and propose a practical compilation framework for achieving forward secure ORE to resist the perniciousness of FIA. The compilation framework can transform most of the existing OPEs/OREs into forward secure OREs, with the goal of minimizing the extra burden incurred on computation and storage. We also present its security proof, and execute some experiments to analyze its performance. The proposed compilation is highly efficient and forward secure.