SQL queries over encrypted databases: a survey

Abstract

Limited by the local storage resource, data users have to encrypt their data and outsource the encrypted databases to cloud servers to enjoy low-cost, professional data management services, which promotes the rapid development of outsourcing database technology. Despite this, the complex underlying setting and loosely coupled database architecture lead to various security risks and performance bottlenecks, while there is currently no work to achieve a comprehensive evaluation of existing encrypted database solutions from the aspects of underlying settings, security levels, functions, etc. In this work, we first propose an evaluation model to assess SQL functionalities and security from multiple dimensions. Secondly, we categorise the existing SQL query schemes into three categories: software-based construction, hardware-based construction, and hybrid-based construction, that is, a combination of software and hardware components. On this basis, we analyse the framework, advantages, and limitations of classic and state-of-the-art schemes. Finally, we summarise the software-based and hardware-based approaches from dimensions of SQL functionality, security, and efficiency, thus clarifying their ideal application scenarios. Notably, SQL query schemes that exhibit minimal equality of pair leakage and support strong obliviousness can achieve higher levels of security. In addition, hardware-based solutions can achieve more complex SQL queries and superior performance without designing complex and functionally-limited cryptographic tools.

Keywords:

• SQL queries
• encrypted databases
• evaluation model

1. Introduction

The rise of cloud computing has revolutionised the way organisations store and manage data. The scalability and cost efficiency offered by cloud services have led to the widespread adoption of outsourced databases. Despite the compelling of cloud computing (Armbrust et al., 2010), unauthorised access to outsourced databases launched by malicious database administrators or external attackers also poses security problems (Chu et al., 2013; Latif et al., 2014; Mell & Grance, 2009).

In response to these problems, encrypted databases have emerged as a promising solution, which ensures data confidentiality while retaining the convenience and efficiency of cloud services. Once the databases are encrypted and outsourced to the cloud servers, it is becoming difficult to perform meaningful operations over encrypted data. Therefore, efficient SQL queries (Chamberlin & Boyce, 1974) over encrypted databases has been studied by plenty of researchers (Carbunar & Sion, 2011; L. Chen et al., 2023; Kerschbaum et al., 2013; J. Li, Liu et al., 2015; Mironov et al., 2017; Pang & Ding, 2014; Zhu et al., 2021). CryptDB (Popa et al., 2011) utilised Property-Preserving Encryption (PPE) to perform various SQL query operations. EnclaveDB (Priebe et al., 2018) hosted sensitive data along with natively compiled queries in an enclave, enabling efficient and secure SQL queries over encrypted databases. Huawei's GaussDB (Zhu et al., 2021) integrates software-mode encryption algorithms and hardware-mode confidentiality calculations to realise rich SQL query functions. Since then, plenty of researches have emerged (Eskandarian & Zaharia, 2017; Hahn et al., 2019; Jutla & Patranabis, 2022; Kamara & Moataz, 2018; M. Li et al., 2023; Lv et al., 2023; Shafieinejad et al., 2022; Sun et al., 2021). These researches may rely on different techniques, such as cryptographic primitives and trusted hardware.

Despite these advances, current encrypted database solutions still face significant challenges, especially the architecture and security. Loosely coupled database architecture and complex underlying settings lead to various security risks and performance bottlenecks. In addition, existing work lacks a comprehensive evaluation of SQL query schemes from the dimensions of architecture, SQL functionality, and security level. In this case, there is no clear understanding of the trade-offs between functionality and security, and the feasibility of deploying such a solution in the real world, which hinders further development of encrypted databases.

To address the current gaps in encrypted database research, we need a clear classification of existing SQL query schemes. Additionally, we need to establish a comprehensive evaluation model to fully assess the SQL query schemes from the aspects of SQL functionality, performance, and security level. It is also important to develop a security level evaluation system that can provide guidance and benchmarks for comparing and selecting SQL query schemes.

1.1. Our contributions

In this paper, we summarise the state of art SQL query solutions on encrypted databases and evaluate them from multiple aspects. Our contributions are listed as follows.

• We propose a novel evaluation model that comprehensively analyses the functionalities supported by different SQL query schemes and their security regarding confidentiality, privacy, and obliviousness. We also carefully evaluate the security of different schemes by integrating factors such as leakage profile and obliviousness into a unified security assessment scale, ranging from “low” to “higher”.

• We comparatively analyse software and hardware-based SQL query schemes from dimensions of functionality, security, and efficiency. We also delve into software algorithm-based schemes. We summarise the granularity of protection and application scenarios of schemes using different encryption algorithms depending on the data sensitivity and the requirements of the SQL query function.

1.2. Organisation

This paper is organised as follows. The system and threat models of a generic secure SQL query scheme are presented in Section 2. We also proposed an evaluation model capable of analysing the SQL functionalities of different schemes and the security level they provide. In Section 3, we discuss the secure query schemes based on software algorithms. In Section 4, we discuss the classic trusted hardware-based SQL query schemes. In Section 5, we discuss the hybrid schemes combining software and hardware. In Section 6, we first compare some recent and classic secure SQL query schemes and then comparatively analyse the software and hardware-based approaches from dimensions of functionalities, security, and efficiency. We also compare the functionality and security of software-based schemes which use different cryptographic algorithms. Finally, the conclusion and prospects are presented in Section 7.

2. Models and definitions

In this section, we summarise the system and threat models for secure SQL query schemes. These models provide formal definitions for generic secure SQL queries and describe the capabilities of potential adversaries. Following this, we introduce a novel evaluation model capable of analysing both the functionality and security of various SQL query schemes.

2.1. System model

Similar to the model in Poddar et al. (2019), our model is illustrated in Figure 1. Specifically, such a model involves two entities: the cloud server and the data owner.

1. Data Owner: The data owner, an entity with limited resources, opts to outsource their databases to the cloud server. To address security concerns, the database must be locally encrypted before outsourcing. Subsequently. when conducting a SQL query, the parameters within the query are encrypted and sent to the server. Finally, the data owner employs their private key to decrypt the returned query results from the server, ultimately obtaining the final results.

2. Cloud Server: The cloud server is an entity with seemingly inexhaustible resources, responsible for performing data retrieval within the encrypted database and ultimately returning the satisfied records to the data owner.

Figure 1. System model.

Definition 2.1

Generic Secure SQL Query Scheme

Let DB represent a relational database, and EDB represent its encrypted counterpart. The formal definition for generic secure SQL query schemes is given as follows:

• $K\leftarrow \mathrm{KeyGen}\left(1^k\right)$. The key generation algorithm inputs a security parameter $1^k$ and generates a random key K which is managed by the user.

• $\mathrm{EDB}\leftarrow \mathrm{EDBSetup}(K,\mathrm{DB})$. The data owner uses key K to encrypt $\mathrm{DB}$ and generates an encrypted database $\mathrm{EDB}$ which is then outsourced to the cloud server.

• $\mathrm{ER}\leftarrow \mathrm{QueryExec}(\mathrm{EDB},q)$. The cloud server performs SQL query q issued by the user and returns the encrypted results ER to the user.

• $R\leftarrow \mathrm{Dec}(K,\mathrm{ER})$. The user performs the necessary decryption to obtain the plaintext results R.

2.2. Threat model

The threat model for SQL queries over encrypted databases can generally be categorised into three types based on the server's behaviour: honest, semi-honest (Goldreich et al., 2019), and malicious models, each reflecting varying degrees of malicious intent.

1. Honest Model: In the honest model, the server not only faithfully executes the protocol, but also does not pry into the data owner's privacy.

2. Semi-honest Model: In the semi-honest model, the server follows the protocol honestly but remains curious about the owner's data.

3. Malicious Model: In the malicious model, the server not only fails to run the protocol honestly but may also deliberately corrupt the data, engaging in activities such as malicious listening and tampering.

This paper primarily focuses on the semi-honest and malicious models, where the security risks are mainly from malicious listening and tampering. To prevent the cloud server from listening or tampering with sensitive data, encryption and verification techniques have been extensively researched (Benabbas et al., 2011; S. Chen et al., 2023; X. Chen et al., 2021; X. Chen, Li, Weng et al., 2015; Eltayesh, 2017; Jutla & Patranabis, 2022; J. Li et al., 2022; Lv et al., 2023; Reddy & Kumari, 2022; Z. Zhang et al., 2019).

