{'fraction_non_alphanumeric': 0.03426761949591339, 'fraction_numerical': 0.007942145577474432, 'mean_word_length': 4.872543599537619, 'pattern_counts': {'":': 0, '<': 20, '<?xml version=': 0, '>': 16, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
T-DB: Toward Fully Functional Transparent Encrypted Databases in DBaaS Framework

Individuals and organizations tend to migrate their data to clouds, especially in a DataBase as a Service (DBaaS) pattern. The major obstacle is the conflict between secrecy and utilization of the relational database to be outsourced. We address this obstacle with a Transparent DataBase (T-DB) system strictly following the unmodified DBaaS framework. A database owner outsources an encrypted database to a cloud platform, needing only to store the secret keys for encryption and an empty table header for the database; the database users can make almost all types of queries on the encrypted database as usual; and the cloud can process ciphertext queries as if the database were not encrypted. Experimentations in realistic cloud environments demonstrate that T-DB has perfect query answer precision and outstanding performance.


INTRODUCTION
Cloud computing is an Internet-based commercial computing pattern based on networking, virtualization and distributed technology, where shared resources are allocated on demand [1,2]. In such a dynamic and open environment, each cloud user has easy access to high computation speed and large storage capacity. Gradually, cloud computing is widely accepted by industry around the world. According to the survey data announced by International Data Corporation (IDC) [3] in early 2016, worldwide spending on public cloud services will grow at a 19.4% compound annual growth rate from nearly 70 billion dollars in 2015 to more than 141 billion dollars in 2019. Among them, cloud IT infrastructure spending will reach 53.1 billion dollars, which will be 46% of total expenditures on enterprise IT infrastructure. In the same year, a latest report from the famous American IT market research agency TBR (Business Research Technology) [4] predicts that worldwide public cloud revenue will increase from 80 billion dollars in 2015 to 167 billion dollars in 2020. We can see that a notable growth space still exists in the highly competitive public cloud market. Various cloud-based products are emerging in endlessly. Data outsourcing is one of its most important applications as well as a research focus of the trusted cloud computing.
In recent years, more and more individuals and organizations have been migrating their private data into a Cloud Service Provider (CSP). About data outsourcing, the DataBase as a Service (DBaaS) [5,6,7] has become one of the most representative service patterns, e.g., Amazon RDS, Google Cloud SQL, Microsoft Windows Azure SQL Database, Tencent CDB, etc. They all are committed to a cloud database platform similar to the well-known Relational DataBase Management System (RDBMS).
DBaaS conveys a great number of conveniences and benefits, but once stored on the cloud storage servers, the outsourced private data (e.g., personal health care records, financial transaction, etc.) could be disclosed or abused. The security issues of the outsourced databases are increasingly important. The open challenge is to simultaneously achieve database secrecy and full utilization.
Currently, in most public clouds, the approach for the CSP to protect cloud database security is by enforcing cloud-centralized security strategies including resource isolation, authorized access and cloud encryption, etc. For some commercial products, such as SecureDB or Windows Azure SQL Database, encryption is considered critical to prevent various malicious intrusions from external attackers.
For the cloud-centralized security strategies to work, it is necessary that the CSP is willing and able to secure the outsourced database, which is a quite strong assumption in practice. These cloud-centralized security strategies cannot prevent the malicious CSPs from exploiting the outsourced data for commercial benefits. Also, they fail to prevent malicious inner attackers, e.g., the corrupted employees. Furthermore, if the CSP is hacked, then the outsourced database could be fully exposed to attackers.
One possible solution is for the owner to encrypt her database so the CSP is no longer involved in secret key-dependent operations. The database is encrypted before being outsourced to the CSP. This, however, incurs a utilization problem for the encrypted database and requires elegantly designed encryption schemes. So far, encryption technologies have been developed to support Equality Query [8,9,10], Range Query [11,12,13], Aggregation Query [14,15,16] and Fuzzy Query [17,18,19]. Yet, none of them could support the queries as the plaintext database does. Fully homomorphic encryption techniques [20] theoretically permit arbitrary operations over encrypted data, but the computational complexity of encryption/decryption is prohibitively high [21].
In 2011, a research team [22] from MIT released the famous CryptDB. It supports most manipulations on encrypted databases based on Structured Query Language (SQL). However, CryptDB is not available in the DBaaS framework. Specialized encryption algorithms are adopted respectively to interpret various kinds of SQL statements. The SQL operations cannot be performed directly. Instead, the database owner sends the secret keys to the cloud servers for the onion decryptions when processing a query, which introduces security risks similar to those in cloud-centralized security strategies. Variants [23,24] using different encryption algorithms lead to serious performance degradation and heavy reliance on the trusted proxies. Moreover, they require changing the access mode of database users as well as the structure of the cloud database. Other variants (e.g., [25,26]) simply allow limited types of ciphertext manipulations. *Corresponding author.
In view of the limitation in performance of homomorphic techniques and the incompatibility in functionality of existing solutions, our T-DB in this paper is a new comprehensive encrypted database system with database-owner-centralized security strategies under the standard DBaaS framework. It is the first time that all the known types of potential ciphertext queries (i.e., equality, range, aggregation and fuzzy queries) are truly covered through a single cipher, and our average efficiency of ciphertext queries is actually better than that of homomorphic encryptions. The contributions of this paper are summarized as follows: 1) We strictly follow the DBaaS framework and present T-DB equipped with distinguishing features. It can perform almost all of data manipulations over outsourced encrypted databases. T-DB is built for the database users who make queries on plaintext data; the database owner who outsources the encrypted database to the CSP, translates and forwards queries from the database users to the CSP, and decrypts and returns answers to the users; and the CSP who executes encrypted queries on encrypted databases as if they were not encrypted. All the operations involving secret keys are performed by the database owner, who can hence be assured that the database is under her control. The database users and the CSP just work as usual and there is no need for a database user to change the way he accesses the database. Thus T-DB is implementation-friendly and user-friendly.
2) With the help of User-Defined Function (UDF), we deployed T-DB on an unmodified cloud RDBMS server within 30 lines of codes at the cloud server side and a local client machine using standard SQL syntax at the database owner side. We demonstrate that T-DB is secure under two threat models. This is achieved on the premise of supporting almost all types of queries and dynamic updates over an encrypted database.
3) A novel order preserving encryption algorithm with additivity and an SQL-based syntax interpreter are constructed, which allow direct comparison and addition to be executed transparently on ciphertexts by one-time encryption and statement translation. Formal security analyses indicate that this cipher tool can resist weak chosen-plaintext attack. 4) Experimental results show that T-DB supports more queries and achieves a precision rate (or a recall rate) of 100%. Compared with CryptDB under the same precision, query processing in T-DB is faster and its decryption time for query results is shorter. Also, the T-DB applicability is validated on Microsoft Windows Azure SQL Database.
The remainder of this paper is organized as follows: Firstly, Section 2 and Section 3 give an overview of the model and architecture. Then in Section 4 and Section 5, two core modules are proposed. Performance evaluations are provided in Section 6. Finally, we fully discuss the system security, some special cases, related works and future direction in Section 7, and conclude the study in Section 8.

BASIC MODEL
In this section, we define clearly the generalized system model of DBaaS framework and its major security threats, requirements and design objectives. The database owner should emphatically consider two problems during cloud outsourcing. For one thing, how to outsource a database to the cloud, in order to ensure the data storage confidentiality. For another, after the database is outsourced to the cloud, how database users normally get access to their data.

System Model
Data outsourcing is to outsource complex data structure, data storage and data computation to the CSP. The major objective of outsourcing data is to allow the cloud users avoid the lack of local resources, and minimize the cost of deployment, operation and maintenance in data application systems. As one of the most important patterns, database resources are pooled by DBaaS and delivered to database users through network in the form of cloud service. The cloud is responsible for the storage of structured business data, and provides comprehensive database functionalities, including data analysis and data processing.
As an enterprise-level cloud storage service, DBaaS framework allows a database owner inside an enterprise to outsource her internal database to the CSP, thus reducing the cost of management and maintenance in the enterprise. The generalized system model of DBaaS is shown in Figure 1, which is composed of three types of entities, i.e., Database User, Database Owner and CSP. More details are as follows:

Data Flow
The outsourcing flow for plaintext databases is as follows: 1) The database owner secretly generates and keeps the secret keys. A database is encrypted before it is outsourced. After that, no copy of the plaintext database and the encrypted database is preserved by the database owner.
2) The CSP receives and stores the encrypted database. Query-related UDFs are also built and optimized in advance. The data manipulations on encrypted databases are as follows: 1) The database user k uses his password P k to log into the system, and submits a plaintext SQL to the database owner.
2) According to access control policies, the database owner checks whether the query request is authorized and from a legal user. If it is an unauthorized access, then this manipulation is refused and a security alert is returned.
3) The database owner translates the plaintext SQL statement into ciphertext SQL statements, and sends them to the CSP. 4) Appropriate UDFs are invoked by the CSP to execute the ciphertext SQL over the encrypted database, and several encrypted query results are returned.
5) The database owner receives and decrypts the result set, and returns the plaintext query results to the database user k. Figure 2 also shows the data processes in T-DB. Compared with existing models for outsourcing secured data, a distinguishing feature of T-DB is that all crypto-operations are performed by the armed database owner so that they are transparent to both the database users and the CSP. More specifically, the database owner fulfills the following four tasks:

Module Design
1) The database owner keeps the table structure of the original plaintext database, such as the database diagram, field type, field length, scope of data items, and so on.
2) In the pre-processing stage, the database owner adopts two cipher tools to encrypt and outsource the plaintext database. The data items are encrypted with an SQL-oriented encryption algorithm, and the table names and column names are encrypted with a symmetric encryption algorithm or a collision-resistant salted hash function. The database owner always encrypts different data items with different secret keys. These keys are assigned through a pseudo-random generator with a seed key to simplify key management.
3) In the manipulation stage, the database owner translates the plaintext SQL statements by an interpreter (e.g., SQL-Translator) into a set of ciphertext SQL statements with the same semantics. For more details about translation methods, please see Section 5. 4) In the post-processing stage, the database owner decrypts the CSP's answer of the ciphertext SQL statements and returns the final results to the database user.
To ensure data secrecy and normal access to cloud storage, the database owner needs to deploy two additional modules, namely cipher module and translation module. The former is to achieve secrecy so that the database is accessible via its owner, and database updates are supported. The latter is to guarantee that neither the CSP nor database users are affected due to the cipher module.

CIPHER MODULE: OPEA
The cipher module executes the encryption when data are outsourced to the CSP, which ensures that the ciphertext manipulability is well preserved in DBaaS. This implies that the encryption algorithm is somewhat homomorphic. Observe that the majority of data manipulations in relational databases can always be converted into range queries and aggregation queries. Therefore, for T-DB system to work, its cipher module needs to simultaneously meet order-preservation and additivity. These requirements thus define a novel cipher tool of Order Preserving Encryption with Additivity (OPEA).
In this section, the basic idea of OPEA is introduced first, followed by its boundary generation sub-algorithm, encryption sub-algorithm and decryption sub-algorithm. Several properties are then formally described in detail. We also provide some simplified and extended versions. The end of the section further analyzes their security and limitation.

