# Secure Database Using Order-Preserving Encryption Scheme Based on Arithmetic Coding and Noise Function

Sergey Krendelev, Mikhail Yakovlev, Maria Usoltseva

► To cite this version:

Sergey Krendelev, Mikhail Yakovlev, Maria Usoltseva. Secure Database Using Order-Preserving Encryption Scheme Based on Arithmetic Coding and Noise Function. 3rd International Conference on Information and Communication Technology-EurAsia (ICT-EURASIA) and 9th International Conference on Research and Practical Issues of Enterprise Information Systems (CONFENIS), Oct 2015, Daejon, South Korea. pp.193-202, 10.1007/978-3-319-24315-3_19. hal-01466219

HAL Id: hal-01466219

https://inria.hal.science/hal-01466219

Submitted on 13 Feb 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Secure database using order-preserving encryption
scheme based on arithmetic coding and noise function

Sergey Krendelev¹, Mikhail Yakovlev¹, Maria Usoltseva¹

¹ Novosibirsk State University, Pirogova str. 2, 630090 Novosibirsk, Russia
{s.f.krendelev, m.o.yakovlev, m.a.usoltseva}@gmail.com

**Abstract.** Order-preserving symmetric encryption (OPE) is a deterministic encryption scheme which encryption function preserves numerical order of the plaintexts. That allows comparison operations to be directly applied on encrypted data in case, for example, decryption takes too much time or cryptographic key is unknown. That's why it is successfully used in cloud databases as effective range queries can be performed based on. This paper presents order-preserving encryption scheme based on arithmetic coding. In the first part of it we review principles of arithmetic coding, which formed the basis of the algorithm, as well as changes that were made. Then we describe noise function approach, which makes algorithm cryptographically stronger and show modifications that can be made to obtain order-preserving hash function. Finally we analyze resulting vulnerability to chosen-plaintext attack.

**Keywords:** Cloud computing security, order-preserving encryption, symmetric-key cryptosystems, order-preserving hash functions

# 1 Introduction

Nowadays, the amount of information stored in various databases steadily increases. In order to store and effectively manage large amounts of data it is needed to increase data storages capacity and allocate funds for its administration. Another way that was chosen by many companies is to give the database management to a third-party. Such service is managed by a cloud operator and is called Database as a Service, DBaaS.

Obviously, this approach has its own flaws. And the most important of them is security issue. Data can be stolen by the service provider itself or by someone else from its storage. Fortunately, this problem can be solved by encryption. Of course if we just encrypt the whole database with a conventional encryption algorithm, we'll have to encrypt and decrypt it each time we need something. So, all advantages will be lost. That's why special encryption schemes, such as homomorphic encryption and order-preserving encryption, are developed. The first one allows us to handle encrypted data, and the second – to sort them and select the desired.

All known order-preserving schemes have significant problems, such as low level of security (polynomial monotonic functions [1], spline approximation [2], linear functions with random noise [3]), low performance (summation of random numbers
[4], B-trees [5]) or too-large numbers proceeding (scheme by Boldyreva [6]). Proposed scheme doesn't have these disadvantages and, furthermore, unlike all the others can be used to encrypt real numbers. Also it can be used to obtain order-preserving hash function.

This algorithm combines two main ideas, which the majority of OPE schemes operate with: monotonic functions design and elements of coding theory (implicit monotonic functions design). It is claimed that scheme is based on arithmetic coding and noise function, but, in fact, this article considers only the case with binary alphabet. In theory, nothing prevents the use of an arbitrary one.

First, let's give a definition of order-preserving encryption. Assume there are two sets A and B with order relation <. Function f: A → B is strictly increasing if ∀x, y ∈ A, x < y ⇔ f(x) < f(y) . Order-preserving encryption is deterministic symmetric encryption based on strictly increasing function.

The described order-preserving encryption scheme was developed in Laboratory of Modern Computer Technologies of Novosibirsk State University Research Department as a part of “Protected Database” project<fnref n="1" /> and is based on arithmetic coding and noise function. Let us consider them precisely.

## 2 Splitting procedure of arithmetic coding

Suppose c is non-negative integer number requiring for its representation n bits, i.e.

$$c = \sum_{i=1}^{n} \alpha_{i} 2^{i}$$

where ($\alpha_1, \alpha_2, ..., \alpha_n$) is a bit string, $\alpha_1$ is the MSB. Let us define the bijection f. Assume that the string ($\alpha_1, \alpha_2, ..., \alpha_n$) defines certain real number s ∈ [0, 1) as follows:

$$s = \frac{c}{2^n}$$