• Encryption Techniques: Encryption provides a fundamental layer of confidentiality, rendering data opaque to unauthorised parties (Jutla & Patranabis, 2022; J. Li, Liu et al., 2015; M. Li et al., 2023; Lv et al., 2023; Popa et al., 2011). Whether a server is semi-honest or malicious, without the correct encryption keys, sensitive data remains secure.

• Verification: Verification extends the cryptographic defense by enabling data owners to validate the integrity and authenticity of returned query results (Benabbas et al., 2011; S. Chen et al., 2023; X. Chen et al., 2021; Eltayesh, 2017). This is particularly crucial in the malicious model where a server could tamper with results.

Although encryption and verification ensure that the service provider does not access or tamper with the data, the access control mechanisms are essential to prevent external attackers from accessing the encrypted database (S. Chen et al., 2023; X. Chen, Li, Huang et al., 2015; Hur & Noh, 2010; J. Li, Chen et al., 2015; Wei et al., 2021). They serve as gatekeepers that govern data accessibility within an encrypted database. These mechanisms, which encompass user authentication, identity-based access regulation, and additional advanced control strategies, ensure that only verified users can access and execute SQL queries.

2.3. Evaluation model

We assume that $T_A=(A_1,A_2,\dots ,A_m)$ and $T_B=(B_1,B_2,\dots ,B_n)$ are two different tables, where $A_1,A_2,\dots ,A_m$ and $B_1,B_2,\dots ,B_n$ are different attributes within the tables. Specifically, $T_A$ is a set of m-tuples (or rows) $(a_1,a_2,\dots ,a_m)$, where $a_i$ is an element in the domain of attribute $A_i$. Similarly, $T_B$ is a set of n-tuples $(b_1,b_2,\dots ,b_n)$, where $b_i$ is an element in the domain of attribute $B_i$. In this paper, we propose an evaluation model to analyse different schemes from two distinct aspects: the type of SQL functionality and the level of security. However, it's important to note that our model does not explicitly take into account aspects of data integrity and freshness.

2.3.1. SQL functionality

Definition 2.2

Equality Query

For a table $T_A$, an equality query on the $T_A$ is defined as: ${\sigma }_{A_i=v}\left(T_A\right)=\{t|t\in T_A\mathrm{and}t(A_i)=v\}$where $t\left(A_i\right)$ is the value of tuple t on attribute $A_i$, and v is a specific value used for filtering the rows.

Definition 2.3

Join

For table $T_A$ and table $T_B$, where $A_i$ and $B_j$ are join attributes, the join operation is defined as: $T_A\bowtie T_B=\{\widehat{t_a{t}_b}|t_a\in T_A\mathrm{and}{t}_b\in T_B\mathrm{and}{t}_a(A_i)=t_b(B_j\left)\right\}$where $\widehat{t_a{t}_b}$ is a combined tuple $(a_1,a_2,\dots ,a_m,b_1,b_2,\dots ,b_n)$, and $t_a\left(A_i\right)$ is the value of tuple $t_a$ on attribute $A_i$. Similarly, $t_b\left(B_j\right)$ is the value of tuple $t_b$ on attribute $B_j$.

Definition 2.4

Group By

For a table $T_A$, the group by operation on attribute $A_i$ can be defined as: ${\gamma }_{A_i}\left(T_A\right)=\left\{\right(A_i,G)|\mathrm{\forall t}\in T_A,t\in G\iff t(A_i)=v\}$where G is a subset of tuples in $T_A$ that share the same value v of attribute $A_i$, and ${\gamma }_{A_i}$ represents a set of such groups for the entire table $T_A$.

Definition 2.5

Order By

For a table $T_A$, with an attribute $A_i$, the order by operation can be defined as: ${\tau }_{A_i}\left(T_A\right)=\left\{\right(t_1,t_2,\dots ,t_m)|\mathrm{\forall k}\in [1,m-1],t_k(A_i)\le t_{k+1}(A_i\left)\right\}$where $t_k\left(A_i\right)$ denotes the value of the kth tuple in the ordered list on attribute $A_i$, and m is the total number of tuples in $T_A$. Generally, the tuples are arranged in ascending or descending order as specified in the query.

Definition 2.6

Range Query

For a table $T_A$ and an interval $(a,b)$, the range query on $T_A$ can be defined as: ${\sigma }_{a<A_i<b}\left(T_A\right)=\{t|t\in T_A\mathrm{and}a<t(A_i)<b\}$where $t\left(A_i\right)$ is the value of tuple t on attribute $A_i$ and $(a,b)$ is an interval of values taken on attribute $A_i$. Range query expands the querying capabilities by enabling the selection of data that falls within a specific numerical or chronological range.

Definition 2.7

Aggregation

For a table $T_A$, an aggregation operation with respect to an aggregate function f over attribute $A_i$ can be defined as: ${\alpha }_{f\left(A_i\right)}\left(T_A\right)=f\left(t\right(A_i)|t\in T_A)$where f could be SUM, COUNT, AVG, MIN, or MAX, and it computes a single value from the set of $A_i$ values across all tuples t in $T_A$.

Definition 2.8

String Pattern Match

For a table $T_A$ and a pattern string P, the string pattern match query can be defined as: ${\sigma }_{A_i\mathrm{LIKE}P}\left(T_A\right)=\{t|t\in T_A\mathrm{and}P\mathrm{matches}t(A_i\left)\right\}$where $t\left(A_i\right)$ is the string value of tuple t on attribute $A_i$, and the pattern match is based on SQL's LIKE operator, which may include wildcard characters.

2.3.2. Security

We first define three aspects of security: data confidentiality, query privacy, data, and program obliviousness. Additionally, we demonstrate the corresponding risks under security definitions, including data leakages and attacks, and outline the security goals to address these issues.

• (1) Confidentiality.

Data confidentiality protects data from unauthorised access and disclosure, including means for protecting personal privacy and proprietary information. We refer to the adaptive security definition given by Curtmola et al. (2006) and use the leakage profile to define the security.

Definition 2.9

Confidentiality

Let $\mathrm{\Pi }$ = (KeyGen,EDBSetup,QueryExec,Dec) be a secure SQL query scheme and $\mathcal{L}$ be a leakage function. For an efficient adversary $\mathcal{A}$ and a simulator $\mathcal{S}$, we define the experiments $\mathrm{Rea}{l}_{\mathcal{A}}^{\mathrm{\Pi }}$ and $\mathrm{Idea}{l}_{\mathcal{A},\mathcal{S}}^{\mathrm{\Pi }}$ as follows.

• $\mathrm{Rea}{l}_{\mathcal{A}}^{\mathrm{\Pi }}$: $\mathcal{A}$ chooses where λ is a security parameter. The game runs $\mathrm{EDBSetup}$ and gives $\mathrm{EDB}$ to $\mathcal{A}$. Then $\mathcal{A}$ chooses a series of query $q_1,\dots ,q_m$. For all $i\in \left[m\right]$, the game runs $\mathrm{QueryExec}(\mathrm{EDB},q_i)$ and gives output to $\mathcal{A}$. Eventually, $\mathcal{A}$ outputs a bit b which is also the output of the $\mathrm{Rea}{l}_{\mathcal{A}}^{\mathrm{\Pi }}$.

• $\mathrm{Idea}{l}_{\mathcal{A},\mathcal{S}}^{\mathrm{\Pi }}$: $\mathcal{A}$ chooses $\mathrm{DB}$. The simulator $\mathcal{S}$ initialises a query list q. The game runs $\mathrm{EDB}\leftarrow \mathcal{S}\left(\mathcal{L}\right(\mathrm{DB}\left)\right)$ and gives $\mathrm{EDB}$ to $\mathcal{A}$. Then $\mathcal{A}$ chooses a series of query $q_1,\dots ,q_m$. For all $i\in \left[m\right]$, the game runs $\mathcal{S}\left(\mathcal{L}\right(\mathrm{DB},q_i\left)\right)$ and gives output to $\mathcal{A}$. Eventually, $\mathcal{A}$ outputs a bit b.

We say that $\mathrm{\Pi }$ is $\mathcal{L}$-semantically secure if for all polynomial probabilistic time adversaries $\mathcal{A}$ there exists an efficient simulator $\mathcal{S}$ and a negligible function $\mathrm{neg}$ such that $\left|Pr\left[\mathrm{Rea}{l}_{\mathcal{A}}^{\mathrm{\Pi }}\right(\lambda )=1]-Pr\left[\mathrm{Idea}{l}_{\mathcal{A},\mathcal{S}}^{\mathrm{\Pi }}\right(\lambda )=1]\right|\le \mathrm{neg}\left(\lambda \right)$Under this security model, an adversary cannot obtain any information about user data except through the leakage profiles generated by the leakage function $\mathcal{L}$.

