## Kee Sung Kim*## |

Scheme | Rounds | Client storage | Security | Note | ||
---|---|---|---|---|---|---|

Insert | Query | Working | Persistent | |||

Previous constructions | ||||||

[1] | 1 | 1 | O(n) | O(n) | Ideal | F.H. |

[2] | 1 | O(1) | [TeX:] $$\begin{array}{c}{O\left(n^{\varepsilon}\right)} \\ {(0<\varepsilon<1)}\end{array}$$ | O(1) | Ideal | F.H. Partial OPE |

Our constructions | ||||||

Based on [3] | 1 | 1 | O(1) | O(1) | Diff. Bit | - |

Based on [4] | 1 | 1 | O(1) | O(1) | Diff. Block | - |

Based on [5] | 1 | 1 | O(1) | O(1) | Ideal | Impractical |

n is the total number of encrypted data in EDB. Diff. Bit (Block) indicates the position of the first differing bit (block) of two corresponding plaintexts. F.H. means the frequency-hiding property. Partial OPE means a sizable fraction of ciphertexts in EDB remains incomparable.

^{a} Worst case: O(n), ^{b} worst case: [TeX:] $$O\left(n^{1-\varepsilon}\right).$$

The rest paper is organized as follows: Section 2 reviews the formal notion and security of OREnc (OPEnc). In Section 3, we propose our new construction of OPEnc based on OREnc. In Section 4, we analyze our construction. Section 5 concludes this paper.

We write as a security parameter. For two bit strings [TeX:] $$x, y \in\{0,1\}^{\star}, x \| y$$ denotes the concatenation of x and y. We say that two distributions [TeX:] $$D_{1} \text { and } D_{2}$$ are computationally indistinguishable if there is no efficient poly-time adversary can distinguish [TeX:] $$D_{1} \text { from } D_{2}$$ except with negligible probability.

An order-revealing encryption scheme _{OREnc} consists of the following three algorithms (OREnc.Setup, OREnc.Encrypt, OREnc.Compare) defined over a well-ordered domain D and a range R.

OREnc.Setup [TeX:] $$\left(1^{\lambda}\right) \rightarrow \text { skey }$$ : For a security parameter ,this setup algorithm generates a secret key skey.

OREnc.Encrypt [TeX:] $$(m s g, s k e y) \rightarrow c t x$$ : For a secret key skey and a message [TeX:] $$m s g \in D,$$ this encryption algorithm computes a ciphertext [TeX:] $$c t x \in R.$$

OREnc.Compare [TeX:] $$\left(c t x_{1}, c t x_{2}\right) \rightarrow b$$ : On input two ciphertexts [TeX:] $$c t x_{1} \text { and } c t x_{2},$$ this comparison algorithm outputs a bit [TeX:] $$b \in\{0,1\} .\left(b=1 \text { means } m s g_{1}<m s g_{2}\right)$$

**Correctness.** For a fixed security parameter , a given _{OREnc} is correct if for [TeX:] $$\text {skey} \leftarrow \text { OREnc.Setup }\left(1^{\lambda}\right),$$ and any messages [TeX:] $$m s g_{1}, m s g_{2} \in D\left(m s g_{1}<m s g_{2}\right), \quad \text { OREnc. Compare }\left(c t x_{1}, c t x_{2}\right)=1$$ where [TeX:] $$c t x_{1} \leftarrow\text { OREnc.Encrypt }\left(m s g_{1}, s k e y\right) \text { and } c t x_{2} \leftarrow \text { OREnc.Encrypt }\left(m s g_{2}, s k e y\right).$$

An order-preserving encryption scheme _{OREnc} consists of the following two algorithms (OPEnc.Setup, OPEnc.Encrypt) defined over a well-ordered domain D and a range R.

OPEnc.Setup [TeX:] $$\left(1^{\lambda}\right) \rightarrow \text { skey }$$ : For a security parameter , this setup algorithm generates a secret key skey.

OPEnc.Encrypt [TeX:] $$(m s g, s k e y) \rightarrow c t x:$$ On input the secret key skey and a plaintext [TeX:] $$m s g \in D,$$ this encryption algorithm computes a ciphertext [TeX:] $$c t x \in R.$$