Basic Idea
An appropriate SQL-oriented cryptographic technique is needed to execute ciphertext manipulations over outsourced encrypted databases, and thus the cipher tool should be order preserving as well as additive. To this end, we introduce a new idea that is closely related to the order preserving encryption.
Order Preserving Encryption (OPE) is a cryptographic technique which can keep the plaintext order after encryption [11]. The first order preserving encoding function for numeric data was proposed by Agrawal et al. [11] in 2004, whose one-to-one mapping encoding is inefficient and vulnerable to the statistical attack. mOPE [12] works on an interactive encryption protocol to build an encrypted balanced search tree. It hides the order in its ciphertexts and uses additional operations to finish the comparison. Popa et al. [12] showed that mutable ciphertexts are necessary for the ideal IND-OCPA security [27]. Deterministic OPE algorithms always lead to the leakage of plaintext distributions, particularly for those asymmetric OPEs that can be broken easily. The attacker first encrypts every value in the plaintext domain with public keys. Then the relationship between a plaintext and its corresponding ciphertext is established. Any ciphertext can be matched quickly with binary search, thus its plaintext is deciphered successfully. One straightforward solution to the above drawback is to map each plaintext value to a random number in the irregular range with a certain probability, that is, the plaintext should be encrypted by the one-tomany mapping. For example, Reddy and Ramachandram designed a Randomized OPE (called ROPE [28]), which follows the mOPE in [12]. It leaks nothing except the comparison order. On the premise that the whole distribution of the plaintext domain is selected in advance, a recent LiuOPE [29] draws support from the nonlinear space split and some one-to-many mapping functions to extend the message space. It can resist ciphertext-only attacks or particular chosen-plaintext attacks. The one-to-many mapping in LiuOPE is obviously boundary-crossing. Precision loss and the leakage of boundaries of ciphertext partitions might appear in equality queries.
The comparison order among plaintext values is fully preserved by OPE, whereas its order-preservation is no longer valid after several ciphertexts are added together. Therefore, although most of the existing OPE schemes can be incorporated in equality queries, range queries or its relevant extensions, they cannot run any aggregation queries that contain algebraic operations without decryption, such as SUM function and AVG function. The application of OPE techniques in data manipulations of encrypted databases is limited due to the lack of additivity. The main reason is that the comparison and the aggregation in a practical query request are usually operated in an irregular way. In order to facilitate the composite queries, ciphertexts should keep in order after being added together. Besides, although a subtraction can offer the same query as a comparison, the RDBMS row-based access determines that the data items in the same column are hardly sorted through subtraction.
We illustrate an OPEA, inspired by well-established OPE algorithms [11,12,28,29] with one-to-many mapping, that allows both comparison and summation to be operated on ciphertexts. Numerical order can still be preserved after several ciphertexts are added together. Specifically, the OPEA encryption function E: X→Y meets the following conditions: 1) Order-Preservation: ∀a, b∈X, a<b iff E(a)<E(b).
2) Additive order-preservation: . where X and Y represent the plaintext and the ciphertext domain respectively. The algorithmic design of OPEA is relatively straightforward, but technically it is quite suitable for the encrypted database system to develop.
The mapping structure of the OPEA encryption is illustrated in Figure 3. A discrete ciphertext domain is composed of sequential partitions, and there is a non-empty mutable interval between two adjacent partitions. As shown in this figure, for the one-to-many encryption, a plaintext value b is mapped to a random number in the partition [L b , U b ], where L b and U b are the lower boundary and the upper boundary of this partition respectively. Intervals ensure that no overlap exists between any two partitions, that is, for any value c (c>b), its lower boundary L c should be strictly greater than the upper boundary U b . Similarly, for any value a (a<b), its upper boundary U a should be strictly less than the lower boundary L b . Meanwhile, in order to meet the additive order-preservation, the inequation U a +U b <L c should strictly hold.
Ciphertext domain Partition Interval Figure 3: One-to-many mapping in OPEA encryption.
Throughout the paper, we assume that the lower (resp. the upper) boundary of the ith partition can be written as L i or L[i] (resp. U i or U[i]) for easy presentation.

Algorithm Description
Without loss of generality, we define the plaintext domain of OPEA as a part of positive integers, that is, X⊆N + . According to the basic ideas in Section 4.1, OPEA can be summarized formally as a symmetric encryption algorithm, i.e., (BoundaryGen, Enc, Dec), including three sub-algorithms: 1) Boundary generation sub-algorithm (Algorithm 1).
This sub-algorithm takes R and σ which are selected randomly as system keys to return two finite integer sets (L and U). R={R i } (1≤i≤T) is a set of non-negative integers, and σ is a positive integer with σ>max 1≤i≤T {R i }-R 1 , where T is the maximum value in the plaintext domain.
L (resp. U) contains the lower boundaries (resp. the upper boundaries) of every partition in the ciphertext domain.
for t=2 to T do 3: Compute end for 6: return L, U The first partition [L 1 , U 1 ] is selected randomly by the database owner in its initialization phase, and the lower and upper boundaries of subsequent partitions are computed iteratively. Finally, the boundary sets generated by this sub-algorithm divide the ciphertext domain into some discrete partitions. The length of the partition [L i , U i ] for the plaintext i is determined by the random number R i =U i -L i , and the introduced interval between two sequential partitions can ensure non-overlap and additive cipher. We clarify the above mapping relation in Figure 3, where R 1 =R 3 =1 and R 2 =3.
2) Encryption sub-algorithm (Algorithm 2). This quasi-probabilistic sub-algorithm takes a plaintext value m and two boundary sets (L and U) to return its ciphertext c=E(m). The function RandomSelect(·) is defined to select a random element from the parameter set {L[m], L[m]+1, …, U[m]} and return it as ciphertext. Intuitively, the encryption function keeps the numerical order of plaintexts, which will be fully discussed in Section 4.3.

Algorithm 2 E(m)←Enc(m, L, U)
3) Decryption sub-algorithm (Algorithm 3). This deterministic sub-algorithm takes the boundary set L and a ciphertext value c to return its plaintext m=D(c). The ciphertext is decrypted by means of a reverse mapping and the process is similar to binary search method.

Algorithm Property
Some properties about correctness, order-preservation and additivity of the OPEA algorithm are given below. 1) Correctness. As an order preserving encryption algorithm, the encryption function and the decryption function in OPEA output strictly the correct pairs of plaintext-ciphertext and always preserve their order. Since there is no overlap between different partitions and every ciphertext corresponds to a unique partition, the index of this ciphertext partition (i.e., the plaintext value) can be decrypted correctly by a lookup of the boundary set L. Then correctness of OPEA is proven as follows: ∀m∈X, m←Dec(Enc(m, L, U), L) 2) Order-Preservation. Several lemmas are first established.

Simplified and Extended Version
There are simplified and extended versions of the OPEA algorithm, which are discussed below.

Simplified Version of OPEA
The one-time BoundaryGen needs O(T 2 ) computations to generate T pairs of boundaries. In order to reduce the local computational cost, the secret keys R i (1≤i≤T) should be generated in a non-decreasing order. A simplified boundary generation sub-algorithm (L, U)← SBoundaryGen(R, σ) is developed as Algorithm 4.

1:
Set S=0 2: for t=1 to T do 3: Compute Compute S=S+R t 6: end for 7: return L, U From Line 3 to Line 5 in Algorithm 4, the lower and upper boundaries of ciphertext partitions can be calculated in linear time, which is proven as follows: Theorem 3 (Linear boundary function). For any integer t (1≤t≤T), its lower and upper boundaries satisfy that The second mathematical induction is used to prove the correctness of Theorem 3. Basis: In light of Line 1, Algorithm 1, Eq. (1) holds for t=1. L [1] (1) and O(log T), respectively. In particular, SBoundaryGen is a one-time function. Private boundaries would not have to be updated after being generated locally. As for some sparse databases, there is no need to calculate partitions for every integer in the plaintext domain. Here, computing on demand is allowed. When a new value appears in the database or a value is updated, the database owner just needs to calculate the boundaries for its corresponding partition, as long as enough ordered random numbers are reserved in the initialization phase.

Extended Version of OPEA
According to the converse-negative proposition of Theorem 2 obtained in Section 4.3, the additive numerical relation a 1 +a 2 +...+a k ≥b is determined by its ciphertext inequation, i.e., E(a 1 )+E(a 2 )+...+E(a k )≥E(b). But for the negative proposition of Theorem 2, we also study the

Simplified Version of Extended OPEA
T+1 non-decreasing random numbers are generated, which satisfy that R i ≤R j and σ>3R T for 1≤i<j≤T. A simplified version of the extended OPEA (see Algorithm 6) is developed into (L', U')←SBoundaryGen'(R, σ).

1:
Set S=0 2: for t=1 to T do 3: Compute S=S+R t 6: end for 7: return L', U' It reduces the time complexity of the extended OPEA from O(T 2 ) to O(T) successfully. From Line 3 to Line 5 in this sub-algorithm, we can also derive a new theorem for the linear boundary function in the extended version.

Theorem 5 (Linear boundary function of extended version). For any integer t (1≤t≤T), its extended lower and upper boundaries satisfy that
This theorem can be proven in exactly the same way as that of Theorem 3. Eq. (4) is easily derived from its definition. The second mathematical induction is used to prove the correctness of Eq. (3).

U'[t]>0, L'[t]>0
, 1≤t≤T Furthermore, for any integer t (1<t≤T), the interval between two partitions is Therefore, it can be seen that any two adjacent partitions are non-overlapped, which conforms to the limitation in Line 4, Algorithm 5. In addition, let us assume that ς (|ς|≥2) is a set of positive integers, whose arithmetic sum is denoted as SUM(ς). E(ς)←Enc(ς, L, U) and E'(ς)←Enc(ς, L', U') are two encrypted sets. Thus, for a non-decreasing sequence R and any plaintext (i.e., value) with σ≥(value+|ς|)·R T - Since R is a non-decreasing random sequence in the simplified version, we have that max 1≤i≤T {R i }=R T as well as min 1≤i≤T {R i }=R 1 . So it is further noticed that Therefore, we have 1 1 Proof. This theorem can be proven in exactly the same way as that of Theorem 6, so we have ( ) It is further noticed that  □ The analyses of functionality limitations in OPEA indicate that only the comparison between a summation of a set of ciphertexts and a fixed threshold is available (for more illustrations, please see Section 4.6). So there may be some possible extensions in functionalities and one would also like to present a novel additive order preserving encryption scheme. Related cryptographic techniques need more investigation in the future.

Security Analysis
Formal analyses in this subsection demonstrate that our OPEA can resist ciphertext-only attacks, statistical attacks and weak chosenplaintext attacks in the process of executing data manipulations.

Ciphertext-Only Attack
Due to the undiscovered partition precision, the initial location σ as well as the partition length R, the adversary A fails to infer the plaintext distributions based on the distance between ciphertexts. If A is allowed to select a finite number of ciphertext values in the game, he should first determine the lower and upper boundaries of the encrypted partition [L m , U m ] in order to guess successfully the plaintext m and its secret key R m . And for this purpose, A needs to get at least four encrypted values (i.e., V 1 , V 2 , V 3 and V 4 ), where V 1 is the ciphertext of m-1, V 2 and V 3 are the ciphertexts of m, and V 4 is the ciphertext of m+1. Meanwhile, V 2 =V 1 +μ 1 and V 4 =V 3 +μ 2 should be set up, such that μ 1 and μ 2 are the interval length between two partitions. From the inequation L[t]-U[t-1]≥U [1]=σ+R 1 , 1<t≤T, one could easily argue that μ 1 and μ 2 are influenced by the initial random number σ+R 1 . Besides, a ciphertext E(m) is randomly selected from the partition [L m , U m ] with length R m =U m -L m , then the probability of successful attack is at most 2 , , The justification is that, in the one-to-many mapping, every encryption is mapped to different ciphertexts, and every decryption does not provide any assistance to analyze the private boundaries. It can be seen that the bigger σ+R 1 or R m is, the wider interval or alternative ciphertext partition will be. So by choosing the random parameters appropriately, the P[success A, R, σ ] tends to be negligible, and the security is enhanced significantly with the help of randomness in this probabilistic encryption. Hence, we can conclude that OPEA is secure enough under a ciphertext-only attack.