• (2) Privacy.

Privacy is the most critical concern when performing SQL queries over encrypted databases. To ensure the protection of sensitive information, it is crucial to prevent unauthorised parties from gaining in-depth insights into various aspects of the data. Therefore, we define size pattern, equality pattern, and order pattern to quantify privacy protection.

• Size Pattern (SP). The size pattern typically pertains to the size of the tables retrieved by the query. In most cases, result pattern leakage is not considered a significant risk, since it is challenging for an attacker to extract sensitive information based solely on the size of the table.

• Equality Pattern (EP). The equality pattern pertains to the usage of the equality operator $(=)$ in selection queries, particularly in the WHERE clause, to filter out rows that meet certain conditions. This pattern is often used to match a specific attribute or column value.

• Join Pattern (JP). The join pattern refers to the equality condition used for tuple matching when performing primary, foreign key join operations on two tables. Specifically, during a join operation, the Database Management System (DBMS) needs to select a subset of the Cartesian product using the equality condition. The join pattern reveals whether a pair of tuples have equal values on the join attribute. Although join patterns do not reveal the underlying plaintext data, the frequency information it reveals can be exploited by attackers to extract valuable data.

• Order Pattern (OP). The order pattern refers to the relative order of the encrypted data. Many schemes commonly employ order-preserving encryption (Agrawal et al., 2004; Boldyreva et al., 2011) (OPE) to enable SQL functions that involve comparison operations, such as range queries, group by and aggregation. OPE ensures that $E\left(m_i\right)<E\left(m_j\right)$ for $m_i<m_j$ where E is the encryption algorithm. While the order facilitates a wide range of SQL functions, it is also valid information that an attacker can exploit.

Definition 2.10

Size Pattern Leakage

For a SQL query on table $T_A=(A_1,A_2,\dots ,A_m)$, the size pattern leakage (SPL) is defined as: $\mathrm{SPL}=m\cdot |t|\mathrm{or}m\cdot |t_{\sigma }|$where m is the number of attributes in the $T_A$, $|t|$ and $|t_{\sigma }|$ denote the number of all tuples in the table and the number of tuples satisfying the query.

It is difficult for attackers to launch an effective attack using only SPL. In cases where the database size and query result size are sensitive data, padding is utilised to hide the size pattern.

Definition 2.11

Equality Pattern Leakage

For a table $T_A$ and an attribute $A_i$, the equality pattern leakage (EPL) can be defined as: $\mathrm{EPL}=\left\{t_1\right(A_i)=t_2(A_i\left)\right\}\mathrm{if}ϵ\left(t_1\right(A_i\left)\right)=ϵ\left(t_2\right(A_i\left)\right)$where $t_1\left(A_i\right)$ and $t_2\left(A_i\right)$ represent the plaintext values of attribute $A_i$ for records $t_1$ and $t_2$. $ϵ\left(t_1\right(A_i\left)\right)$ and $ϵ\left(t_2\right(A_i\left)\right)$ represent the encrypted values of attribute $A_i$ for records $t_1$ and $t_2$.

Definition 2.12

Join Pattern Leakage

For a primary, foreign key join operation $T_A\bowtie T_B$ on table $T_A$ and $T_B$, the join pattern leakage (JPL) can be simply defined as: $\begin{array}{rl}\mathrm{JPL}[t_a,t_b]& =1\mathrm{if}{t}_a\left(A_i\right)=t_b\left(B_j\right)\\ \mathrm{JPL}[t_a,t_b]& =0\mathrm{if}{t}_a\left(A_i\right)\ne t_b\left(B_j\right)\end{array}$where $t_a\left(A_i\right)$ is the value of tuple $t_a$ on attribute $A_i$ and $t_b\left(B_j\right)$ is the value of tuple $t_b$ on attribute $B_j$. $A_i$ and $B_j$ are join attributes with the same domain. JPL = 1 indicates that the two tuples have equal values on the join attribute, whereas JPL = 0 indicates that the two tuples have different values on the join attributes.

While attackers cannot directly obtain sensitive data through JPL, it is important to note that the frequency of items can still be deduced using JPL, providing a powerful weapon for launching inference attacks. For example, consider two tables, Customers and Orders, that share a common field CustomerID. The Customers table contains unique CustomerIDs, while the Orders table may contain multiple entries of the same CustomerID, representing multiple orders placed by the same customer. Performing the join operation on these two tables using the equality condition (CustomerID in Customers = CustomerID in Orders) reveals the equality of pairs that can be utilised by attackers to infer the frequency of items. If a specific encrypted CustomerID appears multiple times in the result of the join query, it indicates that the corresponding customer has placed multiple orders. This leakage enables the attacker to deduce the frequency of orders placed by each customer, despite the inability to discern the exact customer identities or order details.

We present two common types of inference attacks (Blackstone et al., 2019; Naveed et al., 2015) that utilise the frequency information revealed by JPL. In these attacks, attackers can effectively deduce private data by combining publicly available auxiliary datasets with frequency information. This approach enables them to launch sophisticated and effective inference attacks as follows.

• Frequency Analysis Attack (Lacharité & Paterson, 2015). In frequency analysis attacks, attackers exploit pattern information leaked during database queries to obtain frequency information which is then used to infer or recover sensitive data within the database. Specifically, attackers can utilise frequency information along with publicly available auxiliary information to correlate the frequencies of the two datasets. Through this correlation, they can deduce private data by performing one-to-one sorting.

• $l_p$-Optimisation Attack (Lacharité & Paterson, 2015). In $l_p$-Optimisation attacks, attackers similarly correlate the frequency information obtained from the pattern information with the frequencies of the public auxiliary dataset to deduce private data. Specifically, attackers minimise a designated cost function, typically $l_p$ distance, between ciphertext and plaintext histograms.

Definition 2.13

Order Pattern Leakage

For a table $T_A$ and an attribute $A_i$, the order pattern leakage (OPL) can be defined as: $\mathrm{OPL}=\left\{t_1\right(A_i)>t_2(A_i\left)\right\}\mathrm{if}ϵ\left(t_1\right(A_i\left)\right)>ϵ\left(t_2\right(A_i\left)\right)$where $t_1\left(A_i\right)$ and $t_2\left(A_i\right)$ represent the plaintext values of attribute $A_i$ for records $t_1$ and $t_2$. $ϵ\left(t_1\right(A_i\left)\right)$ and $ϵ\left(t_2\right(A_i\left)\right)$ represent the encrypted values of attribute $A_i$ for records $t_1$ and $t_2$.

When using OPL, another attack surface arises. We show two common attacks that utilise the order information.

• Sorting Attack (Naveed et al., 2015). In sorting attacks, attackers use the relative order of the encrypted data to deduce sensitive data. Specifically, with enough different attribute values in the encrypted attribute columns, attackers can sort the encrypted data to correspond one-to-one with the message space to recover the private data.

• Cumulative Attack (Naveed et al., 2015). In cumulative attacks, attackers leverage the auxiliary datasets and the relative order of encrypted data to recover the sensitive data. Specifically, if a ciphertext in the encrypted column exceeds $90\mathrm{\%}$ of the other ciphertexts, attackers can recover the plaintext by mapping this ciphertext to the data in the auxiliary dataset that exceeds $90\mathrm{\%}$ of the remaining data.

If the scheme reveals equality, join, or order patterns when executing SQL queries over encrypted databases, then even if it supports rich SQL functionalities, this advantage comes at the expense of leaking a substantial amount of valid information. Such schemes are proven to be insecure.

