Executing SQL over encrypted data in the database-service-provider model

Hakan HacigümüşB. IyerChen LiS. Mehrotra

article2002SIGMOD1,389 citationsSIGMOD Test of Time Award

Proposes an algebraic query-splitting framework that pairs coarse-grained server-side index processing with fine-grained client-side decryption, enabling efficient execution of complex SQL queries over untrusted cloud databases while preserving data privacy.

Listen

Modern organizations increasingly rely on third-party service providers to host and manage database workloads. However, outsourcing sensitive enterprise data introduces severe privacy risks, as untrusted providers or compromised servers could expose confidential records. Conventional solutions either require the provider to decrypt data during processing—compromising confidentiality—or force the client to download and decrypt entire databases locally, creating unacceptable network and computational bottlenecks.

The article develops and evaluates a framework that executes structured query language operations directly over encrypted databases hosted by untrusted providers. The primary objective is to maximize query processing on the remote server while ensuring that neither plaintext data nor exact values are revealed, leaving only minimal post-processing for the client.

To achieve this, the article introduces a data storage and query transformation model. Plaintext records are encrypted in bulk using standard encryption algorithms, while individual attribute domains are partitioned into coarse discrete intervals, or buckets, with assigned index values stored alongside the ciphertext. When a user issues a query, an algebraic rewriting framework splits it into two components: a server-side query that operates on bucket identifiers to filter candidates without decryption, and a lightweight client-side query that decrypts returned candidate rows and eliminates false positives. The authors validated this architecture using standard industry benchmarks across multiple database scales and bucket configurations.

The findings show that bucket-based query splitting effectively offloads the majority of query filtering to the remote database provider. Increasing the number of attribute buckets significantly sharpens server-side filtering, leading to steep reductions in network transmission volume and client post-processing time. Across benchmark queries, client decryption and residual filtering accounted for most client-side latency, while overall response times remained within practical operational thresholds compared to centralized architectures.

These results demonstrate that organizations can achieve strong data confidentiality without sacrificing the economic and management benefits of outsourced database services. By delegating coarse candidate filtering to untrusted infrastructure, enterprises can lower infrastructure overhead and maintain data security without prohibitive network penalties.

The article recommends adopting bucket-based coarse indexing when deploying outsourced database architectures. System designers should tune partition granularities according to query patterns to balance security and performance. Future work should focus on developing automated, cost-based optimizers to select optimal bucket partitions and extend algebraic rewriting to support more advanced analytical functions.

Department of Information and Computer Science IBM University of California, Irvine centralized architecture ciphertexts data security database-service-provider model SQL over encrypted data query execution

Hacigümüş et al (2002).pdf

Paper: Protecting Respondents' Identities in Microdata Release, Pierangela Samarati (2001). This foundational work establishes core data anonymization and domain generalization principles that inform coarse partitioning and bucket-based indexing over sensitive records.

Paper: CryptDB: protecting confidentiality with encrypted query processing, Raluca Ada Popa et al. (2011). CryptDB advances query execution over encrypted relational databases beyond bucket-based partitioning by introducing onion encryption and dynamic, operation-specific proxy rewriting.
Paper: Order preserving encryption for numeric data, Rakesh Agrawal et al. (2004). This paper develops order-preserving encryption schemes for numeric data to evaluate comparisons directly on ciphertext without relying on coarse bucket approximations.

Cover for Executing SQL over encrypted data in the database-service-provider model

Abstract

Rapid advances in networking and Internet technologies have fueled the emergence of the “software as a service” model for enterprise computing. Successful examples of commercially viable software services include rent-a-spreadsheet, electronic mail services, general storage services, disaster protection services. “Database as a Service” model provides users power to create, store, modify, and retrieve data from anywhere in the world, as long as they have access to the Internet. It introduces several challenges, an important issue being data privacy. It is in this context that we specifically address the issue of data privacy.

There are two main privacy issues. First, the owner of the data needs to be assured that the data stored on the service-provider site is protected against data thefts from outsiders. Second, data needs to be protected even from the service providers, if the providers themselves cannot be trusted. In this paper, we focus on the second challenge. Specifically, we explore techniques to execute SQL queries over encrypted data. Our strategy is to process as much of the query as possible at the service providers’ site, without having to decrypt the data. Decryption and the remainder of the query processing are performed at the client site. The paper explores an algebraic framework to split the query to minimize the computation at the client site. Results of experiments validating our approach are also presented.

Topics

centralized architecture ciphertexts data security decryption encrypted data privacy risks query processing remote servers sql content providers

Keywords

