# Practical Frequency-Hiding Order-Preserving Encryption with Improved Update

Authors: JiHye Yang; Kee Sung Kim
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Order-preserving encryption (OPE) that preserves the numerical ordering of plaintexts is one of the promising solutions of cloud security. In 2013, an ideally secure OPE, which reveals no additional information except for the order of underlying plaintexts, was proposed, along with the notion (mutable encryption) that ciphertexts can be changed. Unfortunately, even the ideally secure OPE can be vulnerable by inferring the underlying frequency of repeated plaintexts. To solve this problem, in 2015, Kerschbaum designed a frequency-hiding OPE (FH-OPE) scheme based on the notion of a randomized order under the strengthened security model. Later, Maffei et al. has shown that Kerschbaum’s model is imprecise, which means no such OPE scheme can exist. Moreover, they provided a new FH-OPE scheme under the corrected security model. However, their scheme requires the order information of all the encrypted plaintexts as an input; therefore, it causes relatively high overhead during encryption. In this work, we propose a more efficient FH-OPE based on Maffei et al.’ s security model and also present an improved update algorithm suitable for duplicate plaintexts.


---

## Body

## 1. Introduction

Cloud storage has become a common practice in recent years, but it still has privacy concerns with respect to the service provider hosting the data. In these data-outsourcing scenarios, encryption is one of the most reliable solutions. However, the existing normal encryption schemes have limitations; for instance, it is impossible to perform operations, e.g., range query, on encrypted data. To perform such operations, the client has to download all the encrypted data and decrypt them. To overcome these limitations, few solutions have been proposed by slightly weakening the security of the normal encryption schemes. Order-preserving encryption is one of the promising solutions and allows a client to perform efficient range queries on the encrypted data because it maintains the ordering of plaintexts in ciphertexts.


### 1.1. Related Works

The first concept of order-preserving encryption was introduced by Agrawal et al. [1]. In 2009, Boldyreva et al. [2] presented the first formal security notion of OPE, which is called indistinguishability against ordered chosen plaintext attacks (IND-OCPA). Moreover, they showed that any stateless OPE cannot guarantee the IND-OCPA security unless the ciphertext space is exponentially large in the plaintext space. They also presented the weaker security notion, which is known as pseudorandom order-preserving function advantage under chosen ciphertext attacks (POPF-CCA). However, this security model does not precisely quantify the leakage information of plaintexts. Later, Boldyreva et al. [3] and Xiao and Yen [4] showed that ciphertexts of [2] scheme leak approximately the first half bits of the underlying plaintexts. Yum et al. [5] improved Boldyreva’s construction by extending their work to nonuniformly distributed plaintexts but still remained in the same security level of random order-preserving functions. Subsequently, few OPE schemes [6–15] that provide no formal security proof were proposed, but rather they provided an ad hoc security analysis.Recently, some ideally secure (IND-OCPA secure) OPE schemes [16–20], which are stateful or interactive, have been proposed. Popa et al. [18] developed an interactive model for clients and servers as a two-party protocol. The client encrypts plaintexts using a deterministic OPE algorithm and sends them to the server that maintains a search tree where ciphertexts are stored. When the client wants to perform range queries on the encrypted data, the server exploits the search tree. Moreover, they presented a notion of mutable encryption, which means that ciphertexts can be updated to achieve the IND-OCPA security. Their interacting scheme requires a large amount of communication. In 2014, Kerschbaum and Schröpfer [19] presented a revised ideally secure OPE scheme where the client stores the search tree. This approach makes it possible for their scheme to incur lower communication cost than that proposed by [18].To solve the problem of deterministic OPE [1, 3, 18, 19, 21, 22] that are vulnerable to frequency analysis, sorting, and cumulative attack [23], Kerschbaum [16] presented a new frequency-hiding OPE to apply randomization to duplicate plaintexts. In addition, they introduced a stronger security notion than IND-OCPA, which is known as indistinguishability against frequency-analyzing ordered chosen plaintext attacks (IND-FA-OCPA). In 2017, Maffei et al. [17] has shown that Kerschbaum’s security model is imprecise. Therefore, they designed a new construction based on the corrected security model. However, their scheme causes relatively high overhead during encryption due to requiring the order information of all encrypted plaintexts. Moreover, we figure out that the update algorithm used in [16, 17] cannot guarantee to produce a perfectly balanced search tree when duplicate plaintexts are encrypted.Yang et al. [24] presented a semiorder-preserving encryption (SOPE) although with the sacrifice of the precision of order-preserving. In this scheme, two different plaintexts may be encrypted to the same ciphertext; thus, the ciphertext sequence cannot be mapped to a plaintext. Dyer et al. [25] presented OPE scheme based on the general approximate common divisor problem (GACDP). This approach is the first OPE scheme using a computational hardness, not on a security game. Like Liu and Wang [9], their scheme adds random noise to the initial plaintext so that if there are duplicate plaintexts, the ciphertexts seem like distinct. Kim [26] showed a new OPE scheme based on order-revealing encryption (ORE) and improved the round and client side storage complexities on the exiting ideally secure OPE [16, 20]. Tueno and Kerschbaum [27] introduced an oblivious OPE (OOPE) as an equivalent of a public-key OPE; they also showed a protocol for OOPE that combines existing ideally secure OPE [16, 19] with Paillier’s homomorphic encryption and garbled circuits. In [28], Taigel et al. presented a real-life use case that combines OPE and decision tree classification to enable privacy-preserving forecasting of demand for spare parts based on distributed condition data. In [29], Meng and Feigenbaum described an application of OPE that combines OPE, pseudorandom functions (PRFs), and additively homomorphic encryption (AHE) to design a privacy-preserving XGBoost inference algorithm, that is, to create an encrypted regression tree.