Overall, the primary objective of designing a secure SQL query scheme is to prevent the leakage of equality, join, and order patterns. For example, when executing SQL queries involving equality such as selection, join, and group by, it is crucial to restrict the amount of information an attacker can learn about equality of pairs. This can be achieved by limiting the leakage of equality conditions and frequency information to only those tuples that match the SQL query, rather than exposing all tuples in the table. Similarly, for the order pattern, the schemes should aim to prevent attackers from deducing any information about the plaintext data, except for the order of the ciphertext, particularly when supporting SQL functions that involve comparison operations like range queries. The m-ORE proposed by Lv et al. (2023) enables to achieve comparison over ciphertext while hiding the most significant differing bits. Regarding the size pattern, most schemes do not prioritise hiding it, as it is challenging for attackers to effectively infer sensitive information solely based on metadata such as table sizes in the database. However, if the metadata, such as the database size, is deemed sensitive and needs to be concealed, the size pattern can be hidden using padding techniques. This involves adding extra characters to a field or column, ensuring that all encrypted values have a uniform length, regardless of the original plaintext length.

• (3) Obliviousness.

Obliviousness is primarily aimed at enhancing the security and privacy of access patterns. Without such measures, malicious adversaries could exploit these patterns to launch leakage abuse attacks (Blackstone et al., 2019; Grubbs et al., 2017; Islam et al., 2012) on query schemes.

Access Pattern. The access pattern refers to the traces left by users during the process of querying records in a table. This includes the locations of accessed data blocks, the order of data block requests, the frequency of access to the same data block, and specific methods of reading or writing data.

The leakage of the access patterns leads to the precise location of the underlying database elements being revealed when a user issues a query on the data block. This allows attackers to infer the importance of the stored data from the user's access pattern, e.g. by counting the frequency of accesses to each data block. At the same time, attackers can also match two consecutive access patterns to infer the correlation between data queries and even the content of the encrypted data. Therefore, the access pattern is the powerful information for an attacker to use to launch effective attacks.

• Access Pattern Attack (Islam et al., 2012). In access pattern attacks, attackers can gain insights into encrypted data by observing the patterns of access to that data. For example, if a particular piece of data is accessed frequently, attackers might infer that it's highly relevant or sensitive. They could potentially guess the contents of encrypted records or infer which records contain certain keywords based on the frequency and access pattern.

• File Injection Attack (Y. Zhang et al., 2016). In file injection attacks, attackers trick a user into encrypting and uploading specially crafted files to a searchable encrypted database or cloud storage. These files are designed by attackers and contain specific data patterns. Once these files are part of the user's encrypted database, attackers monitor the access patterns or query results when the user performs queries. Based on which injected files are accessed during these searches, attackers can infer the nature of the user's queries and potentially gain insights into the user's private data.

• Side-channel Attack (Van Schaik et al., 2021). In side-channel attacks, attackers obtain information from the physical implementation of the cryptosystem, diverging from traditional attacks that rely on brute force or theoretical weaknesses in the algorithm. Side-channel attacks are essentially indirect attacks, exploiting information that is unintentionally exposed rather than directly attacking the system. Access pattern leakage is one such unintentional exposure. For example, attackers observing repeated access to a particular data location could infer that this location contains critical data, thus making it a target for future attacks. The granularity of access patterns can significantly impact the potential for side-channel attacks. For instance, if the access patterns reveal detailed information about individual data items, they could provide a rich source of information for attackers. On the other hand, if the access patterns are coarse-grained, revealing only high-level information, the potential for side-channel attacks may be reduced. The relationship between side-channel attacks and access pattern leakage also has a temporal aspect. Attackers may need to observe the system over a period of time to discern meaningful patterns. This makes systems with frequent data access potentially more vulnerable to these types of attacks.

Definition 2.14

Obliviousness

Let $l=\left(\right(o{p}_1,\mathrm{add}{r}_1,\mathrm{dat}{a}_1),(o{p}_2,\mathrm{add}{r}_2,\mathrm{dat}{a}_2),\dots ,(o{p}_n,\mathrm{add}{r}_n,\mathrm{dat}{a}_n\left)\right)$ be a sequence of operations of length n that accesses the data in the table. Each operation $o{p}_i$ represents a read operation $\mathrm{read}\left(\mathrm{add}{r}_i\right)$ or a write operation $\mathrm{write}(\mathrm{add}{r}_i,\mathrm{data})$. For two sequences of operations $l_1$ and $l_2$ of the same length, we say that the access pattern was successfully hidden if, for all polynomial probabilistic time algorithms, there exists a negligible function neg such that $\left|Pr\left[A\right(l_1)=1]-Pr\left[A\right(l_2)=1]\right|\le \mathrm{neg}\left(\lambda \right)$where $A\left(l_i\right)$ denotes the access sequence generated for a given sequence of operations $l_i$.

The secure SQL schemes should be designed to provide obliviousness while preserving privacy, ensuring that an attacker cannot learn sensitive information from access pattern differences, thus achieving a higher level of security.

3. Software-based secure SQL query schemes

In this section, we discuss the secure SQL query schemes based on software algorithms that utilise cryptographic primitives to provide data security and privacy. According to the utilisation of different cryptographic primitives, we further categorise the secure SQL schemes into three types: those based on property-preserving encryption (PPE), searchable symmetric encryption (SSE), and structured encryption (STE). We discuss the representative schemes in Sections 3.1, 3.2, and 3.3, respectively.

3.1. Schemes based on property-preserving encryption

Property-preserving encryption (Pandey & Rouselakis, 2012) is a category of encryption schemes that permits public computation on encrypted data based on a pre-specified property, such as OPE (Boldyreva et al., 2011) and deterministic encryption (Bellare et al., 2007) (DET). Specifically, DET ensures that $ϵ\left(m_i\right)=ϵ\left(m_j\right)$ for $m_i=m_j$ and OPE ensures that $ϵ\left(m_i\right)>ϵ\left(m_j\right)$ for $m_i>m_j$ where ε is the encryption algorithm. Through the properties it preserves, PPE-based schemes (Alsirhani et al., 2017; Fuller et al., 2017; Papadimitriou et al., 2016; Popa et al., 2011, 2014; Tu et al., 2013) allow performing operations such as range queries and equality comparisons on encrypted data without decryption. To better understand the SQL functionality supported by such schemes along with the leakage, we introduce CryptDB (Popa et al., 2011), a well-established PPE-based scheme as follows.

CryptDB is devoted to establishing an intermediate proxy server situated between the DBMS and the user client. This intermediary proxy server assumes a pivotal role in facilitating various essential operations, including but not limited to SQL query rewriting, key delivering, and result decryption. Notably, CryptDB introduces a multi-layered encryption scheme “onion encryption”, as shown in Figure 2. Specifically, each onion layer represents a specific encryption type that supports particular query functions. The outer layer provides stronger security than the inner layers. When an application initiates a predicate computation on a column, the CryptDB proxy determines the appropriate layer of the onion to perform the computation. If the column's encryption is not in the correct layer, the proxy sends the necessary keys to the server to decrypt the ciphertext layer by layer until the correct encryption layer is reached, enabling the desired computation. The encryption methods used in various onions are shown in Table 1. Specifically, The choice of encryption method within the “onion” is determined by the SQL query issued by the application. For example, DET supports equality-based queries, and OPE supports range queries. CryptDB also introduces other encryption schemes, such as Join, OPE-Join, and Word Search, to facilitate join and search operations.

Figure 2. Onion encryption.

Table 1. Encryption schemes used in onion.

Encryption type	Encryption scheme	Functionality
RND	AES-CBC	Security protection
DET	AES-CMC	Equality query
OPE	Boldyreva et al. (2009)	Range query
HOM	Paillier (1999)	Sum
JOIN	JOIN-ADJ Popa et al. (2011)	Join
SEARCH	Song et al. (2000)	String pattern match

While CryptDB provides rich SQL functionality, it also has concerns regarding efficiency and security.

• Inefficiency. One notable disadvantage of CryptDB is its inherent inefficiency. The outermost layer in an onion is usually non-deterministic, and when performing almost any SQL query, the server needs to decrypt the entire column of data to strip off the outermost layer of the onion.

• Huge Leakage (Grubbs et al., 2017; Naveed et al., 2015). In terms of security, CryptDB reveals equality and order patterns when using DET and OPE, respectively. Specifically, because the onion wraps the deterministic ciphertext in a probabilistic ciphertext, CryptDB is semantically secure and does not reveal any equality pattern when no join operation is performed. However, once the user initiates a join query, the onion is stripped away and the data is again in an insecure deterministic layer, which reveals the frequency information of all the records in the columns. The severe leakage makes CryptDB vulnerable to the frequency analysis, ${\ell }_p$-optimisation, sorting attacks, and cumulative attacks mentioned in Section 2.6.