database-service-provider model SQL over encrypted data query execution

1. INTRODUCTION
2. RELATION ENCRYPTION AND STORAGE MODEL
2.1 Partition Functions
2.2 Identification Functions
2.3 Mapping Functions
2.4 Storing Encrypted Data
2.5 Decryption Functions
4. IMPLEMENTING RELATIONAL OPERATORS OVER ENCRYPTED RELATIONS
5. ALGEBRAIC FRAMEWORK FOR QUERY SPLITTING
5.1 Heuristic Rules to Separate Queries
6. EXPERIMENTAL EVALUATION
6.1 Experiment 1
6.2 Experiment 2
7. CONCLUSIONS
8. REFERENCES

Knowls

Knowl 1 — Relation Encryption and Storage Model
model/method
In the database-service-provider model, each original relational table $R(A_1, A_2, \dots, A_n)$ is stored at the untrusted service provider as an encrypted relation:

$R^S(etuple, A_1^S, A_2^S, \dots, A_n^S)$

where $etuple$ is an encrypted string representing the entire tuple $(a_1, a_2, \dots, a_n)$ produced using a block cipher (such as AES, RSA, Blowfish, or DES), and each $A_i^S$ is an auxiliary attribute index used for query processing at the server.

The decryption operator $D$ maps an encrypted relation (or the result of relational operations over encrypted relations) back to the unencrypted plaintext domain:

$D(R^S) = R$

When applied, $D$ strips off the auxiliary index values $A_i^S$ and decrypts the encrypted tuple string $etuple$ into the plaintext attribute values $(A_1, A_2, \dots, A_n)$ .
Knowl 2 — Partition, Identification, and Mapping Functions for Attribute Indexing
definition
To enable server-side query filtering on an attribute $A_i$ of relation $R$ without decrypting data, the domain of values $\mathcal{D}_i$ of $R.A_i$ is divided into $k$ non-overlapping partition intervals or sets $\{p_1, p_2, \dots, p_k\}$ such that their union covers $\mathcal{D}_i$ :

$partition(R.A_i) = \{p_1, p_2, \dots, p_k\}$

An identification function $ident_{R.A_i}(p_j)$ assigns a unique identifier (such as a collision-free hash value or integer) to each partition $p_j$ such that $ident_{R.A_i}(p_j) \neq ident_{R.A_i}(p_l)$ whenever $j \neq l$ .

The base mapping function $Map_{R.A_i}(v)$ maps any attribute value $v \in \mathcal{D}_i$ to the identifier of the partition containing $v$ :

$Map_{R.A_i}(v) = ident_{R.A_i}(p_j) \quad \text{where } v \in p_j$

Mapping functions are classified into two types:
1. Order-preserving: For any two values $v_i, v_j \in \mathcal{D}_i$ , $v_i < v_j \implies Map_{R.A_i}(v_i) \le Map_{R.A_i}(v_j)$ .
2. Random: Mapping functions that are not order-preserving.
Extended mapping functions for sets and range comparisons are defined as:

$Map_{R.A_i}(S) = \{ident_{R.A_i}(p_j) \mid p_j \cap S \neq \emptyset\}$

$Map_{R.A_i}^>(v) = \{ident_{R.A_i}(p_j) \mid p_j.\text{low} \ge v\}$

$Map_{R.A_i}^<(v) = \{ident_{R.A_i}(p_j) \mid p_j.\text{high} \le v\}$

where $p_j.\text{low}$ and $p_j.\text{high}$ denote the lower and upper bounds of partition $p_j$ .
Knowl 3 — Condition Mapping Rules for Single-Attribute Predicates
algorithm
Given an unencrypted query selection condition $C$ , the mapping function $Map_{cond}(C)$ translates $C$ into an index condition over the auxiliary encrypted attributes $A_i^S$ evaluated by the server:
- Equality ( $A_i = v$ ):
$Map_{cond}(A_i = v) \implies A_i^S = Map_{A_i}(v)$
- Inequality ( $A_i < v$ ):
  - Order-preserving mapping: $Map_{cond}(A_i < v) \implies A_i^S \le Map_{A_i}(v)$
  - Random mapping: $Map_{cond}(A_i < v) \implies A_i^S \in Map_{A_i}(\{v' \mid v' < v\})$
- Inequality ( $A_i > v$ ):
  - Order-preserving mapping: $Map_{cond}(A_i > v) \implies A_i^S \ge Map_{A_i}(v)$
  - Random mapping: $Map_{cond}(A_i > v) \implies A_i^S \in Map_{A_i}(\{v' \mid v' > v\})$