Statistical Attack
The statistical method of calculating ciphertext frequency is also one of the possible ciphertext-only attacks. Under this attack, if two plaintext values (m 1 and m 2 ) have a totally different distribution like P[x=m 1 ]<P[x=m 2 ], then the adversary A may assert that their ciphertext values should satisfy that P[x=E(m 1 )]<P[x=E(m 2 )] with a high probability. As a consequence, he successfully breaks the cryptosystem. In fact, most of the existing OPE schemes are vulnerable to statistical attacks because of their deterministic one-to-one mapping.
Probabilistic encryption is used in OPEA to prevent the statistical attack. The plaintext distribution is altered by the one-to-many mapping, so the probability of ciphertext distributions turns to be [ ] [ ( )] m P x m P y E m R = = = By this way, OPEA succeeds in preventing the statistical attack. A simulative evaluation was performed on the input and output distribution of OPEA. Figure 4 shows the distributions of ciphertext domain under different distributions of plaintext domain (e.g., normal distribution or uniform distribution). As shown in Figure 4, it is obvious that the ciphertext domain encrypted by OPEA is nearly uniform (Figure 4b) for bigger R m , regardless of the plaintext domain distribution (Figure 4a), which suggests that the adversary A cannot acquire any additional statistical information from ciphertexts.

Chosen-Plaintext Attack
Theoretically, if it is assumed that a malicious attacker has some prior knowledge about finite plaintext values, all of the existing OPE schemes based on one-to-one mapping are not secure for the known-plaintext attack. For example, if an attacker obtains two pairs of given plaintext-ciphertext, that is, (m 1 , c 1 ) and (m 2 , c 2 ), then as for another ciphertext c 3 with c 1 <c 3 <c 2 , the attacker will easily guess that its corresponding plaintext value m 3 belongs to the interval [m 1 , m 2 ]. As you could see above, knowing that specific datasets have been encrypted with OPE provides useful information to get the approximate plaintext value. Clearly, such OPE schemes are also vulnerable to a chosenplaintext attack in the standard model. So, one approach to guarantee security for OPEA is to try to reveal no additional information about the plaintext values except their numerical order. The most ideal security definition is INDistinguishability under Ordered Chosen-Plaintext Attack (IND-OCPA), presented by Boldyreva et al. [27]. Surprisingly, almost no OPE scheme achieves it. Popa et al. [12] have proven that any stateful IND-OCPA-secure OPE must have ciphertext size at least exponential in the plaintext size, and the ciphertext mutability is necessary for IND-OCPA security. Regarding our OPEA, although it is a stateful algorithm with mutable ciphertexts, its additivity leaks the multiple relations or the distance relations among plaintexts, causing vulnerabilities in IND-OCPA.
For simultaneous order and additivity preservation, we weaken the IND-OCPA [27] security notion to the INDistinguishability under an Additive Ordered Chosen-Plaintext Attack (IND-AOCPA), and show that the honest-but-curious cloud servers cannot obtain any additional sensitive information except that inferred by the ciphertexts' order and additivity. In a practical sense, this information leakage is inevitable to guarantee the normal data manipulation of encrypted databases.
As for the security game for IND-AOCPA, it requires the chosen plaintexts in each round to satisfy the same order and multiple relations. In what follows, let us suppose that the CSP does not have any prior knowledge about the plaintext domain, and there is no collusion in any way between the CSP and database users. Queries on sequential plaintext values are generally not allowed, and the pseudo-random number generator used to assign secret keys is assumed to be secure.
Similar to [12], the following game is modeled between the database owner and a Probabilistic Polynomial Time (PPT) adversary A from the CSP, which is called IND-AOCPA Game. It has one more constraint to the adversary A compared to previous IND-OCPA Game, i.e., the plaintexts in queries are bounded by a proportional relation. Our IND-AOCPA Game is consisting of three stages.
1) The database owner generates the private boundaries (L, U) by secret keys (R, σ), and selects a random bit b.
2) The database owner and the adversary A repeat an adaptive encryption query through a polynomial number of rounds. Then at the round i: a. The adversary A selects two values v 0 (i) and v 1 (i) from the plaintext domain, and sends them to the database owner. b. The database owner encrypts the value v b (i) by Enc(v b (i), L, U), and sends its ciphertext E(v b (i)) to the adversary A.

3) The adversary A outputs his guess b'.
The adversary A wins in this security game when the following three conditions hold simultaneously: 1) The adversary A outputs the right guess, namely, b=b'.
3) The input sequences {v 0 (i)} and {v 1 (i)} have the same multiple relations, namely, for any i, j, Then we have a new security definition. Definition 1. An OPE is IND-AOCPA-secure if any polynomial time adversary has only a negligible advantage in the IND-AOCPA Game shown above, where the adversary wins with a probability P cpa [win A, R, σ ] and his advantage is defined as , , Proof. The main step is to prove the information that A obtains in the case b=0 is the same as that in the case b=1. Assume by inductive method that before the second game stage and after the ith round in the second stage, the same information is learned by A. Then after the (i+1)th round encryption, since the sequences {v 0 (i)} and {v 1 (i)} have the same multiple relations, v 0 (i+1) and v 1 (i+1) satisfy that Then it is true that So the adversary A obtains nothing from ciphertexts other than the same duplicates, multiple relations and order relations in both cases. In the point of information theory, there is no way for A to distinguish between {v 0 (i)} and {v 1 (i)}. For all sufficiently large secret keys (R, σ), a conclusion follows that , , where negl(R, σ) is a negligible probability. The proof of Theorem 8 is completed. The adversary A wins in the above security game with the probability P cca [win A, R, σ ] when the following two conditions hold simultaneously: 1) The adversary A outputs the right guess, namely, b=b'. 2 With further analyses, OPEA is clearly not IND-OCCA-secure. It is not secure under the ordered chosen-ciphertext attack as long as a plaintext-ciphertext pair is revealed by A. It is no longer important to consider the multiple relations now. The proof of Theorem 9 is completed.
□ For T-DB system to simultaneously perform range queries and aggregation queries over ciphertexts, the IND-AOCPA in the OPEA algorithm is the best security that has been proven formally so far.
Besides, as [30] has noted, there are a series of ciphertext-only inference attacks on the relational databases encrypted using OPE. According to the research conclusions [30] from Naveed et al., given the encrypted database along with some auxiliary information, an attacker can guarantee the success of recovering parts of underlying plaintext values. Thus it can be seen that the order-preservation makes OPE algorithms suitable for range queries on encrypted data, while it also inherently limits the achievable security. To this end, a recent research team [31,32] from the Stanford University constructed a highly-efficient, non-interactive and stateless Order-Revealing Encryption (ORE) scheme with the best-possible semantic security. It takes advantage of the special structure of ciphertexts to perform ciphertext search while protect against inference attacks. However, before we use the ORE in place of OPE to support range queries in the encrypted database, the cloud RDBMS is required to deploy a custom comparator. In addition, since the ORE does not include any decryption function, its encryption function and comparison function have to be invoked many times to decrypt the query results. The final plaintexts are recovered by a binary search, which causes a significant increase in the computational overhead of the database owner. In conclusion, ORE techniques are far from being practically viable in the encrypted database, and their supported query functionalities are also limited so far. Moreover, the study of a secure ORE with additivity is still an open and notable question.

Algorithm Limitation
As the cipher tool in T-DB, OPEA settles the problem about the utilization of data manipulations in outsourced encrypted databases. Nevertheless, there are still some deficiencies remaining. For example, combined with the additive order-preservations in Theorem 2 and Theorem 4, a corollary is made as follows: There is no such probabilistic OPE scheme that can be used to judge the order relation between the sum expression a 1 +a 2 +...+a k and b 1 +b 2 +...+b k' .
Proof. The proof is by contradiction. Firstly, we assume that there exists a probabilistic OPE algorithm to compare E(a 1 )+E(a 2 )+...+ E(a k ) and E(b 1  □ Hence, the above assumption is actually invalid. There is no feasible method to construct a probabilistic encryption algorithm by dividing ciphertext partitions with intervals, otherwise the order-preservation and the additive homomorphism should be satisfied simultaneously, which turns OPEA into a completely deterministic encryption.

TRANSLATION MODULE: SQL-TRANSLATOR
The translation module works to hide the outsourced databases' changes that result from encryption from the CSP and database users so that they can behave as if the database were not encrypted. The database users can query the database server as usual and receive the appropriate answers. The CSP can process almost all kinds of SQL queries (from the database owner) as in the standard DBaaS pattern, and may not notice that it is executing manipulations on an encrypted database. We work on Microsoft SQL Server but stress that our work can be easily extended to other relational databases.
The general method adopted by T-DB system to execute data manipulations over an outsourced encrypted database is discussed in this section. To begin with, two user-defined functions are designed to solve the problem of equality comparison. Secondly, an SQL interpreter (called SQL-Translator) is deployed on the database owner to translate a plaintext SQL statement into ciphertext SQL statements that can be executed directly on the cloud server. Various translation rules about common data manipulations and relational operations [33] in the process of translating statements are introduced in detail. We finally summarize several classes of functionality limitations and formal syntax rules in SQL-Translator.

Equality Comparison Function
Two cloud UDFs are established as follows: 1) Equality comparison for two values (Algorithm 7). Since OPEA is a kind of probabilistic encryption algorithm, the same plaintext may be encrypted to different ciphertexts frequently. In order to determine whether two plaintexts (value 1 and value 2 ) are equal by their ciphertexts (i.e., E(value 1 ) and E(value 2 )), the database owner should pick out a random integer x∈[max{R 1 , R 2 }, σ+R 1 ) based on secret keys and send it to the cloud RDBMS, where R 1 (resp. R 2 ) is the length of the partition that value 1 (resp. value 2 ) belongs to. As we can see from Line 3, Algorithm 1, the expression L[t]≥U [1]+U [t-1] holds for any t (t=2, 3, …, T), so the interval between two sequential partitions satisfies that 1≤j≤T That is to say, the x is between the partition length R j (1≤j≤T) and the interval length L[t]-U[t-1] (t=2, 3, …, T). The difference between ciphertexts of two different plaintexts is bigger than x, while the difference between ciphertexts of a single plaintext is no bigger than x. Hence, a cloud UDF (i.e., EqualityCom) for two-value equality comparison can be made by the pre-selected x.
if |E(value 1 )-E(value 2 )|≤x then 2: return 0 //value 1 =value 2 3: else if E(value 1 )>E(value 2 ) then 4: return 1 //value 1 >value 2 5: This algorithm is running on the random number x and two encrypted values. If output is 0, then two plaintext values are equal; If output is 1, then the first plaintext value is bigger than the second one; If output is -1, then the first plaintext value is less than the second one.
In general, the selection of x is based on some partition boundaries of the ciphertexts that are to be queried by the database users, thereby avoiding the possibility that an attacker determines the equality of other plaintexts. Every time the database user proposes a new query request, the database owner will reselect x according to the encryption granularity and scope of data items. This value is only available for all the possible plaintext items requested by the current database user within his authorized scope, which does not reveal more information about the outsourced data on the cloud. The CSP would invoke the EqualityCom function to accomplish each subsequent equality comparison in pairs, without involving the database owner.
2) Equality comparison for arithmetic sum (Algorithm 8). This part focuses on the equality comparison between an arithmetic sum (i.e., SUM(ς), |ς|≥2) and a plaintext (i.e., value). This algorithm runs securely on the CSP. If output is 0, then the arithmetic sum is equal to the plaintext value; If output is 1, then the arithmetic sum is bigger than the plaintext value; If output is -1, then the arithmetic sum is less than the plaintext value.