### 1.2. Our Contributions

Table1 shows the comparison of the existing FH-OPE schemes. As mentioned before, the original definition of IND-FA-OCPA of [16] is imprecise, and their FH-OPE scheme is insecure under the security model that they proposed. In fact, no FH-OPE scheme that can be proven under their security model can exist. The scheme of [17] guarantees the IND-FA-OCPA security that has been revised to be feasible, but the client has to maintain the order information of all the encrypted plaintexts to date; this maintenance causes inefficiency in the client’s persistent storage and the encryption performance.Table 1
Comparison among the existing FH-OPE schemes.
Open schemeEncryption costSecurityAdditional persistent storageImproved updateNoteBestWorst[16]OlognOlognIND-OCPA—XImprecise[17]OlognOnIND-FA-OCPAOnlognXImpracticalOursOlognOlognIND-FA-OCPA—O—n∗ is the number of plaintexts to be encrypted. Additional persistent storage means the information a client should maintain except for the search tree. Encryption cost denotes the computational complexity of encryption except for the rebalancing of the search tree.To summarize, our contributions are as follows:(i)
We propose a more practical FH-OPE scheme compared with the previous schemes. Our scheme does not require the order information of all the encrypted plaintexts; thus, the client does not need to maintain them. The security of the proposed scheme can be proven considering the IND-FA-OCPA security model of [17].(ii)
We figure out that the update algorithm in [16, 17] is not suitable for random duplicate distributions. Moreover, it cannot guarantee to produce a perfectly balanced search tree when duplicate plaintexts are encrypted. To overcome this problem, we propose an improved update algorithm. The proposed algorithm always produces a perfectly balanced search tree regardless of the distribution of plaintexts and positively affects the overall performance of FH-OPE.(iii)
We implement the schemes of [16, 17] and the proposed scheme and evaluate the schemes based on different plaintext distributions. Among others, the implementation results show the excellence of our scheme.


### 1.3. Outline

In Section2, we recall the formal notion of (stateful) OPE and its security definitions. In Section 3, we analyze the scheme proposed by [17] and present that the scheme still needs to be improved in terms of storage and computational complexity. Section 4 proposes a new practical FH-OPE scheme and an improved update algorithm and shows that the proposed scheme achieves the IND-FA-OCPA security. We present the experimental results in Section 5. Finally, we conclude our work in Section 6.


## 1.1. Related Works