- Composite Conditions:
$Map_{cond}(C_1 \lor C_2) \implies Map_{cond}(C_1) \lor Map_{cond}(C_2)$

$Map_{cond}(C_1 \land C_2) \implies Map_{cond}(C_1) \land Map_{cond}(C_2)$
Knowl 4 — Condition Mapping Rules for Join Predicates
algorithm
The condition mapping function $Map_{cond}$ translates join conditions between attributes $A_i$ and $A_j$ into conditions over index attributes $A_i^S$ and $A_j^S$ executed at the server:
- Equi-join ( $A_i = A_j$ ):
$Map_{cond}(A_i = A_j) \implies \bigvee_{(p_k, p_l) \in \Phi} \left(A_i^S = ident_{A_i}(p_k) \land A_j^S = ident_{A_j}(p_l)\right)$

where $\Phi = \{(p_k, p_l) \mid p_k \in partition(A_i), p_l \in partition(A_j), p_k \cap p_l \neq \emptyset\}$ .
- Theta-join with Inequality ( $A_i < A_j$ ):
  - If $Map_{A_i}$ is order-preserving:
$Map_{cond}(A_i < A_j) \implies \bigvee_{p \in partition(A_i)} \left(A_i^S = ident_{A_i}(p) \land A_j^S \ge Map_{A_j}(p.\text{low})\right)$
- If $Map_{A_j}$ is order-preserving:
$Map_{cond}(A_i < A_j) \implies \bigvee_{p \in partition(A_j)} \left(A_j^S = ident_{A_j}(p) \land A_i^S \le Map_{A_i}(p.\text{high})\right)$
- If both $Map_{A_i}$ and $Map_{A_j}$ are order-preserving:
$Map_{cond}(A_i < A_j) \implies \bigvee \left(Map_{A_i}(p_k.\text{low}) \le Map_{A_j}(p_l.\text{high})\right)$
- If both $Map_{A_i}$ and $Map_{A_j}$ are random:
$Map_{cond}(A_i < A_j) \implies \bigvee_{(p_k, p_l) \in \Psi} \left(A_i^S = ident_{A_i}(p_k) \land A_j^S = ident_{A_j}(p_l)\right)$

where $\Psi = \{(p_k, p_l) \mid p_k \in partition(A_i), p_l \in partition(A_j), p_k.\text{high} \ge p_l.\text{low}\}$ .
Knowl 5 — Split Execution of Selection and Join Operators
model/method
To evaluate relational selections and joins over encrypted relations, operations are split into coarse filtering executed at the server over auxiliary index attributes and exact filtering executed at the client after decryption:
- Selection Operator ( $\sigma_C(R)$ ):
$\sigma_C(R) = \sigma_C\left(D\left(\sigma^S_{Map_{cond}(C)}(R^S)\right)\right)$

where $\sigma^S$ executes at the server using the translated condition $Map_{cond}(C)$ over encrypted index attributes in $R^S$ . The server returns a superset of candidate encrypted tuples, which the client decrypts with $D$ and filters with $\sigma_C$ to eliminate false positives.
- Join Operator ( $R \bowtie_C T$ ):
$R \bowtie_C T = \sigma_C\left(D\left(R^S \bowtie^S_{Map_{cond}(C)} T^S\right)\right)$