Design Principle
The database owner is in charge of translating plaintext SQL statements, so the process of data manipulations is transparent to database users and the CSP. The cloud server can execute exact data manipulations over outsourced encrypted databases without being able to find out the original request. Different from previous studies [22,23], the key point of SQL translation in T-DB lies in how to run all kinds of data manipulations on the results of a single encryption.
A syntax interpreter based on standard Transact-SQL Data Manipulation Language (DML) [34] is implemented to translate a plaintext SQL statement into a set of ciphertext SQL statements with negligible computational costs. It targets the outsourced database that is stored in the form of OPEA ciphertext. Some specific rules of storage format can be obtained from Section 7. The major procedure of SQL-Translator is described as Figure 5, where a minimum translation unit is defined as a sub-statement that contains a perfectly formed clause structure or predicate expression, i.e., a separate operator and data operational entities.  Specific translation steps are as follows: 1) Extract and then translate database entities in the plaintext DML statement, including table names, data fields, constants, etc. The translation rule is that a. The table name or the data field is translated with a symmetric encryption algorithm (e.g., AES, Blowfish, etc.) or a salted collisionresistant hash function for anonymization.
b. The constant in the statement is translated by the OPEA algorithm, e.g., the constant expression in a range query, the pattern string in a fuzzy query (except the wildcard characters), and the data items in insert, delete and update operations.
2) Divide the statement by SQL keywords and syntactic structure into minimum translation units.
3) Invoke the corresponding translation module in turn to translate the minimum translation unit, see Section 5.3 and Section 5.4 for more details about translation rules. 4) Concat and reorder the translation results, while preserving DML semantics. 5) Return the ciphertext DML statements that can be executed on the outsourced encrypted database directly. The set of ciphertext SQL statements translated by SQL-Translator strictly follows Transact-SQL standard, so it runs directly on the universal RDBMS. If there is no need for the ciphertext manipulation to declare variables dynamically, then the translated results might be expressed as a store procedure to improve the query efficiency of cloud databases.
To facilitate the understanding of SQL-Translator, we take the following plaintext query statement as an example: where tbl is a table name, Att 1 and Att 2 are the column names, and num is a constant. The above plaintext statement is translated by SQL-Translator into the following ciphertext query statement that can be executed directly over the encrypted database: where * C denotes the corresponding database object or data manipulation in the ciphertext domain. L[num] and U' [num] represent relevant judgment parameters about num. EqualityCom and SumEqualityCom are two UDFs which are built by the cloud in advance (Algorithms 7 to 8 and Protocol 1). They are invoked by the CSP to make equality comparison or aggregation comparison respectively (see Section 5.1 for more details about UDFs). The x value is a pre-selected random number used to judge the equality in our probabilistic encryption algorithm.
In what follows, we illustrate various translation rules of minimum translation units. More formal syntax conventions and syntax rules are available at [35] and Section 5.6 for lack of space.

Translation Rule of Data Manipulation
The detailed translation rules of minimum translation units (extended functionalities may always be simplified or decomposed to these units) are published in this subsection. A data manipulation statement s over the plaintext database DB is translated into ciphertext statements s C over the encrypted database DB C . For brevity, in the rest of this paper, Att, Att 1 and Att 2 denote field names in a plaintext table, and val, val 1 and val 2 denote three constants.

Query
A query manipulation is to retrieve the data tuples that satisfy certain query conditions. SELECT is the most complex statement in the plaintext database, whose basic grammatical structure is: SELECT <Att 1 , Att 2 , …> FROM <table_name> In the encrypted database, the above statement is translated into SELECT <Att 1 EqualityCom Operator IS can find out the tuples with NULL or empty attribute value. NULL signifies that the value is missing or unknown, which is allowed to be consistent in both the plaintext database and the encrypted database. A query condition like 'Att IS NULL' is translated into EqualityCom(x, Att C , NULL C )=0 Similar translations may be easily adapted for another operator like NOT BETWEEN, NOT IN or IS NOT. e. LIKE operator. Operator LIKE works to carry out a wildcard-based fuzzy query. It requires that the query column to be stored as ASCII characters (e.g., char, varchar, text, etc.) or some related convertible data types. This column should follow specific encryption rules, as described in Section 7.3. SQL-Translator supports all four patterns (i.e., %, _, [] and [^]) as well as the escaping of wildcard or special literal characters. Its basic grammatical structure is shown as below: where pat is a search pattern string and esc is an escape character.
Before invoking LIKE translation module, a table-valued UDF (e.g., Split(@str, @delimiter), please see source code [75] for its SQL definition) is built on the cloud RDBMS. An encrypted string is divided by the delimiter and is returned in the form of a Table type. Besides, a temporary column Att_Match is added to the field Att, in order to save the final matching results of the encrypted string. The internal structure of pat is analyzed, and regular characters are escaped and encrypted simultaneously.
Taking the encrypted search pattern string 'αα%ββ%γγ' as an example, translating LIKE operator involves several steps: Firstly, we split pat by the wildcard character % into three parts (i.e., αα, ββ and γγ). Then a double-layer cursor is used in matching. The first cursor is in charge of traversing the encrypted column in the LIKE clause from top to bottom. It tends to determine whether the length of data items in the current line conforms to the minimal matching length of pat. The second cursor sequentially matches the beginning, the middle as well as the ending part of the current encrypted string from left to right. So in other words, it checks for the following three matching conditions in sequence: (i) The current encrypted string begins with αα; (ii) and the current encrypted string ends with γγ. Here, automatic filtration and matching are also included for trailing blanks. (iii) In addition to the beginning and the ending, the current encrypted string still contains the substring ββ. Moreover, AND or OR is utilized to connect the matching conditions in the above. Afterwards, we update the temporary column Att_Match and the SQL query condition according to the matching results of the current encrypted string.
The whole process of the above matching is done in ciphertext domain, but there are also some limitations in the translated set of the ciphertext SQL statements. For instance, encrypting the string by splitting into characters leaks the string length; using double-layer cursor and SQL loop statement reduces the query efficiency of wildcard characters.
f. Subquery. The subquery in SELECT statement mainly falls into the one with EXISTS and the one with a comparison operator. Standard Transact-SQL allows of 32 nesting levels or less.
SQL-Translator translates the nested query level by level. We take the double-level nested query 's 1 WHERE EXISTS (s 2 )' as an example, where s 1 and s 2 are two basic SELECT statements. The inner query s 2 is first translated and its query results are stored into a corresponding temporary intermediate table (e.g., #INTER_ TABLE2), then the outer query will be translated into s 1 WHERE EXISTS (SELECT * FROM #INTER_TABLE2) Similar translation may be easily adapted for the subquery with comparison operator. The main difference is that the query results of the inner query will be stored into the corresponding temporary intermediate variables. Other statements with more nesting levels can be translated iteratively.
Multiple query conditions constitute a composite condition by Boolean operators (e.g., AND, OR, etc.) among predicate expressions. As for two query conditions (i.e., con 1 and con 2 ), a composite condition like 'con 1 AND con 2 ' is translated into con 1 C ⋀ con 2 C A composite query condition like 'con 1 OR con 2 ' is translated into con 1 C ⋁ con 2 C Thus it can be seen that a composite condition is translated directly by concatenating each condition after translating individually. For the above operators (i.e., a to e), their translation rules are nearly identical when Att, Att 1 or Att 2 is a constant.
2) ORDER BY clause. The ascending or the descending ORDER BY clause sorts the tuples in query results by specified fields. An ORDER BY clause like 'ORDER BY Att 1  3) GROUP BY clause. Grouping statistics are implemented by the GROUP BY clause. It projects the tuples with the same attribute value into a group. For a GROUP BY clause like 'GROUP BY Att', we first execute a self-join query on the data column Att. Then the query results that satisfy WHERE conditions are stored in a temporary table #TEMPORARY_TABLE, resulting that the encrypted attribute values in the same group are completely equal. After that, the grouping is translated into an operation on the temporary table, that is, GROUP BY Att C 4) HAVING clause. The HAVING clause is used to further filter the groups resulting from the GROUP BY clause. In addition to the query conditions mentioned above, this clause supports some aggregate functions. In general, these functions can replace the table fields (e.g., Att, Att 1 or Att 2 ) to participate in the query. The translation rules of different aggregate functions are defined as follows: a. MIN function. The aggregate function MIN(·) returns the minimum attribute value that matches the query condition or that consists in a group. An aggregation operation like 'MIN(Att)' is translated into The aggregate function MAX(·) returns the maximum attribute value that matches the query condition or that consists in a group. An aggregation operation like 'MAX(Att)' is translated into MAX(Att C ) c. COUNT function. The aggregate function COUNT(·) returns the number of the tuples that match the query condition or that consist in a group. An aggregation operation like 'COUNT(Att)' is translated into COUNT(Att C ) d. SUM function. The aggregate function SUM(·) returns the sum of an attribute that matches the query condition or that consists in a group. For an aggregation operation like 'SUM(Att)', its translation 'E(SUM (Att))' is given by a secure two-party computation protocol. Now recall that SUM(E(Att))≤E(SUM(Att)) and SUM(E'(Att))≥E'(SUM(Att)), so we have that Dec(SUM(E(Att)), L)≤SUM(Att)≤Dec (SUM(E'(Att)), U'). See Protocol 1 for more details about the secure sum calculation protocol.

Output:
The client obtains SUM(Att). The server obtains E(SUM(Att)). Protocol steps: 1: The server requests SUM(E(Att)) and SUM(E'(Att)), and sends them to the client.

3:
If there is d=d', then the client obtains SUM(Att)=d and sends E(SUM(Att))=SUM(E(Att)) to the server. This is the termination of this protocol. Otherwise, continue to Step 4.

4:
The client tries to find out a parameter i (0≤i≤d'-d), s.t., SumEqualityCom(SUM(E(Att)), =0, which implies that SUM(Att)=d+i. Then the client sends E(d+i) to the server. This is the termination of this protocol.
Different from MIN, MAX and COUNT function, the nature of the OPEA algorithm determines that there are different approaches to invoke SUM function: If SUM function exists in the select list of SELECT statement, then it will be translated into 'SUM(Att C ), SUM(Att C _Extension)', where * C _Extension represents the ciphertext column encrypted by the extended OPEA. If SUM function exists in the query condition and we further assume that the other operand is a constant, then it will be translated directly by SumEqualityCom(·).
e. AVG function. The aggregate function AVG(·) returns the average of an attribute that matches the query condition or that consists in a group. An aggregation operation like 'AVG(Att)' is translated into E(SUM(Att))/COUNT(Att C ) where E(SUM(Att)) and COUNT(Att C ) have been defined above. The way to invoke is similar to SUM function.

Insert, Update and Delete
Next, we publish several translation rules for the insert, update and delete manipulations. 2) Update. An update manipulation is used to replace attribute values without changing all the other data in tuples. The basic grammatical structure of UPDATE statement is: UPDATE <table_name> SET <Att>=val In the encrypted database, the above statement is translated into UPDATE <table_name C > SET <Att C >=E(val) The FROM clause and the WHERE clause may also be used to restrict the scope of the tuples to be updated. And its update conditions are the same as the query conditions in SELECT.
3) Delete. A delete manipulation is used to delete some tuples from a relation. The basic grammatical structure of DELETE statement is: DELETE FROM <table_name> In the encrypted database, the above statement is translated into DELETE FROM <table_name C > The WHERE clause may also be used to restrict the scope of the tuples to be deleted. And its delete conditions are the same as the query conditions in SELECT.

Translation Rule of Relational Operation
Database relational operations can be divided into traditional operations and special operations. The former includes union, intersection, set difference, extended Cartesian product, etc., and the later includes selection, projection, join, etc. The following subsection expands on the translation rules of relational operations, which are used to translate the database relational operations over plaintexts into the corresponding operations over ciphertexts.