The first concept of order-preserving encryption was introduced by Agrawal et al. [1]. In 2009, Boldyreva et al. [2] presented the first formal security notion of OPE, which is called indistinguishability against ordered chosen plaintext attacks (IND-OCPA). Moreover, they showed that any stateless OPE cannot guarantee the IND-OCPA security unless the ciphertext space is exponentially large in the plaintext space. They also presented the weaker security notion, which is known as pseudorandom order-preserving function advantage under chosen ciphertext attacks (POPF-CCA). However, this security model does not precisely quantify the leakage information of plaintexts. Later, Boldyreva et al. [3] and Xiao and Yen [4] showed that ciphertexts of [2] scheme leak approximately the first half bits of the underlying plaintexts. Yum et al. [5] improved Boldyreva’s construction by extending their work to nonuniformly distributed plaintexts but still remained in the same security level of random order-preserving functions. Subsequently, few OPE schemes [6–15] that provide no formal security proof were proposed, but rather they provided an ad hoc security analysis.Recently, some ideally secure (IND-OCPA secure) OPE schemes [16–20], which are stateful or interactive, have been proposed. Popa et al. [18] developed an interactive model for clients and servers as a two-party protocol. The client encrypts plaintexts using a deterministic OPE algorithm and sends them to the server that maintains a search tree where ciphertexts are stored. When the client wants to perform range queries on the encrypted data, the server exploits the search tree. Moreover, they presented a notion of mutable encryption, which means that ciphertexts can be updated to achieve the IND-OCPA security. Their interacting scheme requires a large amount of communication. In 2014, Kerschbaum and Schröpfer [19] presented a revised ideally secure OPE scheme where the client stores the search tree. This approach makes it possible for their scheme to incur lower communication cost than that proposed by [18].To solve the problem of deterministic OPE [1, 3, 18, 19, 21, 22] that are vulnerable to frequency analysis, sorting, and cumulative attack [23], Kerschbaum [16] presented a new frequency-hiding OPE to apply randomization to duplicate plaintexts. In addition, they introduced a stronger security notion than IND-OCPA, which is known as indistinguishability against frequency-analyzing ordered chosen plaintext attacks (IND-FA-OCPA). In 2017, Maffei et al. [17] has shown that Kerschbaum’s security model is imprecise. Therefore, they designed a new construction based on the corrected security model. However, their scheme causes relatively high overhead during encryption due to requiring the order information of all encrypted plaintexts. Moreover, we figure out that the update algorithm used in [16, 17] cannot guarantee to produce a perfectly balanced search tree when duplicate plaintexts are encrypted.Yang et al. [24] presented a semiorder-preserving encryption (SOPE) although with the sacrifice of the precision of order-preserving. In this scheme, two different plaintexts may be encrypted to the same ciphertext; thus, the ciphertext sequence cannot be mapped to a plaintext. Dyer et al. [25] presented OPE scheme based on the general approximate common divisor problem (GACDP). This approach is the first OPE scheme using a computational hardness, not on a security game. Like Liu and Wang [9], their scheme adds random noise to the initial plaintext so that if there are duplicate plaintexts, the ciphertexts seem like distinct. Kim [26] showed a new OPE scheme based on order-revealing encryption (ORE) and improved the round and client side storage complexities on the exiting ideally secure OPE [16, 20]. Tueno and Kerschbaum [27] introduced an oblivious OPE (OOPE) as an equivalent of a public-key OPE; they also showed a protocol for OOPE that combines existing ideally secure OPE [16, 19] with Paillier’s homomorphic encryption and garbled circuits. In [28], Taigel et al. presented a real-life use case that combines OPE and decision tree classification to enable privacy-preserving forecasting of demand for spare parts based on distributed condition data. In [29], Meng and Feigenbaum described an application of OPE that combines OPE, pseudorandom functions (PRFs), and additively homomorphic encryption (AHE) to design a privacy-preserving XGBoost inference algorithm, that is, to create an encrypted regression tree.


## 1.2. Our Contributions

Table1 shows the comparison of the existing FH-OPE schemes. As mentioned before, the original definition of IND-FA-OCPA of [16] is imprecise, and their FH-OPE scheme is insecure under the security model that they proposed. In fact, no FH-OPE scheme that can be proven under their security model can exist. The scheme of [17] guarantees the IND-FA-OCPA security that has been revised to be feasible, but the client has to maintain the order information of all the encrypted plaintexts to date; this maintenance causes inefficiency in the client’s persistent storage and the encryption performance.Table 1
Comparison among the existing FH-OPE schemes.
Open schemeEncryption costSecurityAdditional persistent storageImproved updateNoteBestWorst[16]OlognOlognIND-OCPA—XImprecise[17]OlognOnIND-FA-OCPAOnlognXImpracticalOursOlognOlognIND-FA-OCPA—O—n∗ is the number of plaintexts to be encrypted. Additional persistent storage means the information a client should maintain except for the search tree. Encryption cost denotes the computational complexity of encryption except for the rebalancing of the search tree.To summarize, our contributions are as follows:(i)
We propose a more practical FH-OPE scheme compared with the previous schemes. Our scheme does not require the order information of all the encrypted plaintexts; thus, the client does not need to maintain them. The security of the proposed scheme can be proven considering the IND-FA-OCPA security model of [17].(ii)
We figure out that the update algorithm in [16, 17] is not suitable for random duplicate distributions. Moreover, it cannot guarantee to produce a perfectly balanced search tree when duplicate plaintexts are encrypted. To overcome this problem, we propose an improved update algorithm. The proposed algorithm always produces a perfectly balanced search tree regardless of the distribution of plaintexts and positively affects the overall performance of FH-OPE.(iii)
We implement the schemes of [16, 17] and the proposed scheme and evaluate the schemes based on different plaintext distributions. Among others, the implementation results show the excellence of our scheme.


## 1.3. Outline