**Correctness.** For a fixed security parameter , a given _{OREnc} is correct if for [TeX:] $$\text {skey} \leftarrow \text { OPEnc.Setup }\left(1^{\lambda}\right),$$ and any messages [TeX:] $$m s g_{1}, m s g_{2} \in D\left(m s g_{1}<m s g_{2}\right), c t x_{1}<c t x_{2} \text { where } c t x_{1} \leftarrow \text { OPEnc.Encrypt }\left(m s g_{1}, s k e y\right)$$ and [TeX:] $$c t x_{2} \leftarrow \text { OPEnc. Encrypt }\left(m s g_{2}, \text { skey }\right).$$ Thus, OPEnc can be seen as a special case of OREnc where the comparison algorithm output 1 if [TeX:] $$c t x_{1}<c t x_{2}.$$

As described above, these two schemes don’t contain a decryption algorithm, but the following two options can be applied. Note that the secret key holder can generate a ciphertext ctx of any messages he choose, and he can also verify the output of OREnc.Compare [TeX:] $$\left(c t x, c t x^{\star}\right) \text { where } c t x^{\star}$$ is the target ciphertext. Thus, he can decrypt [TeX:] $$c t x^{*}$$ by performing the binary search. Another method which avoids the logarithmic scale binary search overhead is combining with a CPA-secure encryption scheme, i.e., inserting an encryption of the same message under this symmetric encryption scheme together. Note that this additional ciphertext doesn’t reveal any information about the underlying plaintext due to the CPA security.

In this section, we review a simulation-based security model [3] of OREnc that precisely quantifies what information of plaintexts is leaked as defining a leakage function. We denote an adversary and a simulator for some [TeX:] $$q=\operatorname{poly}(\lambda) \text { by } A d v=\left(A_{1}, \ldots, A_{q}\right) \text { and } \operatorname{sim}=\left(S_{0}, \ldots, S_{q}\right), \text { respectively. }$$ _{OREnc} = (OREnc.Setup, OREnc.Encrypt, OREnc.Compare) be an OREnc scheme, and Lkg(·) denotes a leakage function of _{OREnc}. For a security parameter , the experiment is defined as follow:

We say that _{OREnc} is a secure with Lkg(·) if for all poly-size adversaries Adv, there exists a simulator Sim such that the two distributions [TeX:] $$R E A L_{A}^{\Pi}(\lambda) \text { and } S I M_{S}^{\Pi}(\lambda)$$ are computationally indistinguishable. From the security notion, we also say that _{OREnc} is a ideally-secure if the leakage function Lkg(·) reveals only the relative order of the underlying plaintexts. Note that we can apply the same experiment to an OPEnc scheme since it can be seen as a special case of OREnc.

As described in Section 1, it is natural to obtain an OREnc scheme from a given OPEnc scheme since the comparison algorithm of the OREnc scheme can simply return 1 if [TeX:] $$c t x_{1}<c t x_{2}$$ ciphertexts of OPEnc. The authors [3] showed how to compose an OPEnc scheme with an OREnc scheme. Their main idea is to encrypt a message with the OPEnc scheme, then use this ciphertext as an input of the encryption algorithm of OREnc. They also showed that the security of the resulting OREnc scheme is at least as strong as the security of the underlying OPEnc scheme. However, there has been no generic construction of converting an OREnc scheme into an OPEnc scheme yet. Although some previous works including [3] suggested methods to convert their OREnc scheme into OPEnc schemes, this is not generic construction. In this section, we propose a generic construction of an OPEnc scheme from a given ORE scheme.