Traditional Relational Operation
Since relations in database are essentially sets, traditional set operations can be performed on them. To keep things simple, we denote the relation with n 1 attributes (resp. n 2 attributes) as P (resp. Q) in the plaintext database.
1) Union operator (  ). If n 1 =n 2 , then the union operator is implemented directly on their encrypted relations as below: where duplicative tuples are eliminated by EqualityCom(·).
2) Intersection operator (  ). If n 1 =n 2 , then the intersection operator is implemented directly on their encrypted relations as below: EqualityCom 3) Set difference operator (-). If n 1 =n 2 , then the set difference operator is implemented directly on their encrypted relations as below:

4) Extended Cartesian product operator (×).
An extended Cartesian product operator is implemented directly on their encrypted relations as below: where pq represents a new tuple that is constituted by encrypted tuples p and q orderly.

Special Relational Operation
Except the traditional set operations that are discussed above, there are some other special relational operations.

1) Selection operator (Δ).
In the selection operation, tuples are selected by given conditions to constitute a new relation. The translated selection operation is defined on an encrypted relation, that is, where Con is a translated query condition over ciphertexts. If the condition holds for the encrypted tuple p, then it returns true.

2) Projection operator (Π).
In the projection operation, several attributes are selected from an existing relation to constitute a new relation. The translated projection operation is defined on an encrypted relation, that is, where A is an encrypted attribute column or a set of encrypted attribute values, and p.A is the corresponding component in the encrypted tuple p.
3) Join operator (⋈). P and Q are connected together by a join operation to constitute a new data relation. There are many kinds of join operations, such as Equi-Join, θ Join and Natural Join. Taking θ Join as an example, the translated join operation is defined on encrypted relations, that is, where θ is a comparison operator (see the first part in Section 5.3.1). A and B are two encrypted attribute columns with the same semantics in the encrypted relation P C and Q C , respectively. To sum up, on the premise that no decryption is needed by SQL-Translator in T-DB, almost all kinds of data manipulations and relational operations on an encrypted database can be settled by translating SQL statements.

Functionality Limitation
We claim in this paper that T-DB is a nearly fully functional encrypted database system. What's more, all of its supported functionalities are obviously concentrated on common standard query types (the six kinds of clauses described in Section 5.3.1 are also regarded by Microsoft support document [36] as the most common SQL clauses). From the perspective of the syntax rules, the scope of the plaintext SQL statements that can be interpreted by SQL-Translator is only a subset of Transact-SQL standard syntax diagram. To this end, we analyze in this subsection the limitations in functionality of the T-DB translation module, which are mainly classified into the following several situations.
Besides the DML statement, there is Data Definition Language (DDL) and Data Control Language (DCL) in Transact-SQL. The former is utilized to create, alter or drop database objects and their structural constraints, while the latter is utilized to grant or modify permissions for users and roles. SQL-Translator supports theoretically the translation of DDL and DCL statements. The translation process is equivalent to the anonymization of database entities.
For example, suppose that we have a plaintext DDL statement to create a data table: CREATE TABLE tbl (Att int) Only a simple translation is needed to get the corresponding encrypted DDL statement: CREATE TABLE tbl C (Att C int) No complex translation is involved in similar statements (such as ALTER, DROP, GRANT, DENY, REVOKE, and so on) when running on the encrypted database. They are entirely independent of the SQL-oriented encryption algorithm, and could be naturally achieved by any conventional anonymization technique. In addition, some auxiliary language elements like DECLARE, FETCH, OPEN and CLOSE directly apply to the encrypted database without statement translation.
2) UDF-Restricted SQL statement. According to the translation rules described above, the equality comparison in the ciphertext domain has to invoke the two UDFs in Section 5.1. Both of them are performed as the computation or comparison on data records line by line. The flexibility of various equality comparisons in SQL statements is limited by the mathematical characteristics of our UDF, which cannot be settled just through the unmodified cloud database server.
Particularly, the SumEqualityCom function is more suitable for judgment on the order relation between an attribute column and a constant, instead of the order relation between two attribute columns. For example, a SQL clause like 'HAVING SUM(Att 1 )>SUM(Att 2 )' cannot be properly carried out before being decrypted by the database owner. Similarly, the DISTINCT keyword is designed to filter duplicative data records in the returned result set, so the EqualityCom function should be called many times. Nevertheless, in view of the rowbased access in the cloud RDBMS, some methods (e.g., cursor) are necessary to be adopted when this function is operated on the same column. Thus, a huge workload in querying is inevitably involved in the encrypted database. Other important situations also appear in the ORDER BY clause and the GROUP BY clause, as detailed in Section 5.3.1.
3) Encryption-Restricted SQL statement. It is quite hard for SQL-Translator to translate special SQL operators or keywords, that is, the following data manipulations are not contained in syntax rules due to encryption: a. Arithmetical expression. Since it is often composed of other operations beyond addition, the arithmetical expression cannot be interpreted into the form of UDF. Compared with the outsourced scheme using homomorphic encryption techniques, OPEA does not have any distinct advantage in the numerical calculation over ciphertexts.
At present, the diagram of Transact-SQL syntax is growing and being improved. Enhanced DML clauses and options are emerging. More extended functionalities in the future may be done on the basis of our existing works.
In summary, T-DB system has already transcended all previous solutions in query functionality. Objectively, although it does not cover all the functionalities in Transact-SQL, it is enough to provide the basic form of ciphertext manipulations (as with the basic SQL functionalities generally required by Microsoft technology forum [37]). Therefore, T-DB has strong practicability.
SQL-Translator can translate any DML statement that meets the syntax rules, whose details are published in the online supplementary material (download at [35]) and Section 5.6. Among them, a more intuitive syntax comparison can be made to further analyze the baseset or limitation for functionality.

DML Syntax Rules (for T-DB)
Our SQL-Translator can translate any SQL statement that meets the following DML syntax rules. Errors or unexpected query results will be returned when these syntax rules are broken.
The SQL statement that is submitted by a database user should also pass the semantic and permission check in standard Transact-SQL. The syntax rules are built using Transact-SQL syntax and arguments convention. Please see https://msdn.microsoft.com/en-us/library/ms 177563.aspx for more details.

SYSTEM PERFORMANCE
T-DB, whose performance is affected by various factors, can be deployed on any local or cloud RDBMS that supports UDF. This section provides some experimental results to evaluate T-DB from the following four aspects: (i) computational efficiency of OPEA; (ii) computational efficiency of SQL-Translator; (iii) functionality, precision, overhead and security in ciphertext manipulations; and (iv) the realistic database performance in Microsoft Windows Azure SQL Database (Microsoft SQL Azure for short).

Experimental Design
In order to avoid possible security risks from excessive user permissions, commercial cloud database products generally fail to support or open the programmable interface. In the latest version of SQL Azure, the user-defined function has been partially supported, but it still cannot deal with the storage or relation of encrypted data, which limits the application of certain outsourced encrypted database solutions.
In fact, there are several practical restrictions on the commercial SQL Azure platform, such as cloud migration, data type, data size, storage format, manipulation type, storage procedure, query execution time, etc. For the secure outsourcing schemes that rely on CLR components (e.g., CryptDB [22]), after its encryption and before its decryption, there exists a problem about the code conversion between character stream and byte stream. This problem is waiting for future systematic adjustment.
The execution efficiency of ciphertext SQL statements on the cloud is related with the cloud resources and server configuration, which is not the main concern of this paper. Hence, several simulation experiments are firstly given to make comprehensive evaluations about the overall performance of T-DB.
Experiments instantiated the database platform with Microsoft SQL Server 2012 and Transact-SQL language. We used two machines with 3.6GHz Intel Core i7 processor, 20GB memory and Windows 7 operating system to run the cloud client and the cloud server. OPEA and SQL-Translator modules were developed in the Microsoft Visual Studio 2015 Professional with C++11 standard and ran on the side of database owner. Cryptographic algorithms and the numerical calculation with arbitrary precision were implemented using the static library OPENSSL 1.0.1s [38] and boost 1.60.0 [39]. The T-DB implementation consists of approximately 2000 lines of source codes, mostly in the code for the encryption, decryption and interpreter module. The cloud server requires only approximately 30 lines of SQL codes to declare the UDFs that are used in executing ciphertext query manipulations.
The test database comes from TPC-H 2.17.1 [40], which is a decision support benchmark defined by TPC. It is a normalized and open database with controllable data size. TPC-H can simulate real-world business data. Its database diagram is presented in Figure 6. We set the TPC-H scale parameter to 10 (SF=10), then about 10GB relational tables and data items are generated. There are in total 86586082 records in eight tables. The number of data records in each data table is listed in Table 1. TPC-H can well reflect the ability of a system to execute queries. It has complex data structure and various query types, so it is suitable for testing the effectiveness in executing SQL. TPC-H also makes the verification of OPEA and SQL-Translator comprehensive and objective. Below is a series of comparison tests on the T-DB functionality, which is the most valuable contribution. Their major target is to verify the practical usefulness of certain queries that are developed from the comparability of OPEA ciphertext. Here we introduce several selective SQL test cases (see Figure 7), including query (Q1 to Q5), insert (I6), update (U7) and delete (D8) statements. They cover nearly all standard query types in DML to demonstrate the improvement of our T-DB system on the query functionality of encrypted databases. The query conditions involved in Q1 to Q5 would be obviously impacted by the efficiency issues of core ciphers during their executions, which is particularly problematic in this environment. I6 to D8 are chosen to validate effective dynamic updates on ciphertexts. Take the complicated query Q4 for example: it tests comparison operators, GROUP BY clause and HAVING clause over multiple columns in an encrypted database simultaneously. This kind of query cannot be easily implemented with traditional cipher tools. Besides, these experiments could be extended to more test cases, and the experimental data in the paper is measured by taking the average time over at least ten iterations.

Control Group
The experimental environment was built based on the system architecture in Section 3 to confirm the above conclusions. It strictly follows the procedures of secure database outsourcing. The cloud RDBMS server takes charge of managing encrypted databases and executing all queries received. Other works in the stage of pre-processing or post-processing are completed by the database owner.
The simulation took CryptDB [22] with default parameter setting (see Table 2) as the control group. Secret keys with the same length were selected to encrypt all columns. In CryptDB, data encryption and data decryption are performed by a trusted third-party proxy. During its pre-processing, some related Initial Vectors (IVs) are randomly generated and an AVL-tree is balanced by the range of plaintext values. The experimental parameters are listed in Table 2 where SEARCH algorithm [41] only leaks the number of search keywords, and the rate of false positives in searching is set to 1/2 32 . Similarly, the OPEA algorithm in T-DB chose T+1 8-bit random numbers as its encryption keys. In other words, the total key length has reached 8(T+1) bits, where T is in the magnitude of 10 6 for test data. The encryption costs of OPEA have nothing to do with the partition lengths, and only the storage efficiency of ciphertexts would make an effect on system performance, which is not primary measurement for T-DB. Other security parameters (e.g., symmetric keys or random salt values, etc.) are strong enough, so the comparison experiments that run against CryptDB may be considered fair in practice.
We conduct some theoretical comparisons with CryptDB (Table 3 and Table 4). The overwhelming advantage of T-DB is that it can be straightforwardly deployed without disturbing the CSP or database users. CryptDB has different levels of security, and is more secure than T-DB in some levels. However, after the outer onion decryptions of CryptDB are executed on the CSP for processing queries, it is also clear that T-DB will be at least as secure as CryptDB. Regarding the query efficiency and query precision on the database side, T-DB significantly outperforms CryptDB. And in terms of functionality, T-DB supports almost all types of efficient data manipulations (e.g., data query or data update) on encrypted databases. CryptDB in a fuzzy query only supports the full-word keyword search, excluding any form of regular expressions or the wildcard-based fuzzy queries.  Furthermore, in CryptDB a single plaintext column will always be transformed into multiple ciphertext columns to support queries on ciphertexts; in contrast, our T-DB produces one ciphertext column from each plaintext column, thereby saving much storage space. Beyond that, since incompatible encryptions (including a deterministic encryption AES-CMC, a non-deterministic encryption AES-CBC, an order preserving encryption OPE-AVL [27], a homomorphic encryption Paillier, an Equi-Join algorithm JOIN-ADJ and a keyword search algorithm SEARCH [41]) are adopted by CryptDB, the aggregation query II cannot apply to the HAVING clause. For certain queries where both summation and comparison are operated on the same column, the data items should be rewritten by homomorphic encryption and reencrypted by trusted proxy, which leads to a huge computational cost.