In Section2, we recall the formal notion of (stateful) OPE and its security definitions. In Section 3, we analyze the scheme proposed by [17] and present that the scheme still needs to be improved in terms of storage and computational complexity. Section 4 proposes a new practical FH-OPE scheme and an improved update algorithm and shows that the proposed scheme achieves the IND-FA-OCPA security. We present the experimental results in Section 5. Finally, we conclude our work in Section 6.


## 2. Preliminaries

This section briefly recalls the formal notion of OPE and its security definitions.


### 2.1. Order-Preserving Encryption

The OPE scheme is defined in two ways: stateless and stateful. A stateless scheme is difficult to achieve the IND-OCPA security. Instead of the stateful OPE being a key-less scheme, a state operates as a secret key.Definition 1.
(stateful OPE). A stateful OPE scheme consists of the following three algorithms (Setup, Encryption, and Decryption):(i)
S⟵Setup1λ: the Setup algorithm takes as an input a security parameter λ and outputs a state S.(ii)
S′,y⟵Encryptionx,S: the Encryption algorithm takes as input a plaintext x and a state S. It outputs a ciphertext y and updates the state S to S′.(iii)
x⟵Decryptiony,S: the Decryption algorithm takes as input a ciphertext y and a state S. It outputs a plaintext x.Definition 2.
(order-preserving). An OPE scheme is order-preserving if for any two ciphertextsy1 and y2 with corresponding messages x1 and x2, we have y1≥y2⇒x1≥x2.


### 2.2. Security Definitions

The standard security notion of OPE is IND-OCPA [2]. It means that an adversary cannot know anything about plaintexts except for their order. Let n be the number of necessarily distinct plaintexts in sequence X=x1,x2,…,xn, where xi∈ℕ for all i. The security game GameIND-OCPAλ between the adversary A and challenger C for the security parameter λ proceeds as follows:(1)
The adversaryA prepares two sequences X0 and X1 of necessarily distinct plaintexts with the same order. He sends them to the challenger C.(2)
The challengerC randomly chooses b←0,1, executes the Setup 1λ, and runs yi,b,Si←Encryptionxi,b,Si−1. He sends y1≤i≤n,b to the adversary A.(3)
The adversaryA guesses which sequence is encrypted and accordingly outputs guess b′.We say that the adversaryA wins GameIND-OCPAλ if b=b′. Let WinocpaA,λ be the winning probability of A in GameIND-OCPAλ.Definition 3.
(IND-OCPA). A stateful OPE scheme is IND-OCPA secure if for any PPT adversaryA, WinocpaA,λ is negligible in the security parameter λ, i.e.,(1)PrWinocpaA,λ<12+neglλ.
Now, we review IND-FA-OCPA, which is originally presented in [16] and modified in [17]. To capture “frequency-hiding” security, it allows duplicate plaintexts, e.g., X=1,1,1,1,X′=1,2,3,3, and X′′=2,2,4,4. However, two challenge sequences X0 and X1 have at least one common randomized order Γ. A randomized order Γ of X means any possible permutation of 1,2,…,X is placed in an order according to X, and the order of duplicate plaintexts is randomly determined. For example, with X=1,1,3,3, the randomized order Γ for X can be any of Γ1=1,2,3,4, Γ2=1,2,4,3, Γ3=2,1,3,4, or Γ4=2,1,4,3. The randomized order Γ is precisely defined as follows.Definition 4.
(randomized order). Letn be the number of plaintexts in a sequence X=x1,x2,…,xn that are not necessarily distinct, where xi∈ℕ for all i. A randomized order Γ=γ1,γ2,…,γn, where 1≤γi≤n and i≠j⇒γi≠γj for all i and j of sequence X, it holds that(2)∀i,j.xi>xj⟹γi>γj∧γi>γj⟹xi≥xj.
Two sequencesX0=1,3,3,3 and X1=1,2,3,3 have only two common randomized order: Γ1=1,2,3,4 and Γ2=1,2,4,3. Γ↓i denotes the order of the sequences γ1,…γi. For instance, Γ↓3 of Γ=3,5,1,2,4 means 2,3,1.
The security gameGameIND-FA-OCPAλ between an adversary A and a challenger C for a security parameter λ proceeds as follows:(1)
The adversaryA prepares two sequences X0 and X1 that have at least one common randomized order. He sends them to the challenger C.(2)
The challengerC randomly chooses b⟵0,1 and selects Γ from the common randomized orders of X0 and X1. Then, the challenger C executes the Setup 1λ and runs yi,b, yi,b,Si⟵Encryptionxi,b,Si−1 based on Γ↓i. It means that the relative order of duplicate plaintexts is determined by Γ↓i. He sends y1≤i≤n,b to the adversary A.(3)
The adversaryA guesses which sequence is encrypted and accordingly outputs the guess b′.
We say that the adversaryA wins GameIND−FA−OCPAλ if b=b′. Let Winfa−ocpaA,λ be the winning probability of A in GameIND−FA−OCPAλ.Definition 5.
(IND-FA-OCPA). A FH-OPE scheme is IND-FA-OCPA secure if for any PPT adversaryA, Winfa−ocpaA,λ is negligible in the security parameter λ, i.e.,(3)PrWinfa−ocpaA,λ<12+neglλ.
As the randomized order of distinct plaintexts is equal to its order, the IND-FA-OCPA security is stronger than IND-OCPA.