• Uncertainty of the Proxy Side. CryptDB assumes that cloud servers are semi-honest, but rely on honest proxies. The attacked proxy can result in the leakage of plaintext queries, data, and even secret keys.

In Arasu et al. (2013) first proposed the Cipherbase scheme to support full SQL functionality. The scheme extends industrial-grade database engine (Microsoft, 2022) (Microsoft SQL Server) to achieve orthogonal security. To further improve the efficiency of SQL queries, Tu et al. (2013) proposed the Monomi scheme, splitting the query execution into two parts, one for the encrypted data stored in the cloud and the other for the plaintext data located at the client. However, Monomi's reliance on costly encryption makes it unsuitable for extensive big-data scenarios. To analyse large datasets efficiently, in Papadimitriou et al. (2016) proposed the Seabed using additively symmetric homomorphic encryption. In Alsirhani et al. (2017) further improved security by splitting the encrypted columns among various cloud providers through a distribution technique.

3.2. Schemes based on searchable symmetric encryption

Searchable symmetric encryption allows efficient searching over encrypted documents or records without decryption (Amorim & Costa, 2023; Curtmola et al., 2006; Song et al., 2000). SSE hinges on the utilisation of index mechanisms coupled with trapdoor information to support access to confidential data. In such a scheme, the primary objective for a user is to construct an index that not only supports the efficient retrieval of data but also upholds the principles of privacy preservation. Concurrently, trapdoor information, derived mainly from user queries, plays a critical role in this framework. These trapdoors are typically formulated using key terms or phrases extracted from the query. The formal definition of SSE is as follows and its construction is shown in Figure 3.

Figure 3. Searchable symmetric encryption.

Definition 3.1

Searchable Symmetric Encryption

Let $\mathrm{\Delta }=\{W_1,W_2,\dots ,{\mathrm{W}}_{\mathrm{p}}\}$ be a keyword dictionary, $R=(R_1,R_2,\dots ,R_n)$ be the records in the tables. An SSE scheme is a tuple of five polynomial-time algorithms $\left(\mathrm{KeyGen},\mathrm{Enc},\mathrm{Trapdoor},\mathrm{Search},\mathrm{Dec}\right)$ such that:

• $K\leftarrow \mathrm{KeyGen}(\lambda )$: is a probabilistic algorithm that inputs a security parameter λ, and outputs a random key K.

• $(I,C)\leftarrow \mathrm{Enc}(K,R)$: is a probabilistic algorithm that inputs a secret key K and the plaintext records R, and outputs an index I and ciphertext $C=(C_1,C_2,\dots ,C_{\mathrm{n}})$.

• $T_W\leftarrow \mathrm{Trapdoor}(K,W)$: is a deterministic algorithm that inputs a key K and the search keywords W in SQL queries, and outputs the trapdoor information $T_W$.

• $D_W\leftarrow \mathrm{Search}(I,T_W)$: is a deterministic algorithm to find records that contain keywords W. It inputs an index I and trapdoor information $T_W$, and outputs a collection of identifiers $D_W$.

• $D_i\leftarrow \mathrm{Dec}(K,C_i)$: is a deterministic algorithm running on the client side. It inputs a secret key K and the ciphertext file $C_i$ found by the identifier, and outputs the search results $D_i$.

In this section, we discuss two SSE-based schemes, Secure-Join (Section 3.2.1) and JXT (Section 3.2.2), specifically tailored for the effective handling of a critical category of join queries within the SQL.

3.2.1. Secure-join: leakage-optimised join scheme

The Secure-Join scheme (Hahn et al., 2019) combines SSE and Key-Policy Attribute-Based Encryption (Goyal et al., 2006) (KP-ABE) to provide fine-grained security. The scheme utilises both SSE and ABE encryption to minimise information leakage, and ABE also reduces storage overheads.

The process of performing a join using Secure-Join is illustrated in Figure 4. Firstly, the join attribute is encrypted using SSE. Suppose the join attribute is unique, such as a primary key, the deterministic encryption algorithm SSE.Token is applied. On the other hand, if the join attribute is not unique, the probabilistic encryption algorithm SSE.Enc is applied. The resulting token and ciphertext, collectively known as SSE-value, are then further blinded using ABE to minimise potential leakage. The blinded ciphertext is then outsourced to the cloud. When a user initiates a join query, the client generates a query token by transforming the filter predicates in the query into attribute policies using ABE.KeyGen. Upon receiving the query, the server performs the decryption algorithm, invoking ABE.Dec to filter. Finally, the join matching is executed by SSE based on the filtered data.

Figure 4. Secure-join.

In terms of security, Secure-Join outperforms PPE-based schemes like CryptDB. It only reveals the equality patterns of records that meet the join criteria. However, inherent drawbacks exist within the Secure-Join scheme:

• Limited Join Support and High Overhead (Shafieinejad et al., 2022). Secure-Join exclusively supports primary, foreign key joins, incurring a significant overhead with a time complexity of $O\left(n^2\right)$.

• Absence of Obliviousness. The scheme lacks an additional entity to prevent access pattern leakage, rendering it susceptible to potential access pattern attacks (Islam et al., 2012).

• Super-Additive Leakage (Shafieinejad et al., 2022). It is the most serious point. Specifically, the leakage caused by a collection of queries may be larger than the sum of the leakage caused by each query.

Therefore, although it provides a higher level of security than CryptDB, Secure-Join still falls short in terms of security protection as it does not provide obliviousness and can lead to Super-Additive Leakage. To address these limitations, Shafieinejad et al. (2022) introduced Function-Hiding Inner Product Encryption, enhancing the Secure-Join scheme. This extension not only broadens join support to include hash joins but also achieves a reduced time complexity of $O\left(n\right)$. Critically, it confines the leakage caused by a sequence of queries to the passing closure of the sum of individual query leakages, effectively mitigating super-additive leakage risks.

Similar to the Secure-Join scheme, many schemes use attribute-based encryption to implement access control mechanisms (N. Chen et al., 2022; S. Chen et al., 2023; J. Li et al., 2022; Premkamal et al., 2019). The ciphertext-policy attribute-based encryption (CP-ABE) scheme proposed by J. Li et al. (2022) realises fine-grained access control while solving the problem of user key abuse. The revocable attribute-based encryption scheme that protects the data integrity (RABE-DI) proposed by S. Chen et al. (2023) can dynamically set user access privileges while verifying data integrity.

3.2.2. JXT: queries over join without pre-computation

Join Cross-Tags (Jutla & Patranabis, 2022) (JXT) scheme emerges as a notable enhancement of the Oblivious Cross-Tags (Cash et al., 2013) (OXT) scheme pioneered by Cash et al. This symmetric-key solution adeptly facilitates join operations on encrypted databases without necessitating pre-computation, thereby representing a significant step in SSE. While OXT is based on key-value pairs, JXT uses a similar structure to implement SQL queries on structured data. Therefore we briefly introduce the OXT scheme.

The OXT scheme is the first sublinear index-based framework capable of handling conjunctive keyword queries. Its design incorporates two core index structures, namely TSet and XSet, both of which are essential for retrieval tasks. Specifically, the TSet, serving as an inverted index, is built to expedite the retrieval of individual keywords. Contrarily, the XSet serves as a repository for the hash values of keyword-document pairs. The server utilises s series of intersecting trapdoors which are aligned correspondingly to user queries, enabling to return those documents that contain the complete set of queried keywords.

JXT preserves full compatibility with OXT, ingeniously extending its capabilities to encompass complex queries. In the context of a join query denoted as $w_1\wedge w_2$, where $w_1$ and $w_2$ represent attribute-value pairs originating from two distinct tables, the server orchestrates a meticulous process. Initially, the server synthesises the elements within TSet, encapsulating records that align with the individual keywords $w_1$ and $w_2$. Subsequently, leverage XSet for member detection, enabling the server to ascertain whether records within the respective TSets match the criteria outlined by the join query. Upon the successful completion of member detection, the server promptly transmits the corresponding TSet entry to the client. In the conclusive phase, the client undertakes the decryption process.

In terms of leakage, JXT reveals result pattern, query equality, size pattern, conditional intersection pattern, and join-attribute distribution pattern. These are considered benign, especially if join attributes are primary keys with high entropy (Jutla & Patranabis, 2022). A possible advancement includes future research directed at supporting joins over low-entropy attributes and extending the scheme to support multi-table joins without pre-computation.