Evaluation for OPEA
A primary problem in the efficiency evaluation of OPEA is the generation time of private boundaries. In view of the fact that the storage space of the boundaries is about twice that of the plaintext domain, the total time needed to generate boundaries will be longer as the T value increases.
When evaluating the performance of OPEA, we first encrypted T consecutive positive integers, and measured the average time to generate boundaries. Related experimental results and curves are given in Figure 8. The boundary generation time of OPEA gradually increases in proportion to the T value, while the unit time for the simplified OPEA to generate private boundaries is stable within 0.17μs when T is located from 1 to 100,000. For T-DB system, this is a kind of one-off overhead. Private partition boundaries are stored locally and not required to be exchanged in database outsourcing or query processing. That is to say, they are reused many times after being generated. Excessive computational overhead can be handled with the help of a private cloud, while the SBoundaryGen function (see Algorithm 4 for more details) is practically usable. After partition boundaries are generated, the encryption sub-algorithm of OPEA selects a random number from the corresponding partition and outputs it as a ciphertext, which can be finished in constant time. The decryption sub-algorithm searches and returns the index of the partition where the ciphertext is located, so an approximate logarithmic complexity can be achieved with the well-known binary search method.
Next, we separately performed encryption and decryption operations on the column P_SIZE of the table Part, and measured the average time and encryption frequency for each data item ( Table 5). The encryption time of OPEA is about 1.74μs, second only to the symmetric cipher Blowfish. The decryption time of OPEA is the fastest (about 0.05μs), which indicates that the local computational cost is extremely low at the database owner side. The average comparison time at the cloud server side is nearly negligible (only about 0.03μs). Moreover, no additional network communication overhead is incurred as OPEA is non-interactive. The network traffic is just related with the size of the query request as well as the size of its result set. Table 5: Comparison on time-space overhead of cipher algorithms. The measured average operation time in the third column includes the average time used in encryption/decryption, the conversion of storage type and the balance of AVL-tree (for OPE-AVL) on SQL Server. The encryption frequency in the last column refers to the total number of times encryption is required to make sure that the ciphertext column can support Equality Query, Range Query, Aggregation Query and Fuzzy Query simultaneously. Here, the outermost onion encryption is not taken into consideration. In SEARCH, we replace the data item with a string before encryption/decryption or matching test. Also, the original data column is encrypted only once by T-DB, whereas each data column is encrypted 4 times by CryptDB, i.e., one column per allowable onion structure. Thus without consideration of the oversize ciphertexts, the storage space of the encrypted database in CryptDB is about 4 times the size of that in T-DB (i.e., the latter is almost of the size of the plaintext database).

Evaluation for SQL-Translator
The test cases in Figure 7 are translated by SQL-Translator into ciphertext SQL statements. We leave their translated results in the online material [35] and Figure 9. They can be submitted directly to the CSP to perform the same manipulation. The third column in Table 6 is the translation time. Evaluation results show that, under normal circumstances, the translation of DML statements can be done in microseconds.  The next translation experiments were studied for some nested test cases (Figure 10a) and unit test cases (Figure 10b). The former tests the average translation time of the nested queries in SELECT statement. It grows linearly with the increase of nesting levels. As for the latter, the test object of unit testing is the minimal query unit in a SELECT statement that contains several keywords or operators. Due to the complex translation rules of fuzzy queries, SQL-Translator spent much more time (about 0.19ms) to translate LIKE operator than other cases, but its overhead is still considerably low. To help us to further understand the translation principle of the subquery, we consider the following basic nested query statement: where tbl 1 and tbl 2 are table names, Att 1 , Att 2 and Att 3 are column names, and num is a constant. The above plaintext statement will be translated by SQL-Translator into the following set of ciphertext query statements: These statements would actually run directly over encrypted databases to support nested queries on ciphertexts, where @inter_var2 is a corresponding temporary intermediate variable.

Evaluation for Ciphertext SQL
In T-DB, a data manipulation request from the database user will be sent to a cloud RDBMS after being translated by the database owner. The T-DB workload of query processing is transferred to the cloud as much as possible in order to maximize the query precision in the encrypted database. Since there is no false positive or false negative in the query results returned, the overhead of post-processing (to eliminate false positives) is minimized.
Since CryptDB does not follow DBaaS and cannot be directly deployed on SQL Azure, the subsequent comparisons were conducted in the local simulation environment with a simulating CSP works as required by CryptDB. The query processing time of CryptDB in the encrypted database consists of two parts, i.e., the time for onion decryption and column updates before query, and the time for execution of the ciphertext SQL statement. Overall, T-DB has better efficiency in query and decryption than CryptDB.
As for Q4, the ciphertext manipulation in CryptDB involves a range query and an aggregation query with additive homomorphism. Since the comparison and summation cannot be operated on the same column, several false positives were thus introduced. The overhead of a post-processing stage includes the time for pre-processing and decryption of OPE-AVL, the time for decryption of ciphertext addition as well as the time for elimination of false positives. The encrypted column PS_AVAILQTY was first decrypted by the database proxy, then its order relation was judged. This process took about 5840.245ms, i.e., 0.171 queries per second.
As for Q5, the ciphertext manipulation in CryptDB involves a range query and a keyword matching query. Since the keyword position cannot be matched by the wildcard characters in SEARCH algorithm, a multitude of false positives were introduced. The overhead of the post-processing stage includes the time used in decryption of AES-CBC and SEARCH, and the time used in elimination of false positives. This process took about 13011.340ms, i.e., 0.077 queries per second.
Regarding the post-processing efficiency at the database owner side as well as the query precision and the time overhead of the CSP, Figures 11a to 11c indicate that our T-DB has much higher query precision and far lower time overhead than CryptDB.
The specific analysis is shown as follows: In Figure 11a, we investigate the average queries per second on the database owner, and then compare with a CryptDB proxy running on the same encrypted database. Without considering the communication overhead and query overhead of the cloud RDBMS server, it can be observed from this figure that T-DB decrypts the query results efficiently in the post-processing stage. Our throughput is at least 36.04 times higher than CryptDB, and is even up to 10 4 times faster in some particular test cases.
In terms of the query precision of the CSP, a 100% recall rate is acquired in both T-DB and CryptDB, while their precision rate is quite different. A careful observation of Figure 11b indicates clearly that T-DB preserves the precision rate as a plaintext database in all of the five test cases, but the average precision of CryptDB in Q4 and Q5 (false positives) is 43% and 50%, respectively. This figure also reveals that the homomorphic encryption technique is not enough to achieve accurate ciphertext manipulations, especially in the range query and the fuzzy query. Take Q4 with Paillier homomorphic algorithm as an example, CryptDB cannot perform any ciphertext comparison before its decryption, so the false positives coming from the CSP are inevitable.  Figure 11c compares the query processing time of the CSP. It is noted that T-DB can process the ciphertext queries more efficiently than CryptDB except the fuzzy query Q5. However, CryptDB may return a great number of erroneous results. Although the CSP takes less time to execute Q5, excessive post-processing overhead is transferred to the database owner. Besides, according to Table 5 and the comparison results of Q4 in this figure, we point out that T-DB consumes a shorter time than CryptDB either in the client-side encryption/decryption processing or in the server-side query processing. For this reason, it can be seen that the impact of the OPEA algorithm on the overall query efficiency is outweighed by the homomorphic encryption algorithm (e.g., Paillier).
In conclusion, compared with CryptDB, our T-DB has the following advantages: 1) T-DB can be straightforwardly deployed without disturbing the CSP or the database users.
2) T-DB can handle almost all kinds of basic DML statements, while CryptDB cannot.
3) The CSP does not participate in the decryption of outsourced data, thereby avoiding the leakage of secret keys. 4) Only a single cipher algorithm is adopted in T-DB. Thus the storage overhead of encrypted databases is lower. 5) The average query efficiency of the CSP is higher under the same query precision. 6) Some wildcard-based pattern matching is supported in fuzzy queries, which perfects its query functionality. 7) There is no need for database owners to eliminate the false positives. Thus the local amount of communication and computation is smaller.
8) If an aggregation query and a range query are operated on the same column, then the query precision is higher and the rate of false positives is lower in T-DB.
The source code and other test cases related to T-DB may be downloaded at [35]. Please see Section 7.6 for more detailed illustrations.

Evaluation for SQL Azure
To make a better evaluation of the applicability of T-DB on realistic cloud computing platforms, we implemented this system in SQL Azure environment. The client has exactly the same configuration as that in Section 6.1. The relational SQL database service with the level of Standard S3 was qualified through a free Azure account in China [42], and the server has 100 Database Transaction Units (DTUs). A DTU is a blended measure of CPU, memory and data I/O rate. The above two machines were connected over a shared 300Mbps wireless network. The client configuration ensures that neither the database users nor the database owner is the bottleneck in any case.
A third-party tool called SQLAzureMW v4x [43] was applied to help the database owner to migrate her existing databases to SQL Azure engine (the same test database and cases are adopted here, and please refer to previous sections for specific data size, data source and experimental parameters). It can solve a series of possible restrictions on compatibility during the migration (e.g., the lack of the clustered index, etc.). In the real experiment mentioned below, all of the data items, the UDF definitions and the database architecture in the encrypted TPC-H are stored by SQL Azure, and a fully managed database service is also provided. Beyond that, there appears to be no change on the relational structure of outsourced databases or the access mode of database users.
The total execution time of data manipulations on the encrypted database includes three parts, i.e., translation time of SQL statements, execution time of ciphertext SQL, and decryption time of the final query results. Generally, the query execution time of an encrypted database is greater than that of a plaintext database (see Table 6). Further analyses reveal that the overall performance of T-DB is severely restricted by the execution efficiency of ciphertext statements. The most frequent queries, Q1 to Q2, can be processed in seconds. The time overhead of the unusual queries, Q3 to Q5, is much greater. This performance difference is mainly due to the elastic computing mechanism on the cloud.
The database user is allowed to rent cloud resources as flexible as possible, depending on actual business requirements and usage conditions. Afterwards a dynamic resource scheduling algorithm is utilized by the CSP to achieve load balance. A large number of query requests that come from the database owner are allocated on demand to specific cloud servers. No artificial factor is involved when the queries are running on SQL Azure, but their execution time (see Table 6) might be influenced by the tuning strategies of SQL execution plan. Some queries, for instance, the aggregation operations in Q3, spend a longer amount of time in both plaintext database and encrypted database, which is somewhat different as that in the local simulation experiment. Therefore, it is simply too difficult to ascertain the main reason for causing the current statistics. Table 6: Comparison on execution time of data manipulations between plaintext database and encrypted database in a realistic cloud. (n) in the rightmost column indicates that there are n components in the returned record. Statement execution time in the fourth column represents the total response time of SQL Azure, i.e., the average time elapsed between the time when a query request is submitted by the database owner and the time when its query results are received (end-to-end delay included). Additionally, the tendency of the total response time in the encrypted database under different performance levels, i.e., different number of DTUs, is shown as Figure 12. We just take Q1 and Q2 as representatives. The total response time (i.e., the query efficiency of T-DB) in SQL Azure gradually decreases with the increase of the number of DTUs.  The T-DB applicability in a realistic cloud environment has already been well validated. The migration to SQL Azure is available for T-DB.

DISCUSSION
To begin with, this section discusses the system security of T-DB, the noise growth in OPEA as well as the data type and data length in SQL-Translator. Here the influence of different encryption rules on the encrypted fields is analyzed. We also summarize the related works and point out the possible direction for future research.