## 2.1. Order-Preserving Encryption

The OPE scheme is defined in two ways: stateless and stateful. A stateless scheme is difficult to achieve the IND-OCPA security. Instead of the stateful OPE being a key-less scheme, a state operates as a secret key.Definition 1.
(stateful OPE). A stateful OPE scheme consists of the following three algorithms (Setup, Encryption, and Decryption):(i)
S⟵Setup1λ: the Setup algorithm takes as an input a security parameter λ and outputs a state S.(ii)
S′,y⟵Encryptionx,S: the Encryption algorithm takes as input a plaintext x and a state S. It outputs a ciphertext y and updates the state S to S′.(iii)
x⟵Decryptiony,S: the Decryption algorithm takes as input a ciphertext y and a state S. It outputs a plaintext x.Definition 2.
(order-preserving). An OPE scheme is order-preserving if for any two ciphertextsy1 and y2 with corresponding messages x1 and x2, we have y1≥y2⇒x1≥x2.


## 2.2. Security Definitions

The standard security notion of OPE is IND-OCPA [2]. It means that an adversary cannot know anything about plaintexts except for their order. Let n be the number of necessarily distinct plaintexts in sequence X=x1,x2,…,xn, where xi∈ℕ for all i. The security game GameIND-OCPAλ between the adversary A and challenger C for the security parameter λ proceeds as follows:(1)
The adversaryA prepares two sequences X0 and X1 of necessarily distinct plaintexts with the same order. He sends them to the challenger C.(2)
The challengerC randomly chooses b←0,1, executes the Setup 1λ, and runs yi,b,Si←Encryptionxi,b,Si−1. He sends y1≤i≤n,b to the adversary A.(3)
The adversaryA guesses which sequence is encrypted and accordingly outputs guess b′.We say that the adversaryA wins GameIND-OCPAλ if b=b′. Let WinocpaA,λ be the winning probability of A in GameIND-OCPAλ.Definition 3.
(IND-OCPA). A stateful OPE scheme is IND-OCPA secure if for any PPT adversaryA, WinocpaA,λ is negligible in the security parameter λ, i.e.,(1)PrWinocpaA,λ<12+neglλ.
Now, we review IND-FA-OCPA, which is originally presented in [16] and modified in [17]. To capture “frequency-hiding” security, it allows duplicate plaintexts, e.g., X=1,1,1,1,X′=1,2,3,3, and X′′=2,2,4,4. However, two challenge sequences X0 and X1 have at least one common randomized order Γ. A randomized order Γ of X means any possible permutation of 1,2,…,X is placed in an order according to X, and the order of duplicate plaintexts is randomly determined. For example, with X=1,1,3,3, the randomized order Γ for X can be any of Γ1=1,2,3,4, Γ2=1,2,4,3, Γ3=2,1,3,4, or Γ4=2,1,4,3. The randomized order Γ is precisely defined as follows.Definition 4.
(randomized order). Letn be the number of plaintexts in a sequence X=x1,x2,…,xn that are not necessarily distinct, where xi∈ℕ for all i. A randomized order Γ=γ1,γ2,…,γn, where 1≤γi≤n and i≠j⇒γi≠γj for all i and j of sequence X, it holds that(2)∀i,j.xi>xj⟹γi>γj∧γi>γj⟹xi≥xj.
Two sequencesX0=1,3,3,3 and X1=1,2,3,3 have only two common randomized order: Γ1=1,2,3,4 and Γ2=1,2,4,3. Γ↓i denotes the order of the sequences γ1,…γi. For instance, Γ↓3 of Γ=3,5,1,2,4 means 2,3,1.
The security gameGameIND-FA-OCPAλ between an adversary A and a challenger C for a security parameter λ proceeds as follows:(1)
The adversaryA prepares two sequences X0 and X1 that have at least one common randomized order. He sends them to the challenger C.(2)
The challengerC randomly chooses b⟵0,1 and selects Γ from the common randomized orders of X0 and X1. Then, the challenger C executes the Setup 1λ and runs yi,b, yi,b,Si⟵Encryptionxi,b,Si−1 based on Γ↓i. It means that the relative order of duplicate plaintexts is determined by Γ↓i. He sends y1≤i≤n,b to the adversary A.(3)
The adversaryA guesses which sequence is encrypted and accordingly outputs the guess b′.
We say that the adversaryA wins GameIND−FA−OCPAλ if b=b′. Let Winfa−ocpaA,λ be the winning probability of A in GameIND−FA−OCPAλ.Definition 5.
(IND-FA-OCPA). A FH-OPE scheme is IND-FA-OCPA secure if for any PPT adversaryA, Winfa−ocpaA,λ is negligible in the security parameter λ, i.e.,(3)PrWinfa−ocpaA,λ<12+neglλ.
As the randomized order of distinct plaintexts is equal to its order, the IND-FA-OCPA security is stronger than IND-OCPA.