We also investigated other SSE-based approaches (Cash et al., 2014; L. Chen et al., 2023; Goh, 2003; M. Li et al., 2021). Many SSE-based schemes tend to focus on queries with limited functionality. In contrast, Pappas et al. (2014) propose a scalable and secure database management system that supports arbitrarily efficient Boolean queries. Additionally, we note that most SSE schemes are designed for single-user, whereas M. Li et al. (2021) support multi-user shared use of SQL queries over encrypted databases by applying the Diffie-Hellman protocol to the Trapdoor algorithm of standard SSE. The DSSE-DC scheme proposed by L. Chen et al. (2023) avoids redundant storage in cloud environments while improving query efficiency by using a deduplication mechanism and inner product matching.

3.3. Schemes based on structured encryption

The structured encryption scheme (Chase & Kamara, 2010) is a symmetric key encryption scheme used to encrypt data structures. Drawing parallels with SSE (Song et al., 2000), STE shares the foundational concept of leveraging indexes for efficient query operations. However, what sets STE apart is its extension of index structures to encompass a broader array of data structures, including multi-maps, dictionaries, and graphs.

Definition 3.2

Structured Encryption

Let T be an abstract data type and δ be a data structure of type T. A structured encryption scheme is a tuple of five polynomial-time algorithms $\left(\mathrm{KeyGen},\mathrm{Enc},\mathrm{Token},\mathrm{Query},\mathrm{Dec}\right)$ such that:

• $K\leftarrow \mathrm{KeyGen}\left(\lambda \right)$: is a probabilistic algorithm that inputs a security parameter λ, and outputs a secret key K.

• $(\gamma ,c)\leftarrow \mathrm{Enc}(K,\delta ,M)$: is a probabilistic algorithm that inputs a secret key K, a data structure δ, and a sequence of data M which is another form of plaintext space corresponding to the data structure. It outputs a sequence of ciphertext c and an encrypted data structure γ.

• $\tau \leftarrow \mathrm{Token}(K,q)$: is a probabilistic algorithm that inputs a key K and a query q. It outputs a token τ.

• $(J,v):=\mathrm{Query}(\gamma ,\tau )$: is a deterministic algorithm that inputs a token τ and an encrypted data structure γ. It outputs a set of pointers J to the ciphertext that matches the query q, and a sequence of semi-private data v.

• $m_j:=\mathrm{Dec}(K,c_j)$: is a deterministic algorithm that inputs a secret key K and a ciphertext $c_j$. It outputs a message $m_j$.

We then discuss two STE-based approaches in Section 3.3.1 and 3.3.2.

3.3.1. SPX: SQL on structurally-encrypted databases

SPX, a relational database encryption framework proposed by Kamara and Moataz (2018), employs structured encryption for secure SQL query execution. SPX creates encrypted databases in both row-wise and column-wise formats, supporting queries in Heuristic Normal Form (HNF). Specifically, the encrypted database construct index structure by using multi-maps and dictionaries, including $\mathrm{M}{\mathrm{M}}_R$ for row-wise mapping, $\mathrm{M}{\mathrm{M}}_C$ for column-wise mapping, $\mathrm{M}{\mathrm{M}}_V$ for handling equality relations among values and a dictionary $\mathrm{DX}$ encapsulating the $\mathrm{M}{\mathrm{M}}_C$ of each column. These structures are encrypted using a dictionary and multi-mapping encryption before being outsourced to the server. The combination of selection, projection, and cross-product operations in relational algebra, known as SPC algebra (Chandra & Merlin, 1977; Codd, 1970), forms the basis for SPX's SQL query. To mitigate the exponential time overhead associated with normal form queries of SPC, Kamara and Moataz introduced HNF which also addresses the challenges posed by the complexity of SQL.

Compared to JXT (Jutla & Patranabis, 2022), SPX has lower computational and communication complexity for certain extreme cases where the result of join queries is empty (Jutla & Patranabis, 2022). However, SPX has pre-computation of joins at setup, which might lead to storage blowup for large databases.

In terms of security, SPX reveals the size pattern, equality pattern, access pattern, and search pattern. There is no doubt that SPX exhibits a lower level of leakage compared to PPE-based (Alsirhani et al., 2017; Fuller et al., 2017; Papadimitriou et al., 2016; Popa et al., 2011, 2014; Tu et al., 2013) because it confines equality pattern leakage to records meeting the specified query criteria.

3.3.2. STI: partially precomputed joins

When the server conducts full precomputation of equi-joins, significant drawbacks emerge. Not only does the server learn the equality patterns within rows, but for the client, the burden of downloading and decrypting a massive number of rows becomes overwhelming. To address this challenge, numerous approaches delegate a portion of the computation to the client (Ciriani et al., 2009; Damiani et al., 2003; Tu et al., 2013), aiming to minimise information leakage. However, none of these schemes effectively support join operations.

In response to this limitation, Cash et al. proposed partially precomputed joins (Cash et al., 2021) based on a structured index (STI) which is an extension of STE. Specifically, the server does not preemptively perform joins on all rows in the table and then performs predicate filtering. Instead, the server stores only the rows from the input table that appear in the join result, and the client downloads only those rows to compute the join. This framework not only mitigates the risk of curious servers learning extensive join patterns but also significantly reduces the computational overhead on the client's end.

While both STI and SPX process analogous queries, STI demonstrates less leakage by leveraging the HashSet technique derived from OXT (Cash et al., 2013). However, compared to JXT, which does not need partial pre-computation of joins during setup, STI exhibits higher query complexity.

Another notable STE-based scheme is the ARQ framework (Espiritu et al., 2022), which does not rely on trusted hardware or cryptographic primitives. Instead, it integrates a management structure for plaintext data with STE, supporting efficient aggregate range queries over encrypted databases.

4. Hardware-based secure SQL query schemes

Software algorithms-based solutions have limitations in supporting full SQL capabilities. A range of trusted hardware-based solutions (Antonopoulos et al., 2020; Bajaj & Sion, 2011; Eskandarian & Zaharia, 2017; M. Li et al., 2023; Priebe et al., 2018; Zheng et al., 2017) effectively addresses this challenge. In Section 4.1, we explore a database engine that uses a secure coprocessor. In Section 4.2, we describe an enclave-based database. In Section 4.3, we discuss the first database system that provides data security at an industrial-strength level. In Section 4.4, we delve into the oblivious query processing, which helps to protect access patterns.

The secure SQL query schemes based on trusted hardware utilise the Trusted Execution Environments (Sabt et al., 2015) (TEE) that protect private data at the hardware level. Intel SGX is the most popular Trusted Execution Environment that provides secure data processing inside the cloud. Enclaves in SGX are protected regions in CPUs, where a remotely attested piece of code can run without interference from a potentially adversarial hypervisor and OS.

4.1. TrustedDB

TrustedDB (Bajaj & Sion, 2011) is the first trusted hardware-based approach that performs SQL queries securely by leveraging a server-hosted trusted hardware Secure Coprocessor (SCPU) during the query processing phase. The SQL query process is shown in Figure 5. It begins with the client discerning between private and public attributes in the database. In this case, private attributes are encrypted, with decryption restricted to either the client or the SCPU. Subsequently, the client encrypts the SQL query using the public key of the SCPU and transmits it to the server agent. Upon receiving the encrypted query, the server forwards it to the request handler within the SCPU. The request handler then decrypts the query and passes it to the query parser. Then, the query parser undertakes query optimisation and separates the components involving private attributes. These particular queries are directed to the database engine inside the SCPU for execution. Simultaneously, the remainder of the query is forwarded to untrustworthy servers to enhance overall performance.

Figure 5. TrustedDB.

TrustedDB is not only more cost-effective than software algorithm-based solutions for linear processing queries but also does not impose limitations on SQL functionality. In terms of security, TrustedDB is more secure than software-based schemes due to it only reveals the size pattern and access pattern. However, since TrustedDB places only a small portion of the query process engine in trusted hardware, it does not guarantee the SQL query's privacy, data integrity, and freshness (Priebe et al., 2018).

4.2. EnclaveDB

EnclaveDB (Priebe et al., 2018) addresses the shortcomings of the TrustedDB by building a secure DBMS. It not only safeguards the SQL query's privacy but also protects the integrity of metadata and intermediate data. The architecture is shown in Figure 6.

Figure 6. EnclaveDB.