where $\bowtie^S$ executes at the server over encrypted relations $R^S$ and $T^S$ using $Map_{cond}(C)$ . The joined candidate tuples are transmitted to the client, decrypted with $D$ , and filtered using the original join condition $\sigma_C$ .
Knowl 6 — Split Execution of Grouping, Aggregation, Sorting, and Duplicate Elimination Operators
model/method
Relational grouping, aggregation, sorting, and duplicate elimination are divided between server-side pre-grouping on encrypted partition indices and client-side final evaluation:
- Grouping and Aggregation ( $\gamma_L(R)$ ): For attribute list $L = L_G \cup L_A$ , where $L_G$ is the grouping attribute list and $L_A$ is the aggregate functions list:
$\gamma_L(R) = \gamma_L\left(D\left(\gamma^S_{L'}(R^S)\right)\right) \quad \text{where } L' = \{A_i^S \mid A_i \in L_G\}$

The server groups encrypted tuples by index attributes $L'$ without evaluating aggregates. Because plaintext tuples belonging to the same group map to the same partition index group, the client receives pre-grouped batches, decrypts them in a single pass, and computes $L_A$ without needing full in-memory re-grouping.
- Sorting ( $\tau_L(R)$ ):
$\tau_L(R) = \tau_L\left(D\left(\gamma^S_{L'}(R^S)\right)\right) \quad \text{where } L' = \{A_i^S \mid A_i \in L\}$

If all mapping functions for attributes in $L$ are order-preserving, the server executes sorting $\tau_{L'}^S$ instead of $\gamma_{L'}^S$ , allowing the client to sort locally within pre-sorted partition buckets.
- Duplicate Elimination ( $\delta(R)$ ):
$\delta(R) = \delta\left(D\left(\gamma^S_{L'}(R^S)\right)\right) \quad \text{where } L' = \{A_i^S \mid A_i \in R\}$
Knowl 7 — Split Execution of Set Difference Operator via Left-Outer Join
model/method
Directly evaluating the set difference $R - T$ at the server is infeasible over encrypted data. To avoid transmitting all of $R^S$ and $T^S$ to the client, the operation is translated using a server-side left-outer join (denoted $\leftouterjoin^S$ ) combined with grouping and client-side null-filtering:

$R - T = \pi_{R.A_1, \dots, R.A_n}(R') - \pi_{T.B_1, \dots, T.B_n}(R')$

where

$R' = D\left(\gamma^S_{L'}\left(R^S \leftouterjoin^S_{Map_{cond}\left(\bigwedge_{i=1}^n (R.A_i = T.B_i)\right)} T^S\right)\right)$

with $L' = \{A_1^S, \dots, A_n^S, B_1^S, \dots, B_n^S\}$ .

Server-side grouping by $L'$ groups all outer-join tuples having NULL values for $T^S$ attributes together. When candidate tuples arrive at the client, the client only needs to decrypt and evaluate set difference for tuples where the $T$ component is not NULL; any $R$ tuple joined strictly with NULL $T$ attributes is immediately retained as a valid answer.
Knowl 8 — Algebraic Query Splitting Framework
algorithm
Given an unencrypted relational query tree $Q$ , the algebraic query splitting procedure decomposes $Q$ into a server-side query $Q^S$ executing over encrypted relations and a client-side query $Q^C$ executing over decrypted intermediate results:
1. Replace each plaintext base relation $R$ in the query tree with $D(R^S)$ .
2. Translate leaf selection operators $\sigma_C$ into server selections $\sigma^S_{Map_{cond}(C)}$ positioned below $D$ , and retain client selections $\sigma_C$ positioned above $D$ .
3. Pull the decryption operators $D$ up above relational joins and outer joins by replacing join operators $\bowtie_C$ with server joins $\bowtie^S_{Map_{cond}(C)}$ below $D$ and exact join conditions $\sigma_C$ above $D$ .
4. Replace grouping, duplicate elimination, and sort operators with their corresponding server-side pre-grouping $\gamma^S_{L'}$ operators below $D$ , retaining exact grouping/aggregation $\gamma_L$ , $\delta$ , or $\tau_L$ above $D$ .
5. The boundary defined by the topmost $D$ operators separates the query tree into $Q^S$ (all operators below $D$ , sent to the server) and $Q^C$ (all operators at and above $D$ , executed at the client).
Knowl 9 — Experimental Performance of Split SQL Execution vs Partition Bucket Granularity
empirical result
On TPC-H benchmarks (scale factors 0.01 and 0.1, representing 10 MB and 100 MB databases on IBM DB2 v7.1 with Blowfish encryption on Pentium III 700 MHz machines):
1. For selection queries (such as modified TPC-H Q6), increasing the number of partition buckets from 2 to 8 significantly decreases client-side execution time and network transmission cost. The client execution time drops because a finer partition granularity improves server-side filtering selectivity (reducing false positives), meaning fewer rows are transmitted and decrypted at the client.
2. Server-side query execution time remains relatively constant as the number of buckets increases, because the query optimizer defaults to a sequential table scan due to the overall query selectivity (~18%).
3. For join queries (such as modified TPC-H Q3 joining customer and orders), increasing the number of buckets on join attributes sharply decreases total query execution time, client execution time, and server execution time. Decryption time at the client represents the dominant component of total client-side execution time.

Coverage note — No substantial contributed material was omitted. All core mechanisms including relation encryption, attribute mapping functions, predicate condition translation, split execution of relational operators, query rewriting heuristics, and TPC-H experimental findings are covered.

References

1.AES. Advanced Encryption Standard. National Institute of Science and Technology, FIPS 197, 2001.
2.D. Song and D. Wagner and A. Perrig. Search on encrypted data. In Proc. of IEEE SRSP, 2000.
3.DES. Data Encryption Standard. FIPS PUB 46, Federal Information Processing Standards Publication, 1977.
4.H. Garcia-Molina, J. Ullman, and J. Widom. Database Systems: The Complete Book. Prentice Hall, 2002.
5.H. Hacıgşumüş, B. Iyer, C. Li, and S. Mehrotra. Executing SQL over Encrypted Data in Database-Service-Provider Model. Technical Report TR-DB-02-02, Database Research Group at University of California, Irvine, 2002.
6.H. Hacıgşumüş, B. Iyer, and S. Mehrotra. Providing Database as a Service. In Proc. of ICDE, 2002.
7.Y. E. Ioannidis and V. Poosala. Histogram-based approximation of set-valued query answers. In Proc. of VLDB, pages 174–185, 1999.
8.H. V. Jagadish, H. Jin, B. C. Ooi, and K.-L. Tan. Global optimization of histograms. In Proc. of ACM SIGMOD, 2001.
9.G. Piatatetsky-Shapiro and C. Connell. Accurate estimation of the number of tuples satisfying a condition. In Proc. of ACM SIGMOD, 1984.
10.R. L. Rivest, L. M. Adleman, and M. Dertouzos. On Data Banks and Privacy Homomorphisms. In Foundations of Secure Computation, pages 169–178, 1978.
11.R. L. Rivest, A. Shamir, and L. M. Adleman. A method for obtaining digital signatures and public key cryptosystems. Communications of the ACM, 21(2):120–126, 1978.
12.B. Schneier. Description of a new variable-length key, block cipher (blowfish), fast software encryption. In Cambridge Security Workshop Proceedings, 1994.
13.A. Silberschatz, H. F. Korth, and S. Sudarshan. Database System Concepts, 3rd Edition. McGraw-Hill Book Company, 1997.
14.TPC-H. Benchmark Specification. http://www.tpc.org.
15.M. Winslett and J. D. Ullman. Jeffrey D. Ullman speaks out on the future of higher education, startups, database theory, and more. SIGMOD Record, 30(3), 2001.

Citation

MLA

Hacigümüş, H., et al. “Executing SQL over Encrypted Data in the Database-service-provider Model”. Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, 2002, pp. 216–27, https://doi.org/10.1145/564691.564717.

APA

Hacigümüş, H., Iyer, B., Li, C., & Mehrotra, S. (2002). Executing SQL over encrypted data in the database-service-provider model. Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, 216–227. https://doi.org/10.1145/564691.564717

Chicago

Hacigümüş, H., B. Iyer, C. Li, and S. Mehrotra. 2002. “Executing SQL over Encrypted Data in the Database-service-provider Model”. Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, 216–27. https://doi.org/10.1145/564691.564717.

Harvard

Hacigümüş, H. et al. (2002) “Executing SQL over encrypted data in the database-service-provider model”, Proceedings of the 2002 ACM SIGMOD international conference on Management of data. ACM, pp. 216–227. Available at: https://doi.org/10.1145/564691.564717.

Vancouver

1. Hacigümüş H, Iyer B, Li C, Mehrotra S (2002) Executing SQL over encrypted data in the database-service-provider model. In: Proceedings of the 2002 ACM SIGMOD international conference on Management of data. ACM, pp 216–227

BibTeX

@inproceedings{Hacig_m__2002, series={SIGMOD/PODS02}, title={Executing SQL over encrypted data in the database-service-provider model}, url={http://dx.doi.org/10.1145/564691.564717}, DOI={10.1145/564691.564717}, booktitle={Proceedings of the 2002 ACM SIGMOD international conference on Management of data}, publisher={ACM}, author={Hacigümüş, Hakan and Iyer, Bala and Li, Chen and Mehrotra, Sharad}, year={2002}, month=June, pages={216–227}, collection={SIGMOD/PODS02} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Executing SQL over encrypted data in the database-service-provider model

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Relation Encryption and Storage Model

Knowl 2 — Partition, Identification, and Mapping Functions for Attribute Indexing

Knowl 3 — Condition Mapping Rules for Single-Attribute Predicates

Knowl 4 — Condition Mapping Rules for Join Predicates

Knowl 5 — Split Execution of Selection and Join Operators

Knowl 6 — Split Execution of Grouping, Aggregation, Sorting, and Duplicate Elimination Operators

Knowl 7 — Split Execution of Set Difference Operator via Left-Outer Join

Knowl 8 — Algebraic Query Splitting Framework

Knowl 9 — Experimental Performance of Split SQL Execution vs Partition Bucket Granularity

References

Citation

BibTeX

Access the Paper