## 3. Maffei Et Al.’s FH-OPE Scheme

We review the FH-OPE scheme of [17] in detail. The main idea is that the client maintains the randomized order Γ of all encrypted plaintexts and uses it as one of the inputs of the encryption algorithm. It externally determines their relative order for duplicate plaintexts in the encryption algorithm. A search tree T that maps plaintexts to ciphertexts is stored as a state S on the client side and used in the decryption algorithm. For a node of t of T, t.m and t.c represent a plaintext and a corresponding ciphertext. t.left and t.right denote the left and right child of t, respectively. Every node t in T stores its index based on the plaintext sequence. N is the number of distinct plaintexts, and n is the number of plaintexts in the sequence to be encrypted, which also means Γ. k is the number of plaintexts encrypted and stored on the server so far. M denotes the number of distinct ciphertexts, and its bit length is expanded by a factor of λ, i.e., OλlogN. As described in Algorithm 1, the state S comprises min, max, and T. When the search tree T is empty, the state min,max is initialized as 0,M. The update (tree rebalancing) algorithm is as described in [16].Algorithm 1: Encryption [17].
Input: x, S, and Γ=γ1,…,γkOutput: yState: S=t,min,maxift is empty thent.m=xt.index=kt.c=min+⌈max−min/2⌉ift.c=0thenrebalance the treereturnt.cb⟵−1ifx=t.mthenb⟵γk>γt.indexifb=1∨x>t.mthenEncryptionx,t.right,t.c,max,Γelseifb=0∨x<t.mthenEncryptionx,t.left,t.c,max,ΓTo review their scheme, we present a concrete example. Figure1 shows the encryption results of 1,1,1,1, where M=128. Here, we set the possible randomized order Γ of 1,1,1,1 to 3,2,4,1.Figure 1
Each resulting search tree of1,1,1,1 in [17].We can check that the algorithm produces ciphertexts64,32,96,16 properly based on Γ. However, Γ should be updated continuously with each encryption. For the mutable OPE schemes whose state is stored on the client side, the computational cost of rebalancing T is similar; thus, it will be excluded from the following efficiency analysis.Computational Cost. The encryption algorithm [17] has computational complexities Ologn and On, except the rebalancing T in the best and worst cases, respectively. This is because in the search tree, the cost of finding an empty node and placing a plaintext based on T required for each encryption is Ologn. In addition, the cost of updating Γ is required. In the case of increasing sequential plaintexts, e.g., x1=10, then Γ=1; x2=20, then Γ=1,2; and x3=30, then Γ=1,2,3; the cost of updating Γ is O1. On the other hand, for decreasing sequential plaintexts, e.g., x1=30, then Γ=1; x2=20, then Γ=2,1; and x3=10, then Γ=3,2,1; the cost of updating Γ is On.Storage Cost. There are n elements in Γ, and each can be represented by logn bits. Thus, the client requires Onlogn bits for additional persistent storage, except for T.Rebalancing Tree. In [16, 17], if there is no available ciphertext in T, it has to be rebalanced by calling the update algorithm. However, the algorithm presented in [19] was designed assuming that there were no duplicate plaintexts. Therefore, the algorithm cannot guarantee to produce a perfectly balanced tree when duplicate plaintexts are encrypted. The result quality of the update algorithm significantly impacts the overall performance; thus, a new improved algorithm is needed.


## 4. Proposed Scheme