EnclaveDB is similar to the TrustedDB in its query process for sensitive and public data. Initially, queries undergo pre-compilation on the client side. The resulting compiled queries are loaded into the enclave during the initialisation phase of the database. When a user's query traverses the proxy module, all query parameters are encrypted and transmitted to the SQL server. If the query pertains to sensitive data, it is executed by invoking the compiled queries stored inside the enclave. In contrast, if the query involves non-sensitive data, the SQL server outside the enclave manages it like a conventional database.

Due to the involvement of a trusted enclave, EnclaveDB supports rich SQL functionality and provides higher security protection than software algorithm-based schemes by hiding the equality and order pattern. However, EnclaveDB cannot protect access patterns due to the lack of obliviousness. In terms of performance, EnclaveDB shows high efficiency under the assumption of having a sufficiently large enclave memory. However, aligning with this requirement is currently challenging due to existing hardware limitations, which may affect practical applications.

4.3. Always encrypted DB

Microsoft's Always Encrypted (Antonopoulos et al., 2020) (AE) database, available in SQL Server, supports rich SQL functionality by leveraging the secure enclave and it supports two enclave types: Windows Virtualisation-based Security (Microsoft, 2023a) and Intel SGX (Costan & Devadas, 2016). It is the first industrial-strength database system that provides data confidentiality.

AE's SQL query process is shown in Figure 7. It begins with a client submitting a plaintext query to the driver, which encrypts query parameters using corresponding keys and sends them to the database engine. Then the system decrypts the data in the enclave and completes the SQL query. AE employs a two-level key system: the column encryption key (CEK) and the column master key (CMK). CEK encrypts the data in the column, and a CMK encrypts one or more CEKs. CMKs are securely stored in a trusted key store outside the database engine, such as the Windows certificate store or Azure Key Vault (Microsoft, 2023b). To execute a secure SQL query, the process involves accessing the key store, encrypting parameters, determining the need for an enclave, performing enclave computation, and decrypting query results using the CEK.

Figure 7. Always encrypted DB.

AE supports rich SQL functionality including equality queries, joins, grouping, aggregation, and string pattern matching, and the involvement of a trusted enclave helps improve the security level. However, as with TrustedDB and EnclaveDB, security leaves much to be desired as obliviousness is not provided. Additionally, it is worth noting that AE does not provide data integrity and protection against denial-of-service attacks (Peng & Liu, 2007).

4.4. ObliDB

The software algorithms-based approaches exhibit inherent vulnerabilities that can lead to the leakage of access patterns. While TEE offers data isolation in trusted hardware-based schemes, it remains compromised as adversaries can trace accessed memory, thereby exposing the access pattern within the enclave. Consequently, TrustedDB, EnclaveDB, and AE prove inadequate in safeguarding access patterns from potential side-channel attacks (Van Schaik et al., 2021). Currently, there are already emerged schemes (Arasu & Kaushik, 2013; Eskandarian & Zaharia, 2017; Krastnikov et al., 2020; Zheng et al., 2017) that start to focus on providing obliviousness.

The oblivious RAM (ORAM) proposed by Goldreich and Ostrovsky (Goldreich & Ostrovsky, 1996) offers the capability to hide access patterns. The ORAM utilises “oblivious operations” which intentionally obfuscate the underlying memory access patterns. However, the impracticality of deploying ORAM in real cloud models arises due to its polylogarithmic computation complexity and size overhead (Bindschaedler et al., 2015). Oblivious query processing (Arasu & Kaushik, 2013) offers a series of oblivious query processing algorithms to protect access patterns but with poor performance.

ObliDB, introduced by Eskandarian and Zaharia (2017), not only furnishes obliviousness across multiple database access methods but also exhibits superior speed and diminished overhead when compared to ORAM. The ObliDB's architecture is illustrated in Figure 8. Unlike EnclaveDB which stores tables in the enclave, ObliDB encrypts the tables and stores them in untrusted memory because the protected memory capacity in the enclave is not large enough. The core of its safeguarded access pattern is the deployment of oblivious query processing algorithms within secure enclaves. This ensures that memory blocks that contain sensitive data are uniformly accessed, preventing any unauthorised access or data breaches.

Figure 8. ObliDB.

ObliDB provides obliviousness for two primary data storage methods: flat linear tables and structured indexes. The former organises records in contiguous memory blocks, mandating access to all blocks for both read and write operations to obfuscate access patterns. Even in scenarios where a record fails to satisfy the predicate conditions in a query, a dummy write to the corresponding memory block becomes imperative to maintain uniformity in access patterns across the dataset. Contrarily, the structured index storage approach employs a combination of ORAM and the B+ tree structure to ensure obliviousness. All data resides within the leaf nodes of the B+ tree, ensuring each lookup accesses an equivalent number of nodes. Moreover, when a query entails a fixed number of memory accesses, ORAM steps in to mask the access patterns effectively.

In terms of SQL query functionality, ObliDB supports a spectrum of operations, including selection, join, aggregation, group by, and range queries, etc. Regarding security, ObliDB leaks the least compared to the other schemes discussed before and since it hides the access pattern, it only reveals the size of the input and output tables, providing the highest security level. However, since ObliDB also uses enclaves, its performance is also limited by the small amount of protected memory in the enclave.

Opaque (Zheng et al., 2017) also provides obliviousness by introducing distributed oblivious relational operators while supporting rich SQL functionality. However, ObliDB and Opaque can only support primary-foreign key joins in join operations. Krastnikov et al. (2020) proposed an efficient oblivious join algorithm based on sorting networks that does not use expensive ORAM and specifically protects access patterns in equi-joins.

5. Hybrid approach: combine software and hardware

With the development of secure hardware technologies, there arises a current need to balance the functionality and security of encrypted database queries. Therefore, hybrid schemes have recently emerged (Cao et al., 2020; Zhu et al., 2021). They combine the advantages of both software and hardware approaches. This strategic convergence facilitates comprehensive application scenarios, accommodating diverse business contexts, including public and hybrid cloud environments, through seamless transitions between hardware and software modes. In this section, we present two cloud database products: Huawei's GaussDB (Section 5.1) and Alibaba's PolarDB (Section 5.2), which employ integrated hardware and software solutions to address the evolving landscape of secure data management.

5.1. GaussDB

Huawei's GaussDB (Zhu et al., 2021) achieves rich SQL functionality through the integration of cryptography algorithms in the software mode and confidential computation in the hardware mode. The software mode, operating in the insecure Rich Execution Environment (REE), includes data encryption and indexing, supporting common SQL queries like equality and range queries. On the other hand, the hardware mode, running in TEE, caters to complex queries such as aggregation and string pattern match. To facilitate cross-platform access to TEE resources, GaussDB utilises the SecGear (Chenmaodong & Huawei Co. Ltd, n.d.) (a confidential computing security application development kit) as a virtual TEE, with current support for Intel SGX and ARM TrustZone (Pinto & Santos, 2019).

GaussDB's SQL query process is similar to AE which we discussed in Section 4.3. The driver parses the query, determines the encryption type, rewrites the query, and transmits it to the database engine. The engine then selects the execution mode based on query type and computational cost. When the software mode is selected, the cryptographic algorithm is directly invoked for query execution. While in the hardware mode, a trusted channel between the driver and trusted hardware is established for key exchange.

Although GaussDB ensures data confidentiality, it does not provide data integrity and freshness, and it does not prevent malicious adversaries from tampering with query results. Since GaussDB does not provide obliviousness, it's less secure than ObliDB, and side-channel attacks and access pattern attacks enable adversaries to learn much useful information.

5.2. PolarDB

Alibaba's encrypted database PolarDB (Cao et al., 2020) can integrate hardware and software, and supports both pure cryptography and trusted hardware technical solutions, which makes it easy for users to make their own choices based on business needs. Users are free to specify the encryption columns for each scheme, and non-encrypted data is not affected, which provides a fine-grained security and performance trade-off. At the hardware level, PolarDB supports Intel SGX and FPGA shield cards and provides rich SQL functions including numerical computation, string manipulation, and range queries. At the software level, pure cryptographic algorithms support few SQL functions such as equality and join query in a TEE-free environment.

PolarDB offers a flexible, high-performance, and secure database service with vast storage capacity by combining hardware and software. However, like other pure hardware solutions, PolarDB is not resistant to side-channel attacks and access pattern attacks.

6. Comparison