System Security
The security under two threat models is analyzed on the system level. T-DB aims to provide the following security guarantees: 1) Security guarantee against Threat 1. The database owner uses OPEA and a deterministic encryption algorithm to encrypt all sensitive outsourced data and names of tables or columns. Decryption keys are stored locally and isolated from the cloud, so it is quite difficult for the attacker to compromise any outsourced encrypted data by a ciphertext-only attack. Besides, T-DB does not hide sensitive side information, such as the overall table structure, the number of rows or columns, the field type, and the data size.
Some strict access control policies can be enforced by the database owner. Tables or columns with different security levels are encrypted with different keys to minimize the correlation leakage. Meanwhile, we regulate that an authorized user is allowed to log into the system by sharing a password. The database owner takes the access permissions of the currently logged-in user to lookup his encryption keys. Thus, the accessed private data can only be encrypted or decrypted correctly; the submitted SQL can only be translated properly, if that user is requesting his authorized contents. Otherwise, these manipulations will be poorly executed.
Executing ciphertext queries needs to encrypt the query conditions with different secret keys according to the specified request. The data relations revealed by executing SQL statements depend on the scope of query objects. For instance, if encryption granularity is an entire column, then the x selected by SQL-Translator can only be used to run several specific data queries (i.e., one or more of these queries that are most commonly in equality, range, aggregation and fuzzy) on the current column. That is to say, the actual contents of data items and sensitive information of other columns will not be leaked.
The attacker at the cloud cannot translate the plaintext SQL. It is even harder for him to request any data manipulations on the CSP, so the visits to confidential data are minimized at the cloud.
However, since basic grammatical structure is preserved in the process of statement translation, a malicious attacker could still make a guess based on translated ciphertext SQL statements and steal related information about the private data, mainly including the table structure, entity relations, data item distributions, etc. Specifically, if the cloud receives an Equi-Join query request on two encrypted fields, i.e., Att 1 C and Att 2 C , then the attacker can confirm that the data in these two columns are encrypted with the same key, and they have similar semantics as well as precise equivalence. For another example, the attacker can infer a general distribution of current attribute values according to the number of query results returned from the cloud server. What's more, by simply combining and concating with other ciphertext SQL clauses, the query scope will be gradually narrowed in order to detail the distribution of the encrypted database. But indeed the above attack strategies provide few helps for analyzing boundaries of ciphertext partitions.
2) Security guarantee against Threat 2. Firstly, if a malicious database user colludes with the CSP, then a chosen-plaintext attack will be launched. Ciphertext queries can be performed adaptively by a cloud attacker in the database user's authorized access domain. Some relationships between plaintexts and ciphertexts are established from the final query results. Other private data encrypted with the same key in legitimate cloud servers may thus suffer high privacy risks. For instance, in the case that all of the secret keys and private boundaries are unknown, the malicious cloud attacker can construct an SQL statement that contains specified query conditions, consequently, the input and output of SQL-Translator can be controlled to request the encryption of sequential plaintext values in the form of a SQL injection attack. At last, in accordance with the ideas of order-preservation, additivity and clustering, a general interval and an approximate distribution of ciphertext partitions are analyzed by the attacker. Another fresh encrypted value will be classified into the closest partition with a high probability.
Collusion attack is one of the common security issues in DBaaS framework. In practical terms, every time we execute a data manipulation in an outsourced encrypted database, a certain number of correspondences between plaintexts and ciphertexts are established. Hence, any cipher algorithm with order-preservation cannot provide security guarantee under this attack, that is, collusion risk is inevitable in DBaaS, as T-DB does.
Secondly, in order to minimize the data leakage, some strategies about fine-grained access control and key management (e.g., [44,45], etc.) have to be designed and implemented on the database owner. At any time, T-DB leaks at most the query requests or query results of the currently logged-in cloud users to the collusion attacker, while the private data not accessed would remain confidential since different data are encrypted with different secret keys. Considering that if the collusion attacker has limited access permission, the loss of sensitive information is still under control.
Moreover, the second threat model also includes some active attacks. A malicious database user who is involved in the collusion can insert or update the cloud data if he is granted the corresponding permissions, which may indirectly compromise secrecy. To prevent this kind of attack, we have to introduce appropriate mechanisms for integrity verification and automated data recovery.
In conclusion, our T-DB is a practical secure outsourcing system with the fundamental security on the premise of supporting almost fully functional data manipulations over encrypted databases.

Noise Growth
Essentially, a random noise is added into ciphertexts while encrypting in the OPEA algorithm. The selection of noise should meet some special conditions to ensure cryptographic security as well as order-preservation and additivity. Though the regular decryption function in OPEA can return the only and right plaintext value, serious noise growth always appears after additive operations. Since direct decrypting encrypted sum causes errors if the noise growth is greater than a certain threshold, this subsection analyzes the influence of noise growth that is caused by summation in the ciphertext domain on the correctness of decryption.
In short, the summation of ciphertexts in probabilistic OPEA algorithm may add noise to decryption and in the worst case, the decryption may fail. From the research in Section 4.6, we explain this phenomenon in three aspects.
1) The probability of the deviation of ciphertext partition. The random noise grows after several ciphertexts are added together, and the probability of the deviation of ciphertext partition under various summation frequencies is different. Take the summation between two numbers as an example, for any positive integers a, b, c=a+b (a, b, c∈X), let us set d=Dec(E(a)+E(b), L) and d'=Dec(E'(a)+E'(b), U').
Firstly ] ' a b P d c P d c R R = + = − = ≥ − + In summary, whether the OPEA algorithm is used alone or the extended OPEA algorithm is used alone, the probability of the deviation of ciphertext partition caused by summation is at least P[d=c -1] or P [d'=c+1]. It approaches one with the increase of R a and R b . The above discussion indicates that summation increases the noise, and it is easy to see that multiplication also does so.
As for the next generalized case that value=SUM(ς), |ς|≥2, we set d=Dec(SUM(E(ς)), L) and d'=Dec(SUM (E'(ς)), U'). From the theorems in Section 4.3 and Section 4.4, the upper probability that the encrypted sum is decrypted correctly is shown as follows: And the probability of the deviation of ciphertext partition caused by summation is at least which approaches one with the increase of R t (t∈ς).
2) Client-side overhead in secure sum calculation protocol.
With the help of secure sum calculation protocol, a judgment about the encrypted sum is made by the decrypted results from OPEA and its extended version. Since d∈{value-1, value} and d'∈{value, value+1}, the probability that Step 3 in Protocol 1 outputs directly the correct plaintext sum by a one-time comparison is shown as follows: In other cases, the correct SUM(ς) is located between d and d'. If d'-d=2 at this time, then value=d+1=d'-1, otherwise the client should invoke the SumEqualityCom(·) function to get it. It is obvious that only a finite number of comparison operations are needed, so the computation complexity to eliminate decryption error is constant.
3) Generalized method to control noise growth. Secure sum calculation protocol solves the problem about the decryption error which is caused by noise growth. As we note in the above derivation with further analysis of Theorem 6 and Theorem 7, the lower and upper limit of encrypted sum is on the premise that its system keys satisfy that σ≥(value+|ς|)·R T -R 1 . This means that for a fixed σ, both the summation frequency |ς| and the plaintext sum value are limited, otherwise there will be a wrong decryption. In other words, we demonstrate that the noise is controllable and its growth can be effectively controlled by simply adjusting σ .

Data Type and Data Length
In general, the OPEA encryption function takes integers as input, but it also provides some extended encryption interfaces for float type or string type. SQL-Translator can easily translate data of arbitrary type and arbitrary length. Descriptions of storage format are given below.
For a float data, a simple approach is to divide a ciphertext domain by the least precision of plaintext domain. Lower and upper boundaries are recomputed on the basis of partition distribution. For a character data (e.g., a plaintext string 'abcd'), it is split into multiple characters using standard delimiters (e.g. a semicolon) in CryptDB [22], and then each of the characters is encrypted by SEARCH algorithm [41]. In other words, the encrypted string is denoted as E SEARCH (a); E SEARCH (b); E SEARCH (c); E SEARCH (d) In T-DB, the database owner transforms it into numerical data (e.g., English characters should be transformed into ASCII code; Chinese characters should be transformed into Unicode) before encryption, following three encryption rules: 1) Field in wildcard-based fuzzy query. For the fields in wildcard-based fuzzy queries, the plaintext string is transformed into ASCII code and then encrypted in sequence, so the encrypted string can be denoted as E OPEA ((int)a); E OPEA ((int)b); E OPEA ((int)c); E OPEA ((int)d); π where the minimum matching unit is assumed as a character. π is the number of trailing blanks in the plaintext string, which is utilized to match a search pattern.
2) Field in equality, range and aggregation query. For the fields in the equality, range and aggregation queries, the whole plaintext string can be transformed into numerical data and then encrypted, so the encrypted string can be denoted as Here, each plaintext character is concatenated after being transformed into a 3-digit decimal ASCII code, where || indicates a string concatenation. The ciphertext expansion in this rule will be limited when the plaintext is small. The order-preservation and the additivity are preserved for the field as well.
3) Field in equality, range and aggregation query. For the fields in the equality, range and aggregation queries, the plaintext string can also be transformed by minimum matching unit into ASCII code and then encrypted in sequence. Besides, encrypted characters are concatenated together after being padded to a fixed length, so the encrypted string can be denoted as Specifically speaking, we assume that each ASCII character is encrypted to a N-digit integer. And a zero padding is utilized in the most left of the insufficient characters. The ciphertext expansion in this rule will be limited when the plaintext is large. Only the order-preservation is preserved for the field, but not the additivity.
The third rule is also suitable for encrypting long integers. In order to avoid the run out of bounds exception in ciphertext partition that caused by overlarge plaintext domain, a long integer can be treated as a string. It is divided into multiple segments, encrypted individually, and concatenated orderly. Other data types might be implemented by appropriate type conversion and rule extension.
The data storage type in encrypted databases is bigint and varchar. No encoding is adopted here in any form, which aims at preserving the data manipulability. When a database owner decrypts the OPEA ciphertext, she first splits the encrypted string using the standard delimiter or the fixed length. After being decrypted individually, the segments are concatenated together to get the original plaintext.
In addition, similar to traditional plaintext databases, outsourced encrypted databases also face the issue on incompatible table size. Taking SQL Server as an example, the cloud regulates that there are at most 1024 columns in a table and at most 8060 bytes in a row. Since the length of ciphertexts is influenced by the T value, T-DB breaks the above restriction faster than plaintext databases. The solution lies in that a plaintext column is split into multiple columns and stored into a new table. The data item whose length is not enough in splitting is padded with zero. The database owner then encrypts them separately, which could also improve somewhat the outsourcing security.

Related Work
In 2002, Hacigümüs et al. [5] first presented the concept of DBaaS. From then on, under external and internal attacks, the issues on the security and privacy of outsourced data were identified as a vital research direction. A number of symmetric and asymmetric encryption techniques have been widely used in protecting the confidentiality and integrity of outsourced databases [46,47,48], but most of them end in the impracticability of data manipulations over ciphertexts. Current representative researches mainly include two categories, i.e., single data manipulation schemes and multiple data manipulation schemes.