We propose a practical FH-OPE scheme described in Algorithm2 that achieves the IND-FA-OCPA security with an improved update algorithm. Our search tree T does not need to store the index of the encrypted plaintexts. Let H: 0,1∗⟶0,1 be a hash function with 1-bit output modeled as a random oracle. Our main idea is to replace the inefficient input Γ with the combination of a single random value r⟵0,1ployλ and H. In our scheme, the selection of empty nodes for duplicate plaintexts is determined by Hr‖count. It means that the order of duplicate plaintexts is not determined internally but intended externally. The other notations and the initialization T are defined as described in the previous sections.Algorithm 2: Our encryption.
Input: x, S, and r‖countOutput: yState: S=t,min,maxifcount=nullthencount=1ifmax−min=1thenUpdate()elseift is Empty thent.m=xt.c=min+⌈max−min/2⌉returnt.celseifx<t.mthenEncryptionx,t.left,min,t.cr‖countelse if x=t.xthenb⟵Hr‖countcount ++ifb=0thenEncryptionx,t.left,min,t.c,r‖countelseEncryptionx,t.left,min,t.c,r‖countelseEncryptionx,t.left,t.c,max,r‖countFigure2 shows the encryption of duplicate plaintexts {1, 1, 1, 1} based on our scheme. We can check that the algorithm produces distinct ciphertexts {64, 96, 80, 112} based on the chosen random values, e.g., r′′ has the same role as Γ=1,3,2,4 in [17].Figure 2
Each resulting search tree of1,1,1,1 based on our scheme.The existing update algorithm for FH-OPE [16, 17, 19] sorts the plaintext sequence X=t.m1,t.m2,…,t.mn in ascending order and simply re-encrypts the sequence. The algorithms cannot guarantee to produce a perfectly balanced tree because the node positions are randomly selected for the duplicate plaintexts. The idea of our improved update Algorithm 3 is simple. We build a new search tree T∗ on 1,2,…,n where n is the number of nodes in T and replace t∗.mi with t.mi, where 1≤i≤n. We check that the resulting T∗ is a perfectly balanced tree because it has been built based on the distinct plaintexts.Algorithm 3: Our update.
Input: a set of t.m in tree TOutput: a balanced search tree T∗Initialization: a new empty search tree T∗n= the number of nodes in TEncryption⌈n/2⌉,t∗.root,nullifn=2thenEncryption⌈n/2⌉,t∗.root,nullifn=3thenEncryption⌈n/2⌉,t∗.root,nullEncryption⌈n/2⌉,t∗.root,nullifn>3thenUpdate1,2,…,⌈n/2⌉−1Update⌈n/2⌉+1,…,n−1,nif End recursively iterate thenCallX=t.m1,…,t.mn in ascending orderCallX=t∗.m1,…,t∗.mn in ascending orderforj⟵1tondot∗.mj⟵t.mjreturn treeT∗In stateful OPE, the decryption algorithm can be omitted by the state that is stored on client side. However, this omission is without loss of correctness of OPE scheme. To decrypt a given ciphertexty, he uses the binary search tree T and finds the node t that includes t.m and t.c where t.c=y. Thus, he can simply decrypt the ciphertext y and return a plaintext x by performing the binary search.Next, we will prove the security of our proposed scheme with regard to the IND-FA-OCPA security model and analyze our construction in terms of efficiency.Theorem 1.
LetΓ denote any possible randomized order of the plaintext sequence X. YΓ denotes the ciphertext sequence when Γ is used as plaintexts. Then, the challenger C in IND-FA-OCPA can always simulate the ciphertexts of X, which is identical to YΓ.Proof.
In the encryption algorithm ofx1≤i≤n, let bi,j be the outputs of Hri‖j, where count=j. Then, we can compute bi,j, which is identical to the search tree as if Γ is encrypted. As shown in Figure 2, we can obtain b2,1=1, b3,1=1, b3,2=0, b4,1=1, and b4,2=1 for Γ=1,3,2,4. Finally, the challenger C chooses n random values r1,r2,…,rn and simulates the random oracle H as bi,j⟵Hri‖j; otherwise, it returns a bit chosen randomly.
Based on Theorem1, if the challenger C outputs YΓ in step 3 of IND-FA-OCPA, where Γ is the chosen common randomized order in the step 2, there is no advantage for an attacker A to distinguish X0 and X1.
Efficiency. The security in Table 1 demonstrates that the scheme of [16] achieves only the IND-OCPA security and shows that Kerschbaum’s model is imprecise, which means no such FH-OPE can exist. Furthermore, both [16, 17] do not provide an improved update algorithm. We can know that the proposed update algorithm positively affects the computational performance through some experiments in Section 5. Compared with [17], our scheme does not require the order information of all the encrypted plaintext while Maffei’s scheme requires Onlogn bits for additional persistent storage, except for a state. Moreover, a series of sorting every element in the randomized order Γ causes very low computational performance of [17] because these operations occur whenever a plaintext is inserted into the encryption algorithm of [17].


## 5. Experiments

We analyze the performance of [16, 17] and the proposed scheme using a system that includes an AMD Ryzen 5 3600 6-core processor 3.59 GHz, 16 GB RAM in Python 3.9.5. We use different plaintext sizes N and the number of plaintexts to be encrypted n, but the ciphertext size M is fixed at 2048.