Currently, we have discussed software algorithm-based, trusted hardware-based, and hybrid schemes. To satisfy diverse user requirements regarding functionality and security in executing SQL queries over encrypted databases, we first utilise our evaluation model to compare some recent and classic schemes in Section 6.1. Then, we conduct a comprehensive analysis and comparison of software algorithm-based and trusted hardware-based schemes in Section 6.2. Eventually, we compare and assess the functionality and security aspects of schemes in the software mode which use different cryptographic algorithms in Section 6.3.

Table 2. Comparison of existing encrypted databases

6.1. Comparison of existing secure SQL query schemes

We utilise our proposed evaluation model to compare some recent and classic secure SQL query schemes from dimensions of SQL functionalities, technologies or primitives, potential leakages, and attacks they may face. The detailed evaluation results are shown in Table 2.

To comprehensively assess the security levels of different SQL query schemes, it is essential to evaluate two crucial metrics: the number of revealed equality of pairs and the availability of obliviousness. The number of revealed equality of pairs serves as a fundamental criterion for measuring the security strength of a scheme. A scheme with minimal or no equality of pair leakage protects the access pattern and ensures that the equality relation of some attribute between tuples is not accessible to attackers, avoiding numerous effective inference attacks. In contrast, a scheme that exhibits significant equality of pair leakage poses a higher risk of exposing relationships and patterns within the encrypted data, leading to privacy breaches. In addition, the availability of obliviousness in a SQL query scheme is another critical aspect to consider. A scheme providing obliviousness has the same access patterns for every data block, making it impossible for an attacker to obtain any useful information from the access pattern. In contrast, schemes without obliviousness are vulnerable to access pattern attacks. Therefore, SQL query schemes that exhibit minimal or no equality of pair leakage and offer strong obliviousness can achieve higher levels of security. We harmonise these factors into a scalar security assessment ranging from “low” to “higher”. These four security levels of SQL query schemes are as follows:

• Low Security Level. The SQL query schemes classified under this level offer minimal protections and lack any form of obliviousness. These schemes reveal all equality of pairs within the tables, which means that the cloud server is privy to all access and equality patterns, whether they satisfy the SQL query or not. This level is susceptible to the most basic forms of inference attacks such as frequency analysis and $l_p$-Optimisation due to its transparency in operation patterns and lack of significant protective layers.

• Moderate Security Level. The SQL query schemes at this level do not provide obliviousness and only reveal partial equality of pairs, specifically the records that satisfy the SQL query. Common attacks at this level could include more sophisticated access pattern attacks that narrow down the focus to subset data revealed by queries.

• High Security Level. High-security level schemes significantly reduce the leakage by not revealing any equality of pairs. SQL query schemes that are based on trusted hardware typically reside at this security level, offering enhanced privacy protection and demonstrating resilience against inference attacks. However, their lack of obliviousness leaves them susceptible to more complex side-channel attacks.

• Higher Security Level. The highest level in our model, provides not only protection for all equality of pairs but also incorporates obliviousness. SQL query schemes under this category are the most secure, designed to withstand sophisticated attacks, including those leveraging indirect information such as frequency and access pattern. They obfuscate access patterns by using ORAM or differential privacy.

6.2. Comparative analysis of software and hardware-based schemes

We analyse and summarise the advantages and limitations of the software-based and hardware-based approaches from three dimensions of SQL functionality, security and performance, elucidating their application scenarios.

• SQL Functionality. Secure SQL query schemes based solely on cryptographic tools have limitations in handling complex SQL queries. For example, OPE encryption schemes restrict functionality to range queries, lacking the complete set of operators available in a standard database query. In contrast, the data inside TEE is naturally secure, and hardware-based databases avoid building complex cryptographic schemes by executing SQL queries directly on plaintext within the trusted hardware. Therefore, they can support more complex SQL functionalities and computations such as joins, aggregations, order by, group by, etc.

• Security. Security threats to software-based schemes primarily stem from leakage caused by cryptographic algorithms. For example, DET and OPE algorithms reveal equality and order patterns, respectively, which can be learned by attackers to launch effective inference attacks. Hardware-based schemes, while offering a higher security level, still present concerns which arise from inherent vulnerabilities in the hardware itself and the fact that trusted hardware often overlooks preventing side-channel attacks. Additionally, if vulnerabilities exist in the code running within the TEE, they could be exploited by an attacker to compromise the database's security. Despite these concerns, trusted hardware-based schemes generally maintain a higher security level compared to software algorithm-based schemes, for they reveal less exploitable information.

• Efficiency. Hardware-based solutions demonstrate superior efficiency compared to software-based solutions for several reasons. In hardware-based approaches, data can be decrypted in an isolated and secure environment, such as an Enclave, and operations can be executed efficiently. In contrast, cryptographic primitive-based methods, like fully homomorphic encryption (Gentry, 2009), usually involve higher computational overhead (Cooney, 2009). These methods require complex mathematical operations to maintain the encrypted state of data during processing, which can lead to reduced performance. Therefore, in scenarios that require efficient computation and querying, hardware-based query solutions should be given priority.

The choice between hardware and software solutions should hinge on a judicious evaluation of the context. For environments where trusted hardware is available and requires complex SQL functionality, trusted hardware-based solutions shine. Software solutions are preferable in cases where only common SQL queries are required or where the deployment environment cannot be tightly controlled.

Moreover, an emerging trend is the symbiotic integration of software and hardware solutions, aiming to combine the flexibility of software algorithms with the robust security benefits of hardware. This combination can be particularly effective when dealing with complex query types or meeting stringent security requirements.

6.3. Comparative analysis of PPE, SSE and STE-based schemes

When delving into the domain of software algorithm-based schemes, one uncovers several cryptographic methods, each exhibiting unique characteristics in terms of the SQL functionality they support and the level of security they offer. In our comparative analysis, we dissect and elucidate the features of PPE, SSE, and STE, offering insight into the ideal application scenarios and the granularity of protection for each.

• PPE-based schemes. The granularity of protection in PPE-based schemes is the lowest among these three types of schemes. This is because PPE schemes maintain some properties of the plaintext to allow specific types of queries. They are specialised for efficiency in specific types of queries, such as equality-match or range queries. It offers a compromised security level due to its property-preserving nature, which could lead to a variety of leakage-abuse attacks (Blackstone et al., 2019; Grubbs et al., 2017; Naveed et al., 2015). They are suitable for scenarios that require high query efficiency but do not pay special attention to data sensitivity.

• SSE-based schemes. SSE-based schemes offer a medium level of granularity in protection. They facilitate a more extensive range of search-related operations without preserving the plaintext properties, which improves security over PPE. However, the search pattern and access pattern can still present a potential vector for exploitation (Islam et al., 2012; Y. Zhang et al., 2016). SSE-based schemes strike a balance between functionalities and security. They are well-suited to scenarios that require a broader search capability with moderate security requirements.

• STE-based schemes. STE schemes provide the finest granularity of protection. They encrypt both the data and their structures, which prevents attackers from making inferences based on access or search patterns. This level of protection is the most comprehensive, but it also requires more computational resources, which may impact the efficiency of query processing. They are specifically tailored to handle structured data, enabling rich queries over encrypted databases that maintain the nuanced relationships inherent in complex data structures. They are indispensable for scenarios demanding high-security assurances paired with the need to perform queries on encrypted structured data, such as hierarchical data or graph-based datasets.

When choosing an appropriate cryptographic scheme, we need to have a deep understanding of the data's structure and sensitivity, the specific requirements of the SQL queries anticipated, and the security model necessary. For example, while PPE might suffice for non-sensitive and high-speed querying, STE is the first choice for databases that hold sensitive structured data and require comprehensive security.

7. Conclusion

In this work, we first propose an evaluation model to assess SQL functionality and security. Then, we classify secure SQL query schemes into three categories and analyse their architectures, advantages, and limitations. Finally, we compare hardware-based and software-based schemes from multiple aspects. Our comprehensive evaluation helps guide stakeholders in making informed decisions.

Based on the results analysed in this paper, there may be the following two future research directions:

• Enhancements to TEE-Based Schemes. Future research should focus on optimising the enclave page cache (EPC) memory management. This is critical to enhance the performance of TEE-based schemes.

• Efficient Access Pattern Hiding Structures. There is also a need to develop lightweight ORAM or new obfuscation methods. Such advancements are essential for improving efficiency in big data contexts.

Disclosure statement

No potential conflict of interest was reported by the author(s).