Let us find another representation for the number s. In order to do it, we use the idea of arithmetic coding. Notice that the number s satisfies the equation $2^n s = c$. The equation

$$G(x) = 2^n x - c = 0$$

has only one solution on the interval [0, 1). If we solve this equation using a standard binary search, we get the initial number s after n steps. The main idea of arithmetic coding is that intervals can be split into parts randomly. In this case approximate solution of the equation can be found after the less number of steps. That allows us to

<footnote n="1">¹ This research is performed in Novosibirsk State University under support of Ministry of Education and Science of Russia (contract no. 02.G25.31.0054).</footnote>
Thus, the adversary can get $(a_0, ..., a_n)$ and correspondingly encryption function $f(x)$.

In order to complicate his task it is necessary to maximize the amount of pairs required for this attack and complexity of the system of equations $f(x_i) = y_i$. Therefore, it was decided to generate noise function from class of function

$$f(x) = \int_{c}^{x} (a_{0} + a_{1}t + a_{2}t^{2})(a_{3} + a_{4}\sin(a_{5} + a_{6}t) + a_{7}\cos(a_{8} + a_{9}t)) dt,$$

where c is an arbitrary constant and coefficients $a_i$ are selected so that

$$(a_0 + a_1 t + a_2 t^2)(a_3 + a_4 \sin(a_5 + a_6 t) + a_7 \cos(a_8 + a_9 t)) > 0$$

for $\forall t \in (c; x_{max})$. In this case $f(x)$ is strictly increasing function (see Fig. 1). This integral can be calculated explicitly, which increases the speed of function value calculation.

<figure><img src="image_2.png" /><figcaption>Fig. 1. Example of the correct noise function from the class. Due to such combination of sine and cosine, its behavior is hard to predict without $(a_0, ..., a_9)$ coefficients knowledge.</figcaption></figure>

Nevertheless, the system of equations

