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

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.

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 ${\text{f}}: {\text{A}} \to {\text{B}}$ is strictly increasing if $\forall {\text{x}},{\text{y}} \in {\text{A}}, {\text{x}} < y \Leftrightarrow f\left( {\text{x}} \right) < f\left( {\text{y}} \right)$. 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¹ and is based on arithmetic coding and noise function. Let us consider them precisely.

2 Splitting Procedure of Arithmetic Coding

Suppose ${\text{c}}$ is non-negative integer number requiring for its representation ${\text{n}}$ bits, i.e.

$$ {\text{c}} = \mathop \sum \limits_{{{\text{i}} = 1}}^{\text{n}}\upalpha_{\text{i}} 2^{\text{i}} $$

where $\left( {\upalpha_{1},\upalpha_{2}, \ldots ,\upalpha_{\text{n}} } \right)$ is a bit string, $\upalpha_{1}$ is the MSB. Let us define the bijection ${\text{f}}$. Assume that the string $\left( {\upalpha_{1} ,\upalpha_{2} , \ldots ,\upalpha_{\text{n}} } \right)$ defines certain real number ${\text{s}} \in \left[ {\left. {0, 1} \right)} \right.$ as follows:

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

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

$$ {\text{G}}\left( {\text{x}} \right) = 2^{\text{n}} {\text{x}} - {\text{c}} = 0 $$

has only one solution on the interval $\left[ {\left. {0, 1} \right)} \right.$. 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 achieve compression of data while using arithmetic coding. First of all, let us consider the splitting procedure.

Suppose $\upgamma = \frac{\text{p}}{{{\text{p}} + {\text{q}}}},\upmu = \frac{\text{q}}{{{\text{p}} + {\text{q}}}}$, where ${\text{p}},{\text{q}}$ are random natural numbers. Obviously, $\upgamma +\upmu = 1$. Let us split the interval $\left[ {\left. {0, 1} \right)} \right.$ into two parts $\left[ {\left. {0, \frac{\text{p}}{{{\text{p}} + {\text{q}}}}} \right)} \right.,\left[ {\left. {\frac{\text{p}}{{{\text{p}} + {\text{q}}}}, 1} \right)} \right.$. If ${\text{G}}\left( {\frac{\text{p}}{{{\text{p}} + {\text{q}}}}} \right) > 0$, the interval $\left[ {\left. {0, \frac{\text{p}}{{{\text{p}} + {\text{q}}}}} \right)} \right.$ is selected, and the output is 0-bit ($\upbeta_{1} = 0$). If ${\text{G}}\left( {\frac{\text{p}}{{{\text{p}} + {\text{q}}}}} \right) < 0$, the interval $\left[ {\left. {\frac{\text{p}}{{{\text{p}} + {\text{q}}}}, 1} \right)} \right.$ is selected, and $\upbeta_{1} = 1$. Let us denote $\left[ {\left. {{\text{a}}_{1} ,{\text{b}}_{1} } \right)} \right.$ the interval was selected.

This interval is again split into parts in the ratio $\upgamma:\upmu$. According to the sign of function ${\text{G}}({\text{x}})$ in the splitting point, one of the segments is selected. Proceeding by induction, the interval $\left[ {\left. {{\text{a}}_{\text{k}} ,{\text{b}}_{\text{k}} } \right)} \right.$ can be calculated for $\forall {\text{k}}$. Its length is $\upgamma^{\text{r}}\upmu^{{{\text{n}} - {\text{r}}}}$, where ${\text{r}}$ is the number of zeros in string $\upbeta$. If $\forall {\text{r}}: \frac{1}{{2^{\text{n}} }} <\upgamma^{\text{r}}\upmu^{{{\text{k}} - {\text{r}}}}$, then ${\text{s}} \in \left[ {\left. {{\text{a}}_{\text{k}} ,{\text{b}}_{\text{k}} } \right)} \right.$ and ${\text{c}} = 2^{\text{n}} {\text{s}}$ are uniquely defined by $\upbeta = (\upbeta_{1} , \ldots ,\upbeta_{\text{k}} )$. It is also obvious that this mapping preserves an order.

Generalizing used in the adaptive arithmetic coding, as well as in the proposed algorithm, is that it is possible to use different ratio on each step. This allows us to achieve stronger security of encryption.

