New Construction of Order-Preserving Encryption Based on Order-Revealing Encryption

1. Introduction

One of promising solutions to protect the confidentiality of sensitive data is to use property-preserving encryption schemes which preserve some property of plaintexts, then perform query evaluation over the encrypted database (EDB). Supporting efficient operations on EDB such as sorting and range queries, order-preserving encryption (OPEnc) [1,2] and order-revealing encryption (OREnc) [3-5] have been proposed.

OREnc is a special type of symmetric encryptions which leaks the order of the underlying plaintexts through a publicly computable comparison function. Recently, Boneh et al. [5] proposed the first stateless and non-interactive OREnc scheme which achieves the ideal security. However, their OREnc scheme relies on multilinear maps requiring heavy computation and strong assumption, also suffering from security analysis [6,7], thus is not efficiently implementable today. Chenette et al. [3] proposed the first efficiently-implementable OREnc scheme based on a pseudo-random function. They also provided a new security model that precisely quantifies what information of plaintexts is leaked. Later, Lewi and Wu [4] proposed a new OREnc scheme with reduced leakage as compared to [3].

OPEnc is a special case of OREnc whose ciphertexts have the same order as their plaintexts, thus it enables a server to get the same results as if it had operated on plaintexts without any modification on DBMS. It has been known that any immutable ideally-secure OPEnc schemes must have the exponentially large ciphertext space. Recently, some interactive and mutable order-preserving encryption (or encoding) schemes with the ideal security have been proposed. Kerschbaum [1] proposed the first frequency-hiding OPEnc scheme that randomizes the ciphertexts to hide the frequency of the underlying plaintexts. Recently, Roche et al. [2] gave a partial order-preserving encryption (POPEnc) scheme that is mainly for the application scenarios where a large number of insertions and a moderate number of range queries, and achieves even stronger security compare to [1]. However, these ideally-secure OPEnc schemes either suffer from a large round and client-side storage complexities or incomplete functionalities, as described in Table 1.

In this work, we propose a possible answer to the following question: Is it possible to design a noninteractive ideally-secure OPEnc with a constant-size client storage?

More specifically, we present how to improve the round and client-side storage complexities on the exiting ideally-secure mutable order-preserving encryption protocol using the public comparison functionality of an OREnc scheme. By composing our method with an existing OREnc scheme, we can obtain an efficient OPEnc scheme which security is at least as strong as one of the underlying OREnc scheme. Table 1 presents comparison our constructions based on [3-5] with the existing ideally-secure OPEnc schemes in terms of efficiency and security. Composing with [3,4], the resulting constructions show better efficiency both of the number of rounds and the client-side storage, but cannot guarantee the ideal security. Note that the construction based on [5] is the first non-interactive ideally-secure OPEnc scheme with a constant-size client storage, but it is currently impractical to implement as described before.

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.

2. Preliminaries

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.

2.1 Formal Notion of Order-Revealing Encryption

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).$$

2.2 Formal Notion of Order-Preserving Encryption

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.

2.3 Security of OR(P)Enc

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.

3. Proposed Scheme

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.

4. Analysis

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.

5. Conclusions

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.

Acknowledgement

This work was supported by research grants from Daegu Catholic University in 2019.