$$\left\{
\begin{array}{l}
\displaystyle\int_{c}^{x_0} (a_0 + a_1 t + a_2 t^2)(a_3 + a_4 \sin(a_5 + a_6 t) + a_7 \cos(a_8 + a_9 t)) dt \\
\\
\displaystyle\int_{c}^{x_1} (a_0 + a_1 t + a_2 t^2)(a_3 + a_4 \sin(a_5 + a_6 t) + a_7 \cos(a_8 + a_9 t)) dt \\
\\
\vdots \\
\\
\displaystyle\int_{c}^{x_k} (a_0 + a_1 t + a_2 t^2)(a_3 + a_4 \sin(a_5 + a_6 t) + a_7 \cos(a_8 + a_9 t)) dt
\end{array}
\right.
= y_0 \\
= y_1 \\
\vdots \\
= y_k
$$
is difficult to solve, which indicates that proposed algorithm is cryptographically
strong against this type of attack.

# 4 Cryptographic scheme

## 4.1 Key generation

As a private key of encryption algorithm we consider noise function $f(x) = \int_c^x (a_0 + a_1 t + a_2 t^2)(a_3 + a_4 \sin(a_5 + a_6 t) + a_7 \cos(a_8 + a_9 t)) dt$ and a set of ratios $(p_i, q_i)$.

In order for an encrypted n-bit number to be uniquely decrypted, the length of
intervals computed during decryption has to be less than $\frac{1}{2^n}$. The largest length of the
interval that can be obtained during decryption is $\prod_i \frac{\max(p_i, q_i)}{p_i+q_i} f'_{\max}(x)$. So the
algorithm of calculation the set of ratios is:

1. Generate random ratios $p_i, q_i$.

2. Check the condition

$$ \prod_i \frac{\max(p_i, q_i)}{p_i + q_i} f'_{\max}(x) < \frac{1}{2^n} $$

If this condition is satisfied, go to the step 3, else go back to the step 1.

3. Output the set of ratios $(p_1, q_1), (p_2, q_2), \dots, (p_k, q_k)$.

The key is the set $K = [(a_0, \dots, a_9), (p_1, q_1), (p_2, q_2), \dots, (p_k, q_k)]$.

## 4.2 Encryption

Assume we need to encrypt n-bit integer $s$ with the key $K = [f(x), (p_1, q_1), (p_2, q_2), \dots, (p_k, q_k)]$, where $f(x)$ is a noise function, $f(a_0) = 0$, $f(b_0) = 2^n$, and $(p_i, q_i)$ is a set of ratios. Consider the i-th iteration of algorithm.

The current interval $[a_{i-1}, b_{i-1})$ is split in the ratio $p_i:q_i$. Let it be split at the point $x \in [a_{i-1}, b_{i-1})$, i.e.

$$ x = a_{i-1} + \frac{(b_{i-1} - a_{i-1})p_i}{p_i + q_i} $$

If $f(x) > s$, then $\beta_i = 0$, $a_i = a_{i-1}$, $b_i = x$. Otherwise, $\beta_i = 1$, $a_i = x$, $b_i = b_{i-1}$.

Notice that $\forall i, f^{-1}(s) \in [a_i, b_i)$ according to the selection of $a_i$ and $b_i$. After performing k iterations, (where k is the size of the key, i.e. the number of ratios) we obtain the bit sequence $\beta = (\beta_1, \dots, \beta_k), \beta_i \in \{0,1\}$, which is a ciphertext for s.
## 4.3 Decryption

Suppose there is a bit sequence $\beta = (\beta_1, ..., \beta_k)$, $\beta_i \in \{0,1\}$, which is the ciphertext for s, encrypted with some key K. Let us consider the i-th iteration of the algorithm.

Similar to the encryption algorithm, current interval $[a_{i-1}, b_{i-1})$ is split in the ratio $p_i: q_i$. Let it be split at the point $x \in [a_{i-1}, b_{i-1})$, i.e.

$$x = a_{i-1} + \frac{(b_{i-1} - a_{i-1})p_i}{p_i + q_i}.$$

If $\beta_i = 0$, then $a_i = a_{i-1}$, $b_i = x$. Otherwise, $a_i = x$, $b_i = b_{i-1}$.

After performing k iterations, we obtain the interval $[a_k, b_k)$ and the condition $(f(b_k) - f(a_k)) < \frac{1}{2^n}$ is satisfied according to the key selection. As $s \in [f(a_k), f(b_k))$, the s is uniquely decoded as follows:

$$s = [2^n f(a_k)] + 1,$$

where $[x]$ is the largest integer, which comes before x.

# 5 Scheme modifications

## 5.1 Application of the scheme for fixed-point arithmetic

It is easy to see that this scheme can be generalized to the set of rational numbers. Encryption and decryption algorithms are the same except for the final operation – the length of the segment $[a_k, b_k)$ that determines encrypted number is reduced to $2^l$ times, where l is the number of bit decimal places. It should be known at the stage of key generation and condition from point 2 takes the following form:

$$\prod_{i} \frac{\max_{i}[(p_i, q_i)]}{p_i + q_i} * f'_{\max}(x) < \frac{1}{2^{n+1}}$$

After key generation number l can't be modified and is a part of the key. So, the secret key K now is the set $[l, (a_0, ..., a_9), (p_1, q_1), (p_2, q_2), ..., (p_k, q_k)]$.

## 5.2 Strictly increasing hash function

This algorithm can also be modified to produce a strictly increasing hash function. It can be used, for example, in encrypted database, if it stores two entities for each data: ciphertext, that was obtained from cryptographically strong algorithm and hash value returned by hash function. This allows both to be sure that the data won't be decrypted by adversary (first entity is secure and the second can't be decrypted at all) and apply comparison operations on encrypted data to some extent.
To begin, we note that output has the same bit size as the number of ratios $p_i, q_i$ from the secret key. So, in order to obtain a hash function, it is enough to change the procedure of key generation, and more precisely, its ratios generation part.

Instead of the condition checking from the point 2, satisfaction of which guaranteed that the data can be decrypted, now we need to perform the first point – pair $p_i, q_i$ generation – a number of times. This number, evidently, is equal to the number of bits that hash function returns.

Thus, the key generation algorithm for order-preserving m-bit hash function is:

1. Select strictly increasing noise function $f(x)$. To do this, generate $(a_0, ..., a_9)$ so that

$$ (a_0 + a_1 t + a_2 t^2)(a_3 + a_4 \sin(a_5 + a_6 t) + a_7 \cos(a_8 + a_9 t)) > 0 $$

for $\forall t \in (c; x_{max})$, where c is a fixed constant.

2. Generate random set of ratios $(p_1, q_1), (p_2, q_2), ..., (p_m, q_m)$.

3. The key is the set $K = [(a_0, ..., a_9), (p_1, q_1), (p_2, q_2), ..., (p_m, q_m)]$.

To get rid of the big numbers processing, for instance, if we need to get hash of a large file, it is possible to split input data into parts with acceptable size and calculate hash for each of them. The result hash value of the whole file can be found as their concatenation. This approach allows us to hash data of any predetermined dimension.

So, there are three parameters that we can select arbitrarily depending on our purpose: $s_1$ – size of the processed parts, $s_2$ – hash size for each of them ($s_2 < s_1$), and $s_3$ – maximum file size. Obviously, final hash is $\frac{s_2s_3}{s_1}$-bit.