3 Noise Function

It is known that the composition of two strictly increasing functions strictly increases. Therefore, to provide stronger security of cryptographic algorithm special random strictly increasing function is used in addition to the splitting procedure. In fact, we use inverse function of the one that was generated.

It was proved [6] that OPE schemes cannot satisfy the standard notions of security, such as indistinguishability against chosen-plaintext attack (IND-CPA) [7], since they leak the ordering information of the plaintexts. If an adversary knows plaintexts ${\text{p}}_{1} , {\text{p}}_{2}$ and corresponding ciphertexts ${\text{c}}_{1} , {\text{c}}_{2}$ and ${\text{c}}$, such that ${\text{c}}_{1} < c < {\text{c}}_{2}$, it is obvious that the plaintext for ${\text{c}}$ lies in the interval $({\text{p}}_{1} , {\text{p}}_{2} )$. In addition, the adversary can always find the decryption function in some approximation, for instance, using linear interpolation.

And moreover, in case of using, for example, encryption method developed by David A. Singer and Sun S. Chung [1], where strictly increasing polynomial functions ${\text{f}}\left( {\text{x}} \right) = {\text{a}}_{0} + {\text{a}}_{1} {\text{x}} + \ldots + {\text{a}}_{\text{n}} {\text{x}}^{\text{n}}$ are used for encryption, the adversary can calculate the exact encryption function if he has $({\text{n}} + 1)$ arbitrary pairs (plaintext, ciphertext). It is enough to solve the system of equations:

$$ \left\{ {\begin{array}{*{20}c} {{\text{a}}_{0} + {\text{a}}_{1} {\text{x}}_{0} + \ldots + {\text{a}}_{\text{n}} {\text{x}}_{0}^{\text{n}} = {\text{y}}_{0} } \\ {{\text{a}}_{0} + {\text{a}}_{1} {\text{x}}_{1} + \ldots + {\text{a}}_{\text{n}} {\text{x}}_{1}^{\text{n}} = {\text{y}}_{1} } \\ \vdots \\ {{\text{a}}_{0} + {\text{a}}_{1} {\text{x}}_{\text{n}} + \ldots + {\text{a}}_{\text{n}} {\text{x}}_{\text{n}}^{\text{n}} = {\text{y}}_{\text{n}} } \\ \end{array} } \right. $$

Thus, the adversary can get $\left( {{\text{a}}_{0} , \ldots {\text{a}}_{\text{n}} } \right)$ and correspondingly encryption function ${\text{f}}({\text{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 ${\text{f}}\left( {{\text{x}}_{\text{i}} } \right) = {\text{y}}_{\text{i}}$. Therefore, it was decided to generate noise function from class of function

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

where ${\text{c}}$ is an arbitrary constant and coefficients ${\text{a}}_{\text{i}}$ are selected so that

$$ \left( {{\text{a}}_{0} + {\text{a}}_{1} {\text{t}} + {\text{a}}_{2} {\text{t}}^{2} } \right)({\text{a}}_{3} + {\text{a}}_{4} \sin \left( {{\text{a}}_{5} + {\text{a}}_{6} {\text{t}}} \right) + {\text{a}}_{7} \cos ({\text{a}}_{8} + {\text{a}}_{9} {\text{t}})) > 0 $$

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

$$ \left\{ {\begin{array}{*{20}c} {\int_{\text{c}}^{{\text{x}_{\text{0}} }} {\begin{array}{*{20}c} {\left( {{\text{a}}_{0} + {\text{a}}_{1} {\text{t}} + {\text{a}}_{2} {\text{t}}^{2} } \right)({\text{a}}_{3} + {\text{a}}_{4} \sin \left( {{\text{a}}_{5} + {\text{a}}_{6} {\text{t}}} \right) + } \\ {{\text{a}}_{7} \cos ({\text{a}}_{8} + {\text{a}}_{9} {\text{t}}))\,{\text{dt}}} \\ \end{array} = {\text{y}}_{0} } } \\ {\int_{\text{c}}^{{\text{x}_{\text{1}} }} {\begin{array}{*{20}c} {\left( {{\text{a}}_{0} + {\text{a}}_{1} {\text{t}} + {\text{a}}_{2} {\text{t}}^{2} } \right)({\text{a}}_{3} + {\text{a}}_{4} \sin \left( {{\text{a}}_{5} + {\text{a}}_{6} {\text{t}}} \right) + } \\ {{\text{a}}_{7} \cos ({\text{a}}_{8} + {\text{a}}_{9} {\text{t}}))\,{\text{dt}}} \\ \end{array} = {\text{y}}_{1} } } \\ \vdots \\ {\int_{\text{c}}^{{\text{x}_{\text{k}} }} {\begin{array}{*{20}c} {\left( {{\text{a}}_{0} + {\text{a}}_{1} {\text{t}} + {\text{a}}_{2} {\text{t}}^{2} } \right)({\text{a}}_{3} + {\text{a}}_{4} \sin \left( {{\text{a}}_{5} + {\text{a}}_{6} {\text{t}}} \right) + } \\ {{\text{a}}_{7} \cos ({\text{a}}_{8} + {\text{a}}_{9} {\text{t}}))\,{\text{dt}}} \\ \end{array} = {\text{y}}_{\text{k}} } } \\ \end{array} } \right. $$

is difficult to solve, which indicates that proposed algorithm is cryptographically strong against this type of attack.

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 $\left( {{\text{a}}_{0} , \ldots {\text{a}}_{9} } \right)$ coefficients knowledge.

4 Cryptographic Scheme

4.1 Key Generation

As a private key of encryption algorithm we consider noise function ${\text{f}}\left( {\text{x}} \right) = \int_{\text{c}}^{\text{x}} {\left( {{\text{a}}_{0} + {\text{a}}_{1} {\text{t}} + {\text{a}}_{2} {\text{t}}^{2} } \right)({\text{a}}_{3} + {\text{a}}_{4} \sin \left( {{\text{a}}_{5} + {\text{a}}_{6} {\text{t}}} \right) + {\text{a}}_{7} \cos ({\text{a}}_{8} + {\text{a}}_{9} {\text{t}})){\text{dt}}}$ and a set of ratios $\left( {{\text{p}}_{\text{i}} , {\text{q}}_{\text{i}} } \right)$.

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

• 1. Generate random ratios ${\text{p}}_{\text{i}} ,{\text{q}}_{\text{i}}$.

• 2. Check the condition

  $$ \mathop \prod \limits_{\text{i}} \frac{{{ \hbox{max} }\left( {{\text{p}}_{\text{i}} ,{\text{q}}_{\text{i}} } \right)}}{{{\text{p}}_{\text{i}} + {\text{q}}_{\text{i}} }}{\text{f}}_{ \hbox{max} }^{ '} \left( {\text{x}} \right) < \frac{1}{{2^{\text{n}} }} $$

  If this conditions if satisfied, go to the step 3, else go back to the step 1.

• 3. Output the set of ratios $\left( {{\text{p}}_{1} ,{\text{q}}_{1} } \right),\left( {{\text{p}}_{2} ,{\text{q}}_{2} } \right), \ldots ,\left( {{\text{p}}_{\text{k}} ,{\text{q}}_{\text{k}} } \right).$

  The key is the set ${\text{K}} = [\left( {{\text{a}}_{0} , \ldots ,{\text{a}}_{9} } \right),\left( {{\text{p}}_{1} ,{\text{q}}_{1} } \right),\left( {{\text{p}}_{2} ,{\text{q}}_{2} } \right), \ldots ,\left( {{\text{p}}_{\text{k}} ,{\text{q}}_{\text{k}} } \right)].$

4.2 Encryption

Assume we need to encrypt n-bit integer s with the key ${\text{K}} = [{\text{f}}({\text{x}}),\left( {{\text{p}}_{1} ,{\text{q}}_{1} } \right),\left( {{\text{p}}_{2} ,{\text{q}}_{2} } \right), \ldots ,\left( {{\text{p}}_{\text{k}} ,{\text{q}}_{\text{k}} } \right)]$, where ${\text{f}}({\text{x}})$ is a noise function, ${\text{f}}\left( {{\text{a}}_{0} } \right) = 0$, ${\text{f}}({\text{b}}_{0} ) = 2^{\text{n}}$, and $({\text{p}}_{\text{i}} ,{\text{q}}_{\text{i}} )$ is a set of ratios. Consider the ${\text{i}}$-th iteration of algorithm.

The current interval $\left[ {\left. {{\text{a}}_{{{\text{i}} - 1}} ,{\text{b}}_{{{\text{i}} - 1}} } \right)} \right.$ is split in the ratio ${\text{p}}_{\text{i}} :{\text{q}}_{\text{i}}$. Let it be split at the point ${\text{x}} \in \left[ {\left. {{\text{a}}_{{{\text{i}} - 1}} ,{\text{b}}_{{{\text{i}} - 1}} } \right)} \right.$, i.e.

$$ {\text{x}} = {\text{a}}_{{{\text{i}} - 1}} + \frac{{\left( {{\text{b}}_{{{\text{i}} - 1}} - {\text{a}}_{{{\text{i}} - 1}} } \right){\text{p}}_{\text{i}} }}{{{\text{p}}_{\text{i}} + {\text{q}}_{\text{i}} }}. $$

If ${\text{f}}({\text{x}}) > s$, then $\upbeta_{\text{i}} = 0$, ${\text{a}}_{\text{i}} = {\text{a}}_{{{\text{i}} - 1}} , {\text{b}}_{\text{i}} = {\text{x}}$. Otherwise, $\upbeta_{\text{i}} = 1, {\text{a}}_{\text{i}} = {\text{x}}, {\text{b}}_{\text{i}} = {\text{b}}_{{{\text{i}} - 1}}$.

Notice that $\forall {\text{i}},{\text{f}}^{ - 1} ({\text{s}}) \in \left[ {\left. {{\text{a}}_{\text{i}} ,{\text{b}}_{\text{i}} } \right)} \right.$ according to the selection of ${\text{a}}_{\text{i}}$ and ${\text{b}}_{\text{i}}$. After performing k iterations, (where k is the size of the key, i.e. the number of ratios) we obtain the bit sequence $\upbeta = \left( {\upbeta_{1} , \ldots ,\upbeta_{\text{k}} } \right),\upbeta_{\text{i}} \in \left\{ {0,1} \right\}$, which is a ciphertext for ${\text{s}}$.

4.3 Decryption

Suppose there is a bit sequence $\upbeta = \left( {\upbeta_{1} , \ldots ,\upbeta_{\text{k}} } \right),\upbeta_{\text{i}} \in \left\{ {0,1} \right\}$, which is the ciphertext for ${\text{s}}$, encrypted with some key ${\text{K}}$. Let us consider the i-th iteration of the algorithm.

Similar to the encryption algorithm, current interval $\left[ {\left. {{\text{a}}_{{{\text{i}} - 1}} ,{\text{b}}_{{{\text{i}} - 1}} } \right)} \right.$ is split in the ratio ${\text{p}}_{\text{i}} :{\text{q}}_{\text{i}}$. Let it be split at the point ${\text{x}} \in \left[ {\left. {{\text{a}}_{{{\text{i}} - 1}} ,{\text{b}}_{{{\text{i}} - 1}} } \right)} \right.$, i.e.

$$ {\text{x}} = {\text{a}}_{{{\text{i}} - 1}} + \frac{{\left( {{\text{b}}_{{{\text{i}} - 1}} - {\text{a}}_{{{\text{i}} - 1}} } \right){\text{p}}_{\text{i}} }}{{{\text{p}}_{\text{i}} + {\text{q}}_{\text{i}} }}. $$

If $\upbeta_{\text{i}} = 0$, then ${\text{a}}_{\text{i}} = {\text{a}}_{{{\text{i}} - 1}} , {\text{b}}_{\text{i}} = {\text{x}}$. Otherwise, ${\text{a}}_{\text{i}} = {\text{x}}$, ${\text{b}}_{\text{i}} = {\text{b}}_{{{\text{i}} - 1}}$.

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

$$ {\text{s}} = 2^{\text{n}} {\text{f}}({\text{a}}_{\text{k}} ) + 1, $$

where $\left\lfloor {\text{x}} \right\rfloor$ is the largest integer, which comes before ${\text{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 $\left[ {\left. {{\text{a}}_{\text{k}} ,{\text{b}}_{\text{k}} } \right)} \right.$ that determines encrypted number is reduced to $2^{\text{l}}$ times, where ${\text{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:

$$ \mathop \prod \limits_{\text{i}} \frac{{{ \hbox{max} }\left( {{\text{p}}_{\text{i}} ,{\text{q}}_{\text{i}} } \right)}}{{{\text{p}}_{\text{i}} + {\text{q}}_{\text{i}} }} * {\text{f}}_{ \hbox{max} }^{ '} ({\text{x}}) < \frac{1}{{2^{{{\text{n}} + {\text{l}}}} }} $$

After key generation number ${\text{l}}$ can’t be modified and is a part of the key. So, the secret key ${\text{K}}$ now is the set $[{\text{l}},\left( {{\text{a}}_{0} , \ldots ,{\text{a}}_{9} } \right),\left( {{\text{p}}_{1} ,{\text{q}}_{1} } \right),\left( {{\text{p}}_{2} ,{\text{q}}_{2} } \right), \ldots ,\left( {{\text{p}}_{\text{k}} ,{\text{q}}_{\text{k}} } \right)]$.

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 ${\text{p}}_{\text{i}} ,{\text{q}}_{\text{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 ${\text{p}}_{\text{i}} ,{\text{q}}_{\text{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 ${\text{m}}$-bit hash function is:

• 1. Select strictly increasing noise function f(x). To do this, generate $\left( {{\text{a}}_{0} , \ldots {\text{a}}_{9} } \right)$ so that

  $$ \left( {{\text{a}}_{0} + {\text{a}}_{1} {\text{t}} + {\text{a}}_{2} {\text{t}}^{2} } \right)({\text{a}}_{3} + {\text{a}}_{4} \sin \left( {{\text{a}}_{5} + {\text{a}}_{6} {\text{t}}} \right) + {\text{a}}_{7} \cos ({\text{a}}_{8} + {\text{a}}_{9} {\text{t}})) > 0 $$

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

• 2. Generate random set of ratios $\left( {{\text{p}}_{1} ,{\text{q}}_{1} } \right),\left( {{\text{p}}_{2} ,{\text{q}}_{2} } \right), \ldots ,\left( {{\text{p}}_{\text{m}} ,{\text{q}}_{\text{m}} } \right)$ .

• 3. The key is the set ${\text{K}} = [\left( {{\text{a}}_{0} , \ldots ,{\text{a}}_{9} } \right),\left( {{\text{p}}_{1} ,{\text{q}}_{1} } \right),\left( {{\text{p}}_{2} ,{\text{q}}_{2} } \right), \ldots ,\left( {{\text{p}}_{\text{m}} ,{\text{q}}_{\text{m}} } \right)]$ .

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: ${\text{s}}_{1}$ – size of the processed parts, ${\text{s}}_{2}$ – hash size for each of them (${\text{s}}_{2} < {\text{s}}_{1} )$, and ${\text{s}}_{3}$ – maximum file size. Obviously, final hash is $\frac{{{\text{s}}_{2} {\text{s}}_{3} }}{{{\text{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 ${\text{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 Sect. 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–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 ${\text{f}}\left( {\text{x}} \right) = 2186003864819$ and ${\text{f}}\left( {{\text{x}} + 1} \right) = 2186004033407$, where ${\text{f}}({\text{x}})$ is encryption function, then ${\text{f}}\left( {{\text{x}} + 1} \right) - {\text{f}}\left( {\text{x}} \right) = 168588$ is considered. One of the reasons for this choice was the fact that success of chosen-plaintext attack by interpolation depends on this differences (see Fig. 2).

Fig. 2.

Chosen-plaintext attack using values interpolation. Ciphertext for some ${\text{b}}_{1}$-bit plaintext ${\text{x}}$ is approximated by the value of $\frac{\text{x}}{{2^{{{\text{b}}_{2} }} }}$, where ${\text{b}}_{2}$ is size of ciphertext. Approximation in the other direction is counted similarly.

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.

Fig. 3.

Frequency distribution of the differences between ciphertext.

As we see, this chart and right hyperbola ${\text{y}} = \frac{1}{\text{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 ${\text{f}}\left( {{\text{x}} + 1} \right) - {\text{f}}({\text{x}})$ when the X-axis shows ${\text{x}}$ (from 0 to 65535).

Fig. 4.

Distribution of the differences on the interval.

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.