EncodeORE: Reducing Leakage and Preserving Practicality in Order-Revealing Encryption

Order-preserving encryption (OPE) is a cryptographic primitive that preserves the order of plaintexts. In the past few years, many OPE schemes were proposed to solve the problem of executing range queries in encrypted databases. However, OPE leaks some certain information (for example, the order of ciphertext), so it is vulnerable to many attacks. Subsequently, order-revealing encryption (ORE) was proposed by Boneh
et al.
(Eurocrypt 2015) as a generalization of order-preserving encryption. It breaks through the limitation of the numeric order of OPE plaintext. It implements ciphertext comparison for any specific form of plaintext through a publicly computable comparison function. In this article, we aim to design a new ORE scheme which reduces the leakages and preserves the practicality in terms of ciphertext length and encryption time. We first propose the hybrid model named
HybridORE
. Then, we propose an improved scheme named
EncodeORE
which achieves acceptable security and appropriate ciphertext length. They both explore the encode strategy of encoding plaintext into different parts and apply suitable ORE algorithms to each part according to its security characteristics to reduce leakages. Compared with the typical CLWW scheme (FSE 2016) and Lewi-Wu (CCS 2016) in large domain, they have fewer leakages. The experiment shows that the proposed
EncodeORE
is very practical.