Since encryption algorithm remains the same, the hash function running time depends linearly on its output size (it is equal to the number of algorithm iterations). Therefore, it is not recommended to choose too-big $s_2$ number.

In order to process files smaller than the maximum size, they can be padded with zeros on the left. In this case, order is still preserves. Since this is a hash function algorithm, decryption is no longer exists.

# 6 Encryption security

As we have seen (see Section 3) OPE schemes cannot satisfy the standard notions of security against chosen-plaintext attack. Different methods of cryptoanalysis are considered to determine the notion of order-preserving encryption security [2],[8],[9],[10]. Generally, the security of such schemes is based on the fact that monotonic function, the scheme is based on, must be completely indistinguishable from truly random monotonic function. This means that only an access to the private key allows performing accurate data decryption.

So let us check this algorithm for this condition in practice. To do that, we encrypted all 16-bit numbers (from 0 to 65535) with the same random key and analyzed the results.
As a subject of analysis we chose the difference between two ciphertexts for
nearby integers. For example, if $f(x) = 2186003864819$ and $f(x + 1) =
2186004033407$, where $f(x)$ is encryption function, then $f(x + 1) - f(x) =
168588$ is considered. One of the reasons for this choice was the fact that success of
chosen- plaintext attack by interpolation depends on this differrences (see Fig. 2).

<figure><img src="image_3.png" /><figcaption>**Fig. 2.** Chosen-plaintext attack using values interpolation. Ciphertext for some $b_1$-bit plaintext $x$ is approximated by the value of $\frac{x}{2^{b_2}}$, where $b_2$ is size of ciphertext. Approximation in the other direction is counted similarly.</figcaption></figure>

As a result, we obtained the following data (see Fig. 3). In this chart the Y-axis
displays the difference value between two ciphertexts (higher values were rounded),
and the X-axis shows the number of them was found.
<figure><img src="image_4.png" /><figcaption>**Fig. 3.** Frequency distribution of the differences between ciphertext.</figcaption></figure>

As we see, this chart and right hyperbola $y = \frac{1}{x}$ are alike. It is typical for monotonic functions that were generated randomly and indicates that the maximum available security of the algorithm was achieved.

But the distribution of the differences itself is also important (see Fig. 4). The Y-axis displays f(x + 1) - f(x) when the X-axis shows x (from 0 to 65535).

<figure><img src="image_5.png" /><figcaption>**Fig. 4.** Distribution of the differences on the interval.</figcaption></figure>

We can see that the differences are distributed very irregularly. As it is a feature of secure encryption, we can claim that proposed algorithm is cryptographically strong.
References

1. Gultekin Ozsoyoglu, David A. Singer, Sun S. Chung "Anti-Tamper Databases: Querying Encrypted Databases." EECS Department, Math Department, Case Western Reserve University, Cleveland, OH 44106, DOI=http://dx.doi.org/10.1109/ICDEW.2006.30

2. Rakesh Agrawal, Gerald George Kiernan, Srikant Ramakrishnan, Yirong Xu, System and method for order-preserving encryption for numeric data.

3. Commutative order-preserving encryption, Kerschbaum, Florian - Karlsruhe, United States Patent 20120121080, DE, May 17, 2012.

4. G. Bebek. Anti-tamper database research: Inference control techniques, Technical Report EECS433 Final Report, Case Western Reserve University, 2002.

5. An Ideal-Security Protocol for Order-Preserving Encoding, Raluca Ada Popa, Frank H. Li, Nickolai Zeldovich, MIT CSAIL, 2011, DOI= http://dx.doi.org/10.1109/CISS.2012.6310814

6. Boldyreva, A. Order preserving symmetric encryption, In Proceedings of the 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), Cologne, Germany, April 2009.

7. Bruce, Shnayder B.A. Applied Cryptology. Moscow.: "Triumph", 2002. - 816 pp.

8. Alexandra Boldyreva, Nathan Chenette, and Adam O'Neill. Order-preserving encryption revisited: Improved security analysis and alternative solutions. In Proceedings of the 31st International Conference on Advances in Cryptology, CRYPTO, 2011.

9. Santi Martinez, Josep M. Miret, Rosana Tomas and Magda Valls, "Security Analysis of Order Preserving Symmetric Cryptography", Applied Mathematics & Information Sciences, Vol. 7, No. 4, 1285-1295, 2013.

10. L. Xiao, O. Bastani, I. Yen, "Security Analysis for Order Preserving Encryption Schemes", Tech Report UTDCS-01-12, 2012, URL: https://utd.edu/~ilyen/techrep/OPE-proof1.pdf