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 ge...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-inject ion attacks(FI As)on OPE/ORE,aimed at the situations of possessing order by and range queries.Our FI As 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 FI As 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.展开更多
基金the National Key Research and Development Program of China under Grant No.2017YFB-0802000the National Natural Science Foundation of China under Grant Nos.61472084 and U1536205+2 种基金Shanghai Innovation Action Project under Grant No.16DZ1100200Shanghai Science and Technology Development Funds under Grant No.16JC1400801Shandong Provincial Key Research and Development Program of China under Grant Nos.2017CXG0701 and 2018CXGC0701.
文摘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-inject ion attacks(FI As)on OPE/ORE,aimed at the situations of possessing order by and range queries.Our FI As 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 FI As 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.
