Stateless and Non-Interactive Order-Preserving Encryption for Outsourced Databases through Subtractive Homomorphism

Order-preserving encryption (OPE) has been extensively studied for more than two decades in the context of outsourced databases because OPE is a key enabling technique to allow the outsourced database servers to sort encrypted tuples in order to build indexes, complete range queries, and so forth. The state-of-the-art OPE schemes require (i) a stateful client -- implying that the client manages the local storage of some mapping between plaintexts and ciphertexts, and/or (ii) the interaction between the client and the server during the query. In production systems, however, the above assumptions do not always hold (not to mention performance overhead): In the first case, the storage requirement could exceed the capability of the client; In the second case, the clients may not be accessible when the server executes a query involving sort or comparison. This paper proposes a new OPE scheme that works for stateless clients and requires no client-server interaction during the queries. The key idea of our proposed protocol is to leverage the underlying additive property of a homomorphic encryption scheme such that the sign of the difference between two plaintexts can be revealed by some algebraic operations with an evaluation key. We will demonstrate the correctness and security of the proposed protocol in this short paper; the implementation and experimental results will be presented in an extended report.