Single Data Manipulation
From the perspective of supported query functionalities, the existing studies about single data manipulation in outsourced encrypted databases can be generally classified into four categories, which are shown as follows: 1) Equality query.
In the earliest research about security protection of cloud databases [5], an outsourced database is encrypted by a deterministic encryption scheme (e.g., RSA [49]), which supports accurate equality comparison. However, the deterministic encryption technique directly leaks the equality pattern between data duplicates. Similarly, only equality testing is available in the cryptosystem [50] that was studied by Lu and Tsudik, while JOIN operator and comparison operators are not naturally supported. Besides, it might reveal access structure or sensitive attribute values by brute force attacks if the CSP colludes with the attacker in this scheme.
More discussions are focused on executing Equi-Join query over encrypted data. In 2008, Li and Chen proposed a distributed privacypreserving Equi-Join protocol [51]. One recent work [10] utilizes the bilinear pairing during query processing, causing high computational overhead. Related equality queries on ciphertexts [8,9] also inevitably leak some information about access pattern to the CSP, which causes a series of security attacks [52,53].
2) Range query. The original form of range query in encrypted databases is the TOP-k query [54,55]. Vaidya et al. [55] developed privacy-preserving kanonymity policies in which the data are vertically partitioned instead of being encrypted, but they cannot be extended to encrypted databases. After that, based on the research in [50], a solution proposed by Wang et al. [13] prevents the brute force attack from the point of view of the cloud database. A trusted proxy is explored to encrypt data tuples and to realize basic Equality Query, Range Query, INSERT, UPDATE or DELETE, but it weakens the protection of cloud users' private data items. Tian et al. [56] then adopted a set of non-colluding Database Service Providers (DSPs) according to secret sharing strategies. A range query request is transformed by the Data Requester (DR) into encrypted form. They also constructed an ordered privacy preserving index to accelerate query speed and raise query precision. This kind of distributed database outsourcing protocol relies on the assumption of non-collusion and always has large overhead in terms of computation, communication and storage. Different from the above distributed secure multiparty computation, the first order preserving encoding function proposed by Agrawal et al. [11] in 2004 can be directly applied into the encrypted database. It performs various kinds of range queries (e.g., ORDER BY clause, GROUP BY clause, comparison operators) and related statistical aggregate functions (e.g., COUNT, MIN, MAX). mOPE scheme [12] also supports Range Query, INSERT, UPDATE and DELETE, but it has low efficiency in the order comparison. As for another order preserving encryption algorithm [57] with random noise, CREATE, INSERT and some basic SELECT statements are translated by the trusted proxy into a privacy-preserving form. The security is compromised because its secret parameters are reused many times, and because of its quasi-linear encryption structure. Besides, Reddy and Ramachandram designed a Randomized Order Preserving Encryption scheme (called ROPE [28]). Although ROPE further improves the insert, delete, update and query function in terms of equality and range in mOPE, the frequent communication with proxy reduces its query efficiency. MV-OPES [58,59] is another randomized encryption scheme that maps a plaintext value into different multiple ciphertext values to prevent statistical attacks. This method allows some parts of privacy-preserving relational operations to be executed over an encrypted database, including selection, sorting and the projection based on inequality. But some operations like join, aggregation, grouping, set difference and set union need to eliminate false positives after decrypting the data, which brings additional workload for the client.
3) Aggregation query. Researchers usually employ homomorphic encryption techniques to solve the problem on aggregation queries or algebraic operations in encrypted databases. Although the ciphertexts generated by fully homomorphic encryption [20] can be involved directly in arbitrary computation without decrypting them, this technique is impracticable and prohibitively expensive in computation. As a compromise, Partially Homomorphic Encryption (PHE) has been widely studied. Some examples include Paillier [60] (supports additive aggregation operation), RSA [49] (supports multiplicative aggregation operation), PEKS [61] (supports keyword search on encrypted strings), etc. Such a PHE scheme is just designed to process one particular type of operation, that is, a cryptosystem that supports additive aggregation does not apply to any ciphertext comparison. We fill the gap in this paper by proposing a cipher tool that preserves the order for ciphertexts after additive operations. Then range queries and aggregation queries can be achieved simultaneously in the encrypted database.
The distance-based search (e.g., kNN algorithm, similarity retrieval, etc.) is another important aggregation query. In 2009, Wong et al. [62] presented an asymmetric scalar-product-preserving encryption (ASPE) for kNN queries. As shown in [63], this scheme is not secure and is vulnerable to chosen-plaintext attacks. Recently, a secure kNN query processing technique [14] based on mOPE [12] and a secure kNN protocol [15] which is suitable for mobile devices have appeared continuously. The security about data confidentiality, user's query requests and data access patterns is well guaranteed. Besides, a modified privacy homomorphism was proposed by Hu et al. [16] to protect data privacy and query privacy. The scheme maps a set of data operations (i.e., addition, subtraction, multiplication and division) in the plaintext domain to another set of operations in the ciphertext domain. Recoding and scrambling functions are also used to calculate the distance of ciphertexts, and to ensure their monotonicity and security. However, this privacy homomorphism is only available in distancebased queries with R-tree index and it has high cost in computation and communication.
In the outsourced encrypted database, fuzzy query usually includes keyword search and similarity retrieval, which are used to request some more complex queries. In special cases, the keyword search can be achieved by some extensions of relational operations in the database. Until now, lots of studies on single-keyword search [64] and multi-keyword search [17,65] have been proposed for ciphertexts. But they often suffer from potential information leakage and collusion attacks. Furthermore, they consume large amounts of computing resources. TEES (Traffic and Energy saving Encrypted Search) [18] is an efficient similarity retrieval algorithm at the cloud. It improves the system security and saves the energy, meanwhile the network traffics during the information retrieval are also significantly reduced. The TF-IDF value (Term Frequency-Inverse Document Frequency) is mapped to different ciphertexts with a certain probability. Thus, the statistical information of the term frequency is approximately a uniform distribution. As for the searchable encryption with multiple data owners [66], its key distribution and management are becoming more and more complicated with the rapid increasing of users and the explosive growth of data. Fuzzy matching search has a tolerance of possible keyword misspelling, minor typos and format inconsistencies. The ciphertext search in [67] constructed a fuzzy keyword set by measuring keyword similarity semantics. Bing Wang et al. [68] presented a multi-keyword fuzzy query scheme for cloud outsourced data by exploiting locality-sensitive hashing technique.
Nevertheless, if the above searchable encryption techniques are applied directly to keyword-based queries in the encrypted database, the limitation is that wildcard characters cannot be matched and regular expressions cannot be parsed. Taking CryptDB [22] as an example, its keyword search algorithm SEARCH [41] is only available in the full-word search. A search pattern string like '%αβγ%' can be correctly queried (where αβγ is a search keyword), while other forms of wildcard-based queries are ignored completely. So CryptDB does not support fuzzy queries in the genuine sense. To overcome this limitation, Dongsheng Wang et al. [19] proposed GPSE (Generalized Patternmatching String-search on Encrypted data) for cloud encrypted data. GPSE allows the database users to request a query using generalized wildcard-based pattern strings (similar to the LIKE mode in SQL query). Its security has been demonstrated under known-plaintext model and high search accuracy has been achieved.

Multiple Data Manipulation
At present, several integrated solutions for outsourced encrypted databases have been proposed. They attempt to provide multiple data manipulations in one-time.
Hakan Hacigümüs et al. [25] presented a query framework in 2002 to protect the data security in DBaaS for the first time. OPE and probabilistic encryption are adopted to support basic relational operations in equality, range and aggregation queries. It is fairly good in efficiency but relatively poor in precision. A relevant research [59] realized the same functionality simply by OPE, but a multitude of false positives still exist in its query results. The latest SDB system [26,69] is a series of secure multiparty computation protocols based on asymmetric secret sharing. Data interoperability is achieved in a wide range of queries by the interaction between a single DSP and the client. Even so, since its data model is always column-based, efficient comparison is hardly carried out on the same data column, that is, some statistical functions like MIN, MAX and TOP-k have not been fully performed. Furthermore, this system cannot encrypt character data, so fuzzy search is not supported and the PEKS cryptosystem [61] needs to be introduced.
In 2011, the best-known solution called CryptDB [22] was put forward. With the help of UDFs, a trusted proxy takes charge of translating a majority of query statements into executions on the encrypted database. The query result is roughly accurate. Though multiple ciphertexts are stored by the onion encryption, it can still be seen that CryptDB is too complicated for the encryption in the outsourced database, especially for large-scale aggregation operations. In addition, Wu et al. [70] designed a solution for the privacy-preserving queries over encrypted character data. By means of the format-preserving encryption technique, Li et al. [23] presented a lightweight database encryption mechanism L-EncDB. Similarly, specialized encryption algorithms (e.g., AES, OPE and FQE) are used respectively to interpret certain kinds of SQL statements. In most cases, exact query results can be obtained in this mechanism. Other studies [24,71] developed from the above integrated queries are devoted to making plans for optimization strategies or scheduling for complex analytical query statements. Their target is to reduce the cost of query on ciphertexts and to improve the overall query efficiency.
Through the above summary, there exists a problem about the impracticability of ciphertext manipulations which should not be ignored in most of the existing solutions. Therefore, it is necessary for this paper to propose an almost fully functional, secure, efficient and friendly outsourcing scheme for the encrypted cloud databases.

Limitation and Future Work
T-DB attempts to find a trade-off between performance and security. On one hand, OPEA perfects the functionality of ciphertext query. For example, the results of aggregation query can be compared directly, thereby improving overall query performance. On the other hand, OPEA with IND-AOCPA achieves its optimal security under the same functionalities. As for the above case of aggregation-comparison, only the ciphertext range of the arithmetic sum in the sum calculation protocol is leaked to the CSP, which avoids possible leakage of the plaintext distance caused by self-increase operation.
The database owner performs the post-processing stage after receiving query results returned by the cloud. Decryption or secure twoparty computation protocol is used to acquire the final query results for the database user. T-DB is limited by the arithmetical expression, especially the multiplication among attribute columns, and this is the main performance bottleneck of the post-processing stage. For example, in contrast to homomorphic techniques, the protocol in T-DB needs the involvement of database owners to execute one round of data interaction except decryption of the returned encrypted results. As the data size increases, several communication expenses increase at the database owner side. In order to reduce the network traffic, it may be more practical for the database owner to perform these complex arithmetical computations after decryption. A new problem brought on by this method is how to divide the data manipulation into parts that can be executed on the cloud server, and parts that must be executed on the database owner [24]. It is valuable for further improving the overall performance of T-DB.
The experiments show that the total response time of an outsourced encrypted database is affected by the network throughput, transmission delay, query processing and the size of the result set, where the query efficiency is also influenced by query types and, particularly, scheduling strategies of SQL Azure. Our future work will focus on the performance improvement at the cloud RDBMS in the executions over encrypted databases. As illustrated in Table 6, a query in an encrypted database takes more than twice as long as in a plaintext database. The main reason is that since numerous UDFs are invoked in the encrypted query condition, the number of comparisons grows exponentially at the cloud server side. Fixing this issue is dependent on a targeted adjustment from industries, including a systematic overhaul of the index structure, the comparison operators, etc. Before these problems are addressed, one may obtain fast ciphertext query processing by a comprehensive promotion of resources and configuration of cloud servers.
What's more, along with the increasing development of DBaaS techniques, introducing T-DB system to a verifiable auditing outsourcing (inspired by [72,73]), to an application with multi-datasource (inspired by the scheme in [74]) and to a distance-based keyword similarity search (inspired by the work in [75]) will be investigated in the future.

CONCLUSIONS
In this paper, we proposed T-DB as an almost fully functional encrypted database system in clouds. The database is outsourced in the form of ciphertext and almost all types of database manipulations can be directly executed on the encrypted data (updates are supported as well). Neither the CSP nor the database users will be disturbed due to the encryption of the outsourced database. Owners can migrate their databases to an unmodified DBaaS platform smoothly and safely. The database structure and the access mode are preserved. T-DB realizes a database-owner-controlled reliable cloud storage pattern by encrypting the outsourced relational databases, and simultaneously achieves secrecy and utilization, instead of a compromise between them. Ciphertext values are queried with good precision and high efficiency. Our T-DB promotes cloud computing security best practice and may inspire widespread interest in the field of database security. It is expected to have a positive impact on database and information security academia and industry.