Order Reveling Encryption (ORE) enables eficient range queries on encrypted databases, but may leak information that could be exploited by inference attacks. State-of-the-art ORE schemes claim diferent security guarantees depending on the adversary attack surface. Intuitively, online adversaries who access the database server at runtime may access information leakage; ofline adversaries who access only a snapshot of the database data should not be able to gain useful information. We focus on ofline security of the ORE scheme proposed by Lewi and Wu (LW-ORE, CCS 2016), which guarantees semantic security of ciphertexts stored in the database, but requires that ciphertexts are maintained sorted with regard to the corresponding plaintexts to support sublinear time queries. The design of LW-ORE does not discuss how to build indexing data structures to maintain sorting. The risk is that practitioners consider indexes as a technicality whose design does not afect security. We show that indexes can afect ofline security of LW-ORE because they may leak duplicate plaintext values, and statistical information on plaintexts distribution and on transactions history. As a real-world demonstration, we found two open source implementations related to academic research (JISA 2018, VLDB 2019), and both adopt standard search trees which may introduce such vulnerabilities. We discuss necessary conditions for indexing data structures to be secure for ORE databases, and we outline practical solutions. Our analyses could represent an insightful lesson in the context of security failures due to gaps between theoretical modeling and actual implementation, and may also apply to other cryptographic techniques for securing outsourced databases.
Standard encryption solutions for databases protect data at rest [
Research eforts for encryption of data in use include multifold approaches [
We are interested in Property Preserving Encryption (PPE) [
We focus on Order Revealing Encryption (ORE) [
In this paper, we reconsider ofline security of LW-ORE when deployed in real database
systems. Although right ciphertexts are proved semantically secure, they have to be
maintained sorted to enable sublinear query times via binary search. However, LW-ORE
does not describe indexing data structures or other mechanisms. Thus, the scheme can be
straightforwardly applied only to a handful of use cases or should be adopted with only
support for linear time queries. In any other scenario, LW-ORE must be integrated with
indexing data structures, and the risk is to consider this integration a technicality, that is,
something that cannot afect the original security guarantees of the scheme. As already
experienced many times in applied cryptography and cryptographic engineering, details
left open in theoretical designs may open to security vulnerabilities when implemented in
real systems. We found relevant literature associated with open source implementations
of LW-ORE that indeed adopt standard database indexing techniques based on AVL
trees [
In this paper, we show that using standard indexing techniques for ORE may introduce at least two classes of vulnerabilities: • the first class of vulnerability is the simpler but also the most severe, and is related to the disclosure of duplicate values: standard indexes store pointers to all duplicate values within the same data structure node, thus ofline security guarantees of the encrypted database fall back to that of a deterministic encryption scheme, reenabling powerful inference attacks. This vulnerability thus breaks one of the major contributions of LW-ORE, that is, of guaranteeing semantic security of ciphertexts. Ad-hoc variants of standard indexing techniques must be implemented to avoid storing duplicate value within the same data structure node while maintaining the data structure eficient. • the second class of vulnerability is related to the disclosure of information regarding the history of the transactions executed on the database. This vulnerability may also cause disclosure of information related to the plaintext distribution if such distribution is not independent of the insertion order (or on derived information, such as insertion time). This requirement has been outlined by literature which denote as history independent the data structure that do not leak any information about the transactions history that generated the data structure [32, 33]. However, to the best of our knowledge, it is not considered by literature related to database outsourcing and PPE.
The two classes of vulnerabilities may not apply depending on the characteristics of the database and of the query workload, but protecting against both may require the design of ad-hoc indexing data structures. The last contribution of the paper is to outline such design, leaving further analyses and evaluations as future work.
The rest of the paper is organized as follows. Section 2 outlines ORE schemes and databases. Section 3 discusses possible information leakage due indexing data structures. Section 4 outlines necessary design choices for secure indexes on ORE databases. Section 5 concludes the paper and discusses future work.
The Order Revealing Encryption scheme by Lewi and Wu [
LW-ORE scheme operations framework. The LW-ORE scheme includes four algorithms: setup (ORE.Setup), left encrypt (ORE.EncryptL), right encrypt (ORE.EncryptR), and compare (ORE.Compare): • sk $ ORE.Setup(1 ) is a probabilistic algorithm which takes security parameter 1 and outputs secret key sk; • cL ORE.EncryptL(sk; p) is a deterministic algorithm which takes key sk and plaintext p and outputs left ciphertext cL; • cR $ ORE.EncryptR(sk; p) is a probabilistic algorithm which takes key sk and plaintext p and outputs right ciphertext cR; • f 1; 0; 1g ORE.Compare(c1L; c2R) is a deterministic algorithm which takes left and right ciphertexts c1L and c2R, and outputs 1, 0, 1 if p1 is less then, equal, or greater than p2, where c1L ORE.EncryptL(sk; p1) and c2R $ ORE.EncryptR(sk; p2), for any sk $ ORE.Setup(1 ).
LW-ORE does not expose a native decryption routine, but decryption can be implemented as a binary search over the plaintext domain via encryption and compare (see [8, Remark 2.1]). In the context of encrypted databases, ORE ciphertexts can be associated with ciphertexts computed with any standard symmetric schemes to enable more eficient decryption.
LW-ORE range query protocol for encrypted databases. LW-ORE scheme allows designing a stateless and single round Range Query protocol (RQ) [8, Section 5.2] among a client and a database server that includes four operations: database setup (RQ.Setup), range query (RQ.Range), insert (RQ.Insert), and delete (RQ.Delete). Without loss of generality, in this paper we omit delete to avoid too much verbosity.
• st $ RQ.Setup(1 ; P ): the client initializes ORE secret key sk $ ORE.Setup(1 ),
sorts the database P as P^ = hp1; : : : ; pN i such that pn pn+1 8n 2
[N 1], and encrypts the sorted database P^ as C^ = c1R; : : : ; cRN such that
cnR $ ORE.EncryptR(sk; pn) 8n 2 [N ]. The client sends C^ to the server, which
sets its state information st = C^.
• hpi; : : : ; pj i RQ.Range(sk; q = (x; y); st = C^): the client computes the tuple
cLx; cyL such that cLx ORE.EncryptL(sk; x) and cyL ORE.EncryptL(sk; y), and
sends it to the server. The server uses cLx (cyL) to find ciR (cjR) within C^ such that i (j)
is the smallest (greatest) index of C^ = cnR n2[N] such that ORE.Compare(cLx; ciR) =
1 (ORE.Compare(cyL; cjR) = 1). As suggested in the original protocol [
Limitations of LW-ORE models. The LW-ORE range query protocol models the
encrypted database as state information st = C^ = c1R; : : : ; cRN , which represents the
list of right ciphertexts sorted with regard to their corresponding plaintexts, that is,
pn pn+1 8n 2 [N 1]. The LW-ORE query protocol assumes that the database server
maintains the state information sorted throughout insert operations and thus that binary
search can always be executed on st (see [8, Section 5.2]). Moreover, the original paper
claims semantic security against snapshot ofline adversaries because right ciphertexts are
semantically secure (see [8, Definition 5.2, Theorem 5.5]). We observe that the database
model and security analyses proposed in the original LW-ORE paper have two major
limitations:
• claims about semantic security against snapshot ofline adversaries do not take
into account that although right ciphertexts are semantically secure, the encrypted
database also leaks the partial sorting order with regard their corresponding
plaintexts. It is critical to clearly declare this additional leakage because it may
open to known attacks (e.g., correlation attacks on ideal ORE [
We analyze indexing solutions for LW-ORE databases. In Section 3.1 we extend notation
proposed by the original LW-ORE paper (see Section 2 and [
We extend notation of the original LW-ORE range query protocol (see Section 2) to propose a model that could fit an indexed document-oriented database encrypted with LW-ORE. To this aim, we model the database state information as st = hD; Ii. We denote as D = fid : didg the set of documents possibly encrypted via a standard symmetric scheme, where did denotes a document uniquely indexed by an opaque document identifier id. We denote as I = ; fcRg; fidg the indexing data structure that enables eficient range queries on documents D. The links of the indexing data structure are denoted as , the keys used to evaluate queries are the right ciphertexts fcRg, and the pointers to the documents are document identifiers fidg.
We analyze how an adversary may try to obtain information from the state of the database. Since both documents fdidg and right ciphertexts are encrypted with semantically secure schemes, an adversary cannot infer any information except possibly for their size and number. Moreover, we assume that document identifiers do not reveal any information (e.g., they are random strings). However, an adversary may try to gain information from the data structure . We note that the original paper of LW-ORE did not clearly model this information (see Section 2). In the remaining of the section, we consider diferent kinds of popular data structures and analyze their security guarantees.
----
------
One of the main benefits of LW-ORE is to store semantically secure right ciphertexts
within the database (see Section 2). However, the typical design choice of any indexing
data structure is to store all pointers to duplicate database values within the same node
to improve query performance and to reduce the index size. The result is that applying
standard indexes to LW-ORE leaks duplicate values within the database, and thus the
security guarantees of LW-ORE fall back to those of a deterministic encryption scheme,
possibly re-enabling related inference attacks [
To better explain this class of vulnerability, we consider an example based on an AVL
tree used as the indexing data structure for a LW-ORE database, which represents the
implementation of [
A visual example of an AVL tree instantiated for LW-ORE is shown in Figure 1. Recalling notation described in Section 3.1, the keys are right ciphertexts fc1R; : : : ; c5Rg, and the pointers to documents are identifiers fid1; : : : ; id8g. It is clear that snapshot ofline adversaries that access the AVL tree know that documents associated with id2 and id4 (id1, id5 and id8) are associated with the same key, even if they are not able to compute the ORE.Compare function.
In Section 4.1 we outline how to design data structures that leak no information about duplicates.
The structure of typical indexing data structure depends on the history of the transactions executed on the database. As an example, even if two databases store the same values, the topologies of their indexing data structures may difer if the insertion order of the values is not the same. Thus, the indexing data structure may leak information about the transactions history. Literature identified this security risk and denoted as history 2 0 1 3 4 5 (a) Insertion history SEQA = f3; 2; 4; 0; 1; 5g (b) Insertion history SEQB = f0; 1; 2; 3; 4; 5g independent the data structures whose topology and internal bit representation leak no information about the transaction history [32, 33]. In particular, we are interested in weakly history independent data structures, which guarantee history independence against adversaries which only observe the indexing data structure once [33], thus fitting the same snapshot ofline adversaries considered by ofline security guarantees of LWORE. The adversary that obtains a snapshot of a standard (history dependent) data structure may infer information about the transaction history, potentially also revealing information about the distribution of plaintexts if such distribution is not independent of the transaction history.
To clarify the type of information that a history dependent data structure may leak, we consider the example represented in Figure 2. We consider two Binary Search Trees (BSTs), both generated by providing the same set of values f0; : : : ; 5g in diferent orders. The first BST (Figure 2a) is built from the insertion sequence SEQA = f3; 2; 4; 0; 1; 5g. The second BST (Figure 2b) is built from insertion sequence SEQB = f0; 1; 2; 3; 4; 5g. The structure of the second BST leaks that data has been inserted within the database in ascending order.
Re-balancing the BST may help hiding information leakage related to the structure topology, however frequent re-balancing may critically afect performance and information may still leak from the internal bit representation [34]. Moreover, although history independent data structures have been designed for eficient range queries [ 35], they cannot be straightforwardly adopted to secure LW-ORE databases because they may leak duplicate values (see Section 3.2). In Section 4.2 we outline how to design secure history independent data structures that leak no information about duplicates.
We discuss how to design data structures that do not leak information. In Section 4.1 we describe alternative designs for search trees that avoid leaking information related to duplicate values, but that are still history dependent. In Section 4.2 we describe a history independent skip list without duplicates leakage.
----
------------
The duplicates leakage arises when a search tree stores two or more documents that are associated with same key (we may informally denote them as duplicate documents). As discussed in Section 3.2, standard search trees index duplicate documents by storing their identifiers within the same node. Thus, a variant design for search trees that do not leak information duplicates is to store only one identifier within each node. To this aim, it is necessary to design variant algorithms for insertion, search and deletion operations. We propose a candidate design for the AVL tree already considered in Section 3.2. In this paper, we keep the discussion informal and leave improved analyses as a future work.
When indexing a new document by a certain key, the insertion algorithm proceeds unmodified until the same key is found. Then, the algorithm creates a new node as a child of the existing one, deciding whether the new node should be assigned with the left or the right child position randomly with the same probability. If a node already exists at the assigned position, the sub-tree starting from that node is assigned as a child of the new one. When searching for a document, the search algorithm also proceeds unmodified until the target key is found. However, with regard to the original design, the search algorithm cannot assume that all pointers to documents are stored within that node. Instead, the search algorithm must continue descending into left and right sub-trees, collecting all the pointers stored within nodes associated with the same target key, and stopping descending a sub-tree when a node with a diferent key is found.
We propose an example of the algorithm by referring to Figure 3, which modifies the standard AVL tree described in Section 3.2 (Figure 1).
Although the proposed variant avoids duplicate keys being stored within the same node of the tree, it increases search complexity and thus may afect performance. Moreover, we observe that the variant is still history dependent.
We outline how to design an indexing data structure to avoid both information leakage due to duplicates and insertion history. The design is based on skip lists [36], which ofer inherently weakly history-independent topologies [35], and we denote it as doubly-linked skip list. First, we remind the main design traits of skip lists. Then, we describe the proposed variant design.
A skip list is a hierarchical data structure which includes multiple linked lists. At the bottom layer is the complete list of all the sorted values stored within the database. Each higher level consists of a sparse list which includes a subset of the elements of the list at the level below, and acts as a sort of “fast track” for quicker access. In particular, at insertion time each element has a probability to be promoted to the higher layer until promotion fail. Thus, the structure of the sparse list is completely independent of the contents of the lists or on the transaction history. The promotion probability p, which is typically set to 12 or 14 , determines the average size of the sparse lists.
Although the topology of the skip list is weakly history independent, it may still leak information about duplicates, because each node of the complete list typically stores all the identifiers associated with the same key, as already observed for search trees (see Section 3.2). For this reason, we propose a variant that we denote as doubly-linked skip list. Our design adopts the same unmodified superimposed sparse lists of a standard skip list. However, we operate two modifications: first, to avoid leaking duplicates we let each node of the complete list store only one document identifier (as we already detailed for search trees variants, see Section 4.1); second, to guarantee eficient lookup performance we design the complete list, which traditionally is a linked list with forward pointers only, as a doubly-linked list provided with both forward and backward pointers (which gives the name to our data structure).
We provide a better explanation of our design choices by analyzing how the proposed doubly-linked skip list evolves throughout insertion operations. To this aim, we consider the example represented in Figure 4, where we show three versions associated with an increasing number of inserted elements. Within the figure we slightly modify our notations and denote as cvn a right ciphertext cnR included within the data structure at “version” v, and idt the document identifier inserted via the tth operation. We also denote as L0 the complete list and as L1; : : : ; L3 the sparse lists. At the beginning (v = 1, Figure 4a), we consider a dataset without duplicate values (e.g., corresponding plaintext values are P^1 = h1; 2; 4i) which can be built by using an unmodified skip list insertion algorithm with the only diference that the complete list c1; c12; c13 is a doubly-linked list. 1 When a duplicate key is inserted into the data structure (see Figure 4b, where document identifier id4 is associated with right ciphertext c23 corresponding to plaintext p = 2), the insertion algorithm uses the sparse lists to access the complete list at the latest position that includes a key that is smaller or equal than the given insertion key, as the original skip list insertion algorithm. If a duplicate key is found, the new encrypted key is inserted after its position in the complete list. At insertion, the promotion algorithm is executed to decide whether new encrypted key should be added to upper layer sparse lists. In the example, c23 is inserted after c22 and is promoted to sparse list L1. Similarly,
L3 L2 L1
L0 END
END END END END (a) Initial index without duplicates (v = 1) (b) Index after insertion of a duplicate value (v = 2) (c) Index with all the values (v = 3) in Figure 4c (v = 3) we also insert values h4; 3; 5; 4i in this order. Now we consider searching value p = 4 within the index at version v = 3. The search algorithm finds the value within L2, and thus access the complete list at position 6 (c36). Now, it operates linear searches over the complete list both backward and forward until diferent values are found. Backward search finds c35 and stops at c34, and forward search finds c37 and stops at c38. The search operation would not be able to eficiently find backward duplicate values without adopting a doubly-linked list as complete list.
The proposed doubly-linked list outlines the main ideas for a secure indexing data structure for LW-ORE databases. Clearly, further analyses and improvements should be considered for obtaining good performance in real database systems, which we plan as future work.
We analyzed the security guarantees of a state-of-the-art order revealing encryption scheme when deployed in real database systems, and found issues related to information leakage due to gaps within the original security models and analyses. The most severe security issues are related to information leakage due to indexing data structures, including disclosure of duplicate values within the database and context information related to transactions history. These vulnerabilities may allow adversaries accessing a snapshot of the database to break semantic security guarantees claimed by the encryption scheme or, in certain scenarios, to infer information related to the order of the operations executed on the database and related statistical distributions. We described how variant indexing data structures may be modified to prevent both security issues, and outlined a candidate design based on skip lists. We leave a more formal treatment of the proposed analyses and the design of a complete proof of concept as future work.
We thank Mauro Leoncini for discussions on preliminary versions of this work. This work was supported by Doxee SpA in association with the European Regional Development Fund program “Por FESR 2014-2020” of Emilia-Romagna Region.
Internet Services and Applications (2018). [30] D. Bogatov, G. Kollios, L. Reyzin, A Comparative Evaluation of Order-Revealing Encryption Schemes and Secure Range-Query Protocols, in: Proc. Conf. Very Large Data Bases, 2019. [31] CipherStash, Order-revealing encryption library, https://github.com/cipherstash/ ore.rs, Visited Feb. 2023. [32] D. Micciancio, Oblivious data structures: applications to cryptography, in: Proc.
29th ACM Symp. Theory of Computing, 1997. [33] M. Naor, V. Teague, Anti-persistence: History independent data structures, in:
Proc. 33rd ACM Symp. Theory of Computing, 2001. [34] T. Moran, M. Naor, G. Segev, Deterministic history-independent strategies for storing information on write-once memories, in: Int’l Colloquium on Automata, Languages, and Programming, 2007. [35] M. A. Bender, J. W. Berry, R. Johnson, T. M. Kroeger, S. McCauley, C. A. Phillips, B. Simon, S. Singh, D. Zage, Anti-persistence on persistent storage: Historyindependent sparse tables and dictionaries, in: Proc. 35th ACM SIGMOD-SIGACTSIGAI Symp. Principles of Database Systems, 2016. [36] W. Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM (1990).