For a security parameter , a domain [TeX:] $$D=(1, \ldots, M), \text { a range } R=(1, \ldots, N),$$ and an encrypted database EDB, we define our construction of an OPEnc scheme based on an OREnc scheme as follows (note that OPEnc.Setup [TeX:] $$\left(1^{\lambda}\right)$$ is identically defined as OREnc.Setup [TeX:] $$\left(1^{\lambda}\right)$$ \left(1^{\lambda}\right).

The encryption of our construction consists of two parts [TeX:] $$c t x_{0} \text { and } c t x_{1}$$ ciphertexts of OPEnc and OREnc, respectively. Basically, the encoding and updating methods of [TeX:] $$c t x_{0}$$ can be seen as the non-frequency hiding construction of [1], and it has been known to be ideally-secure. Due to the order-preserving property of [TeX:] $$c t x_{0},$$ the resulting ciphertext [TeX:] $$c t x_{0} \| c t x_{1}$$ also preserves the relative order of the underlying plaintext. More specifically, to encrypt a given message msg, a client who has a secret key generates an encryption [TeX:] $$c t x_{1}$$ of an underlying OREnc scheme, then sends it to a server. Using OREnc.Compare and [TeX:] $$c t x_{1},$$ the server can find the largest [TeX:] $$c t x_{x, 0}$$ and the smallest [TeX:] $$c t x_{y, 0}$$ as describe in Step 2. Here, [TeX:] $$\left(c t x_{x, 0}+1, \ldots, c t x_{y, 0}-\right.1)$$ means the range in which the [TeX:] $$c t x_{0}$$ can be exist. [TeX:] $$c t x_{0}$$ is simply computed as the intermediate value between [TeX:] $$c t x_{x, 0} \text { and } c t x_{y, 0}.$$ Note that if ciphertext space does not exist, i.e., [TeX:] $$c t x_{y, 0}-c t x_{x, 0}=1,$$ the server should perform the above update algorithm (Algorithm 2) to reconstruct [TeX:] $$c t x_{0}^{\prime} \mathrm{s}$$ in EDB.

In this section, we analyze our construction in terms of correctness and security.

**THEOREM 1.** (Correctness) Our proposed OPEnc scheme is correct if the underlying OREnc scheme is correct.

**Proof.** It is sufficient to show that the underlying OREnc is not correct if the resulting OPEnc scheme is not correct. We assume that there exist [TeX:] $$c t x_{a} \text { and } c t x_{b}\left(c t x_{a}>c t x_{b}\right)$$ encryptions of [TeX:] $$m s g_{a} \text { and } m s g_{b}\left(m s g_{a}<\right.\left.m s g_{b}\right).$$ Without loss of generality, we also assume that [TeX:] $$m s g_{a}$$ is encrypted as [TeX:] $$c t x_{a}=\left(c t x_{a, 0}, c t x_{a, 1}\right)$$ first. We know that [TeX:] $$c t x_{a}>c t x_{b} \text { implies } c t x_{a, 0}>c t x_{b, 0}.$$ When [TeX:] $$c t x_{b, 0}$$ is generated during the OPEnc.Encrypt algorithm where [TeX:] $$c t x_{b}=\left(c t x_{b, 0}, c t x_{b, 1}\right),$$ the part of determining the relative order of [TeX:] $$c t x_{b, 0}$$ is only the OREnc.Compare algorithm in Step 2. As a result, it implies that the underlying OREnc scheme is not correct.

**THEOREM 2.** (Security) Our proposed OPEnc scheme is secure with leakage function Lkg(·) of the underlying OREnc scheme.

**Proof.** We write [TeX:] $$L_{\mathrm{OPEnc}}(\cdot) \text { and } L_{\mathrm{ORFnc}}(\cdot)$$ to the leakage functions of our proposed OPEnc scheme and the underlying OREnc scheme, respectively. As described before, the generation and updating methods of [TeX:] $$c t x_{0}$$ can be seen as the non-frequency hiding construction of [1], and it has been known to be ideally secure. This means that the first part of the resulting ciphertext [TeX:] $$c_{0}$$ reveals only the relative ordering of the underlying plaintext. Therefore, a simulator Sim with [TeX:] $$L_{\mathrm{ORFnc}}(\cdot)$$ who can simulates [TeX:] $$c t x_{1}$$ is always able to simulate [TeX:] $$c t x_{0}$$ unless the underlying OREnc scheme provides more strong security than the ideal security.

**THEOREM 3.** (Efficiency) Our proposed OPEnc scheme provides a non-interactive encryption and a range query with a constant client-side storage.

**Proof.** From the specification of Algorithm 1, we know that it doesn’t require any additional rounds to encrypt data with a server. The client simply creates [TeX:] $$c t x_{1},$$ then sends it to the server. The rest of the encryption part is done by the server. Although we have not described in detail how the range query works, it is basically done by sending two encrypted boundary points to the server. It means that range query also does not require any additional rounds.

The client should maintain the secret key skey of the OREnc scheme to generate [TeX:] $$c t x_{1}.$$ Since the computation of [TeX:] $$c t x 0,$$ which requires all of the existing ciphertext information, is performed on the serverside, the client does not need to maintain any additional state except skey.

**REMARKS 1.** One of the interesting points of our proposed scheme is that the client and the server each compute half of the ciphertext. Some sensitive readers might think that it is not natural that the server who does not have a secret key generates the final ciphertext. However, this has no effect on functionalities of OPEnc such as decryption and range queries, and also no effect on the security since the part of ciphertext generated by the server is computed using only the information that has been already disclosed.

**REMARKS 2.** The ciphertext of our proposed OPEnc scheme consists of two ciphertexts of OPEnc and OREnc. This means that each OPEnc and OREnc encryption algorithms have to be performed to generate the ciphertext, thus it can be think that it requires roughly more than twice computational overhead compared to previous works. However, we know that the client generates only half of the ciphertext, and the server who has powerful computation power completes the encryption process, thus it is hard to say that efficiency of our proposed scheme is worse than the existing OPEnc schemes.

In this work, we proposed a new construction of an OPEnc scheme based on an OREnc scheme with the optimal client storage and round complexities. The security of the resulting OPEnc scheme is at least as strong as the underlying OREnc’s security. We also gave comparison result our construction with the existing ideally-secure OPEnc schemes in terms of efficiency and security. Finally, from our construction, we showed that it’s theoretically possible to construct a non-interactive ideally-secure OPEnc scheme with a constant client-side storage.

He received M.S. and Ph.D. degrees in Graduate School of Information Security from Korea University, Seoul, Korea, in 2011 and 2015, respectively. He is currently an assistant professor at School of Information Technology Engineering, Daegu Catholic University, Korea. His research interests focus on cryptography, database security, privacy enhancing technology, and secure protocols.

- 1 F. Kerschbaum, "Frequency-hiding order-preserving encryption," in
*Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security*, Denver, CO, 2015;pp. 656-667. custom:[[[-]]] - 2 D. S. Roche, D. Apon, S. G. Choi, A. Yerukhimovich, "POPE: partial order preserving encoding," in
*Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security*, Vienna, Austria, 2016;pp. 1131-1142. custom:[[[-]]] - 3 N. Chenette, K. Lewi, S. A. Weis, D. J. Wu, "Practical order-revealing encryption with limited leakage,"
*in Fast Software Encryption. Heidelberg: Springer*, pp. 474-493, 2016.doi:[[[10.1007/978-3-662-52993-5_24]]] - 4 K. Lewi, D. J. Wu, "Order-revealing encryption: New constructions, applications, and lower bounds," in
*Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security*, Vienna, Austria, 2016;pp. 1167-1178. custom:[[[-]]] - 5 D. Boneh, K. Lewi, M. Raykova, A. Sahai, M. Zhandry, J. Zimmerman, "Semantically secure order-revealing encryption: multi-input functional encryption without obfuscation,"
*in Advances in Cryptology – EUROCRYPT 2015. Heidelberg: Springer*, pp. 563-594, 2015.doi:[[[10.1007/978-3-662-46803-6_19]]] - 6 E. Miles, A. Sahai, M. Zhandry, "Annihilation attacks for multilinear maps: cryptanalysis of indistinguishability obfuscation over GGH13,"
*in Advances in Cryptology – CRYPT 2016. Heidelberg: Springer*, pp. 629-658, 2016.doi:[[[10.1007/978-3-662-53008-5_22]]] - 7 J. H. Cheon, K. Han, C. Lee, H. Ryu, D. Stehle, "Cryptanalysis of the CLT13 multilinear map,"
*Journal of Cryptology*, vol. 32, no. 2, pp. 547-565, 2019.doi:[[[10.1007/s00145-018-9307-y]]]