### 5.1. Random Duplicate Plaintexts

Figure3 shows the comparison of the encryption of n plaintexts that are randomly selected in 1,2,…,N, allowing duplicates, where n∈128,256,384,512,640,768,896,1024 and the corresponding N∈64,128,192,256,320,384,448,512. As the main operation of [17] is to maintain the order of all encrypted plaintexts, their scheme requires additional Γ updates except for the ciphertext updates. Figure 3 shows that scheme of [17] exhibits lower performance than the other.Figure 3
Encryption time of [16, 17] and ours based on random duplicate plaintexts.


### 5.2. Random Distinct Plaintexts

Here, we encryptn plaintexts that are selected randomly in 1,2,…,N, not allowing duplicates where n=N. Figure 4 shows that the overall speed improved in all the schemes owing to the blockage of the duplicate plaintexts, but the encryption time of [17] is more than the other.Figure 4
Encryption time of [16, 17] and ours based on random distinct plaintexts.


### 5.3. Sequential Plaintexts

We encrypt plaintextsN,N−1,…,1, where N∈128,256,384,512,640,768,896,1024. As these plaintexts cause the rebalancing tree most frequently, Figure 5 shows that all the schemes take more time to encrypt data owing to the frequent updates of search tree. However, as the number of plaintexts to be encrypted increases, the encryption time of the scheme [17] sharply increases.Figure 5
Encryption time of [16, 17] and ours based on sequential plaintexts.


### 5.4. Ciphertext Update Cost

In this section, we prove that our update algorithm is better than other algorithms. We encryptn plaintexts that are selected randomly in 1,2,…,N, allowing duplicates where n∈128,256,384,512,640,768,896,1024 and the corresponding N∈64,128,192,256,320,384,448,512. In our update algorithm, there is no case of producing worst case that the update algorithm outputs a skewed search tree. The update algorithm in [16, 17] may produce the unbalanced search tree after executing the ciphertext updates. Therefore, Figure 6 shows that the number of updates in our case is relatively small.Figure 6
The number of updates of [16, 17] and ours based on random duplicate plaintexts.


## 5.1. Random Duplicate Plaintexts

Figure3 shows the comparison of the encryption of n plaintexts that are randomly selected in 1,2,…,N, allowing duplicates, where n∈128,256,384,512,640,768,896,1024 and the corresponding N∈64,128,192,256,320,384,448,512. As the main operation of [17] is to maintain the order of all encrypted plaintexts, their scheme requires additional Γ updates except for the ciphertext updates. Figure 3 shows that scheme of [17] exhibits lower performance than the other.Figure 3
Encryption time of [16, 17] and ours based on random duplicate plaintexts.


## 5.2. Random Distinct Plaintexts

Here, we encryptn plaintexts that are selected randomly in 1,2,…,N, not allowing duplicates where n=N. Figure 4 shows that the overall speed improved in all the schemes owing to the blockage of the duplicate plaintexts, but the encryption time of [17] is more than the other.Figure 4
Encryption time of [16, 17] and ours based on random distinct plaintexts.


## 5.3. Sequential Plaintexts

We encrypt plaintextsN,N−1,…,1, where N∈128,256,384,512,640,768,896,1024. As these plaintexts cause the rebalancing tree most frequently, Figure 5 shows that all the schemes take more time to encrypt data owing to the frequent updates of search tree. However, as the number of plaintexts to be encrypted increases, the encryption time of the scheme [17] sharply increases.Figure 5
Encryption time of [16, 17] and ours based on sequential plaintexts.


## 5.4. Ciphertext Update Cost

In this section, we prove that our update algorithm is better than other algorithms. We encryptn plaintexts that are selected randomly in 1,2,…,N, allowing duplicates where n∈128,256,384,512,640,768,896,1024 and the corresponding N∈64,128,192,256,320,384,448,512. In our update algorithm, there is no case of producing worst case that the update algorithm outputs a skewed search tree. The update algorithm in [16, 17] may produce the unbalanced search tree after executing the ciphertext updates. Therefore, Figure 6 shows that the number of updates in our case is relatively small.Figure 6
The number of updates of [16, 17] and ours based on random duplicate plaintexts.


## 6. Conclusion

We review the construction presented by Maffei et al. and conclude that the scheme still needs to be improved in terms of storage and computational complexity. Then, we propose a more practical FH-OPE scheme with the formal IND-FA-OCPA security proof. Moreover, we figure out that the previous update algorithms are not suitable for the duplicate plaintexts and propose an improved update algorithm that helps produce a perfectly balanced search tree regardless of the distribution of the plaintexts. Finally, we present some experimental results to demonstrate the excellence of the proposed scheme.



---

*Source: 1160305-2021-12-06.xml*