Source-linked AI summary
StealthDB: a Scalable Encrypted Database with Full SQL Query Support
Alexey Gribov, Dhinakaran Vinayagamurthy, Sergey Gorbunov
TL;DR
Encrypted databases face trade-offs between functionality, performance, and leakage, while complete SQL support at scale remains limited. StealthDB uses Intel SGX to protect encrypted database operations and reports full TPC-C support with a 30% throughput reduction at scale.
Problem
Complete SQL support in encrypted databases is difficult, and only a handful of systems have been evaluated at scale despite research on subsets of SQL operations.
Source: §4.1 · p. 5Method
StealthDB uses Intel SGX enclaves, encrypted datatypes, and data-oblivious operators while making minimal changes to the underlying DBMS.
Source: StealthDB · p. 2Results
StealthDB reports a 30% throughput reduction and approximately 1 ms latency overhead over an unencrypted DBMS for TPC-C at W = 16 and more than 10M rows (2 GB plaintext).
Source: StealthDB · p. 3Takeaways & Limitations
StealthDB supports full SQL and large transactional workloads on newer-generation Intel CPUs with minimal DBMS changes.
Source: StealthDB · p. 3, §9 · p. 15Cache-based side channels are inherent to x86 and require Intel patching, while StealthDB generally does not protect against active attacks.
Source: §6 · p. 11
Abstract
from arXiv · showhide
Encrypted database systems provide a great method for protecting sensitive data in untrusted infrastructures. These systems are built using either special-purpose cryptographic algorithms that support operations over encrypted data, or by leveraging trusted computing co-processors. Strong cryptographic algorithms (e.g., public-key encryptions, garbled circuits) usually result in high performance overheads, while weaker algorithms (e.g., order-preserving encryption) result in large leakage profiles. On the other hand, some encrypted database systems (e.g., Cipherbase, TrustedDB) leverage non-standard trusted computing devices, and are designed to work around the architectural limitations of the specific devices used. In this work we build StealthDB - an encrypted database system from Intel SGX. Our system can run on any newer generation Intel CPU. StealthDB has a very small trusted computing base, scales to large transactional workloads, requires minor DBMS changes, and provides a relatively strong security guarantees at steady state and during query execution. Our prototype on top of Postgres supports the full TPC-C benchmark with a 30% decrease in the average throughput over an unmodified version of Postgres operating on a 2GB unencrypted dataset.
1 Introduction
StealthDB addresses the challenge of supporting complete encrypted database workloads in untrusted clouds without extensive DBMS changes. It builds on SGX and reports full TPC-C support with a 30% throughput reduction at scale.
1 Introduction
- Encrypted database designs trade off security, functionality, performance, and intrusiveness, while only a handful of systems support complete functionality and have been evaluated at scale.CryptDB uses property-preserving encryption, which can leak extensive information on real-world datasets; other approaches may have limited functionality or high computational and storage overheads.Source: §1 · pp. 1–2
- SGX offers enclave-based protection on recent Intel CPUs, but its secure-memory bound, side-channel exposure, and enclave-transition overhead make a direct DBMS port impractical.The design goal is to work around these constraints without extensive changes to the underlying DBMS.Source: §1 · p. 2
StealthDB
- StealthDB uses AES-CTR encryption, an enclave query parser, encrypted datatypes, and data-oblivious operators to support SQL queries over encrypted data.It also encrypts index-file pages before writing them to disk; the changes are described as non-intrusive and let the system inherit underlying DBMS functionality.Source: StealthDB · pp. 2–3
- StealthDB’s stated leakage profile distinguishes snapshot access, which reveals database shape and recent query-log information, from persistent access, which also reveals index inequalities and query access patterns.Its TCB comprises the processor, enclave code, SGX hardware, and attestation procedure.Source: StealthDB · p. 3
- 30% throughput reduction and approximately 1 ms latency overhead over an unencrypted DBMS for TPC-C at W = 16 and more than 10M rows (2 GB plaintext).The Postgres implementation supports large transactional workloads with minimal DBMS changes.Source: StealthDB · p. 3
2 Background on Intel SGX
Intel SGX isolates trusted code and data in enclaves and provides sealing and attestation functions. Its protections do not eliminate software side channels, so applications must account for data-dependent access patterns.
2 Background on Intel SGX
- SGX lets developers isolate code in enclaves and requires them to partition applications into enclave and untrusted code with an I/O interface between them.Security is rooted in a trusted processor, not in trust in the remote software stack.Source: §2 · pp. 3–4
- Sealing encrypts and authenticates data passed to the host, while attestation reports enclave code, static data, metadata, and computation outputs.The passages distinguish local and remote attestation; attestation can also support establishing secure communication channels.Source: §2 · p. 4
- SGX does not prevent software side channels, including cache, scheduling, branch-predictor, and page-level access-pattern attacks.Application developers must design data-independent memory accesses for protection against page-level access-pattern leakage; Intel patches address some other attacks.Source: §2 · p. 4
3 Platform Overview
The usage model places an encrypted SQL database on a remote server equipped with a secure processor, with owners and clients attesting enclaves before transferring sensitive material. The threat model distinguishes adversaries by access and duration.
3.1 Usage Model.
- A data owner stores data on a remote untrusted SQL server, authorizes clients, and transfers secrets to server enclaves after successful attestation.Clients authenticate with credentials and issue permitted queries over secure channels.Source: §3.1 · p. 4
3.2 Threat Model
- StealthDB’s threat model assumes passive adversaries that observe memory, disk, and communications but do not alter execution or inject code.The model considers whether adversaries monitor disk alone or both memory and disk.Source: §3.2 · pp. 4–5
- Threats also vary by duration: snapshot access is distinguished from persistent access to memory and disk.Examples of snapshot attacks include memory dumps, cold-boot attacks, disk theft, and smash-and-grab access after system compromise.Source: §3.2 · p. 5
4 Designing an Encrypted DB
The section sets goals for a scalable encrypted database with broad SQL support and reasonable leakage, then compares SGX designs that vary which operations run inside an enclave. Its experiments expose performance costs of enclave-based designs and motivate executing primitive operators on individually encrypted values.
4.1 Design Goals
- StealthDB targets scalable arbitrary-query support with reasonable leakage, prioritizing performance for large transactional workloads amid a security–performance trade-off.Its goals include complete SQL support and minor DBMS modifications that preserve underlying DBMS properties.Source: §4.1 · p. 5
4.2 Designing an Encrypted DB from SGX
- Across the three designs, data is encrypted on disk and the choices differ in how queries execute over it.The section uses micro-experiments to compare these design choices and inform the system design developed later.Source: §4.2 · p. 5, Figure 2 · p. 6
- Running the entire DBMS inside an enclave faces absent IO/syscall support and a 90 MB working-memory limit, resulting in heavy transactional-workload overheads.The authors note that larger future enclaves would still face Merkle-tree integrity-protection costs; this design may offer better confidentiality once SGX side channels are addressed.Source: §4.2 · p. 6
- Enclave deserialization takes around 3× when the dataset fits inside an enclave and rises to 9× for large datasets.This second design leaves most DBMS components outside but runs query execution logic inside; it also faces secure-memory limits, side-channel concerns, and difficult DBMS partitioning.Source: Figure 3 · p. 6, §4.2 · p. 6
- The third design keeps the DBMS and individually encrypted data outside the enclave, bringing individual values in for primitive operations.This keeps enclave code/data a small constant and requires changes only to primitive operators, but leaks relationships between encrypted values during query execution.Source: §4.2 · pp. 5–7
- Up to 100× overhead occurs for encrypted B-tree searches with enclave comparisons; exitless shared-queue communication reduces this overhead by 5×–10×.Loading the entire tree into an enclave does not scale to larger datasets, though it performs well when the tree fits entirely inside one.Source: Figure 4 · p. 7, §4.2 · p. 7
5 Architecture
StealthDB adds enclaves and encrypted datatypes around an otherwise largely unmodified DBMS. It protects data and query processing through encryption, enclave operations, and additional index and log protections.
5 Architecture
- The architecture keeps most components on top of an unmodified DBMS, adding enclaves and a server-side I/O layer that redirects requests but remains outside the SGX TCB.The layer also wraps enclave I/O requests and system calls.Source: §5 · p. 7, §5.2 · p. 8, Figure 5 · p. 8
5.1 Database creation
- Database owners mark sensitive columns with encrypted datatypes, such as enc_int4 for encrypted integers, whose values StealthDB encrypts using AES-CTR.The owner specifies which table columns use encrypted datatypes when creating the schema.Source: §5.1 · p. 7, Figure 6 · p. 7
5.2 DBMS Initialization
- During initialization, StealthDB creates Auth, PreProcessor, and Ops enclaves; Auth generates a 128-bit master key and transfers it over attested secure channels for sealing by the recipient enclaves.The owner also transfers master credentials, client credentials, and access policies to Auth over an attested secure channel.Source: §5.2 · pp. 7–8
5.3 Client authentication
- Clients attest Auth, authenticate with credentials over a secure channel, and receive a session key that Auth transfers with their ID to PreProcessor.Auth verifies credentials against its sealed client database.Source: §5.3 · p. 9, Figure 7 · p. 9
5.4 Query execution
- PreProcessor decrypts authorized client queries, encrypts constants for encrypted columns, and passes the structurally unchanged query to the DBMS; the design supports an unmodified query driver.StealthDB adds primitive-operator functions for encrypted datatype combinations as Postgres extensions.Source: §5.4 · p. 9
- Primitive operations on encrypted datatypes run in Ops, which decrypts inputs, applies the operator, and optionally encrypts the result; an exit-less queue avoids per-call context switches.The design also permits datatype conversions and computations between encrypted and unencrypted datatypes, with encrypted output available to avoid leaking information about encrypted inputs.Source: §5.4 · p. 10
5.5 Encrypting indexes
- StealthDB re-encrypts indexed values to reduce linkage and encrypts index pages on disk; persistent observation during index creation and use still exposes ORE-level security on indexed columns.The Postgres page-encryption change adds three lines of code; it does not add query-execution overhead.Source: §5.5 · pp. 10–11
5.6 Extensions
- StealthDB can encrypt query logs on disk; its current key-management design uses one master key for all data values and can be extended to support different keys by client or column.The authors state that encrypting individual table-data pages yields no concrete security improvement because table items are already encrypted.Source: §5.6 · p. 11
6 Security evaluation
StealthDB evaluates leakage against passive or semi-honest adversaries and addresses some SGX side channels with oblivious primitive operations. Its stated protections vary by adversary access and do not cover active attacks or query-result integrity.
6 Security evaluation
- Oblivious primitive operations address page-level and other software side channels, but StealthDB does not protect against active attacks and cache-based side channels require Intel patches.The system also does not provide query-result integrity or confidentiality against an actively malicious adversary with side-information on plaintext values.Source: §6 · p. 11
6.1 Leakage profile
- The leakage analysis assumes secure SGX attestation, computation confidentiality and integrity, secure channels, and sealing.The analysis distinguishes database shape, query leakage, and leakage from logs and miscellaneous DBMS structures.Source: §6.1 · p. 12
- After initialization and before any query, StealthDB leaks at most the database's initial shape, unlike OPE- or ORE-based designs that reveal value ordering.The stated comparison is with designs leaking the '<' relation among values in encrypted columns.Source: §6.1 · p. 12
- A snapshot adversary learns at most the database shape at the latest relevant epoch and query-execution leakage since then; encrypted in-memory logs and non-revealing log size reduce this bound to the current shape.The query leakage is bounded by plaintext outputs of Ops invocations.Source: §6.1 · pp. 12–13
- A persistent semi-honest adversary learns the database shape over time and query leakage, defined as the union of plaintext outputs from Ops invocations.The authors state that miscellaneous structures and accessed database parts reveal no more than these quantities.Source: §6.1 · p. 13
7 Implementation and Performance
StealthDB is implemented as a Postgres extension with enclave-executed functions and oblivious operations. Its TPC-C evaluation reports throughput and latency overheads against unmodified Postgres, with a larger throughput cost when IDs are encrypted.
7.1 Implementation details
- StealthDB adds SQL functions, encrypted datatypes, operators, and index support to Postgres 9.6 as an extension; enc_int4_cmp compares encrypted integers and returns {-1, 0, 1}.The function executes in an enclave, while the server-side query pre-parser encrypts query values; enclave operations are made oblivious using AES-NI and CMOV.Source: §7.1 · p. 13
7.2 Performance evaluation
- 4.7% overhead at W = 1 and around 30% at W = 16; Figure 11 compares TPC-C throughput for StealthDB and Postgres across scale factors.The experiments leave TPC-C IDs unencrypted.Source: Figure 11 · p. 14, §7.2 · p. 14
- Experiments compare throughput and latency against unmodified Postgres 9.6 on a TPC-C database of about 10 million rows; encryption increases its size from about 2GB to 7GB.The experiment used 1–10 clients and a single-threaded enclave.Source: §7.2 · pp. 13–14
- About 3x lower throughput and 3.6 times the latency result when TPC-C IDs are encrypted with AES-CTR, compared with StealthDB using unencrypted IDs.The paper notes that the IDs are counters, so encrypting them offers no concrete security advantage.Source: §7.2 · p. 14
- 7.2 milliseconds at the 90th percentile corresponds to 22% latency overhead over unmodified Postgres; Table 1 and Figure 12 compare latency statistics.The latency measurement at W = 16 includes the query pre-parser.Source: Table 1 · p. 14, Figure 12 · p. 14, §7.2 · p. 14
8 Related Work
Related encrypted-database systems trade among security, SQL coverage, performance, and hardware assumptions. StealthDB is positioned against these approaches through its complete TPC-C evaluation and use of current-generation SGX hardware.
Related systems
- Cipherbase achieves about 10% better throughput than ours but skips two TPC-C transactions; our complete benchmark finds these have the highest latency overheads, and we achieve 4× lower latency over the FPGA implementation.Source: §8 · p. 14
SGX and trusted-hardware systems
- TrustedDB places large portions of the DBMS in a trusted zone, while ObliDB requires extensive DBMS changes and does not scale well for transactional workloads.EnclaveDB assumes gigabyte-scale enclaves and ignores access-pattern and other side-channel attacks.Source: §8 · pp. 14–15
Related systems
- CryptDB uses a hybrid of encryption schemes to support a subset of SQL functionality; its throughput decrease is similar to ours only for individual TPC-C transaction queries on a 20× smaller dataset.Source: §8 · p. 15
SGX and trusted-hardware systems
- HardIDX [21] prototypes oblivious B+ tree range searches for static databases, requiring the client to generate the full index locally; StealthDB instead builds a complete encrypted database system.The authors say HardIDX ideas could be incorporated if StealthDB supported only static databases and powerful clients.Source: §8 · p. 15
Cryptographic approaches
- Cryptographic systems such as OSPIR-OXT, SisoSPIR, and BLIND SEER provide provable security for subsets of functionality, while fully homomorphic encryption remains impractical.The paper cautions that real-world security also depends on implementation, metadata, and log-file contents.Source: §8 · p. 15
9 Conclusion
StealthDB is presented as a scalable encrypted cloud database with full SQL support and strong end-to-end security. Its reported performance cost is a 30% throughput decrease and approximately 1 ms latency increase; several security and workload questions remain open.
Conclusion
- StealthDB supports full SQL queries in a scalable encrypted cloud database system.The system can be implemented on newer-generation Intel CPUs.Source: §9 · p. 15
- The reported cost is a 30% throughput decrease and approximately 1 ms latency increase, alongside strong end-to-end security guarantees.Source: §9 · p. 15
- Supporting analytical workloads, reducing leakage, and protecting against active adversaries remain open questions under the design principles.The implementation source code is open-sourced.Source: §9 · p. 15
A Security addendum
The addendum defines encrypted-database security by comparing real and ideal experiments. Its formal setup models adversaries, trusted-hardware interfaces, and simulator-provided leakage.
A.1 Formal definition of security
- The security definition requires that, for every admissible adversary, an efficient simulator makes the real and ideal experiments indistinguishable.The stated criterion is that the difference in the adversary’s output probabilities is negligible.Source: §A.1 · p. 17
- The adversary is split into Adv1, which runs the system, and Adv2, which observes information and outputs a bit; Adv2 may take a snapshot or observe persistently.Adv1 may be semi-honest or actively malicious.Source: §A.1 · p. 17
- The trusted-hardware oracle exposes Auth(), PreProcessor(encquery), and Ops({input}, op); the simulator obtains query leakage Q from L.The simulator emulates the oracle in the ideal experiment.Source: §A.1 · p. 17
A.2 Security of K during StealthDB execution
StealthDB protects the confidentiality and integrity of its master key throughout execution. Its enclave-attestation and query-processing checks also restrict key distribution and query execution to valid components and authorized clients.
A.2 Security of K during StealthDB execution
- StealthDB’s master key remains confidential and integral throughout execution, with only its length exposed during enclave transfers.Auth generates the key and transfers it to correctly measured PreProcessor and Ops enclaves through locally attested secure channels; AES use and disk sealing are also described as protected.Source: §A.2 · p. 18
- Queries reaching the DBMS satisfy the requesting client’s access policies.Auth establishes sessions only for clients with valid credentials, and PreProcessor checks each query before proceeding.Source: §A.2 · p. 18
A.3 Correctness of Claim 6.2
The appendix argues that simulations can reproduce the leakage available to snapshot and query-execution adversaries, under stated assumptions about deterministic execution and log sizes.
A.3 Correctness of Claim 6.2
- For Claim 6.2, the simulator matches the database shape at snapshot time and makes the Real and Ideal experiments indistinguishable, assuming log size reveals no sensitive information.It encrypts zeros with the observed shape, rewrites the database at t′, and keeps query logs and other structures consistent; the argument also assumes deterministic execution and encrypted logs and structures in memory.Source: §A.3 · pp. 18–19
A.4 Correctness of Claim 6.3
- For Claim 6.3, the simulator uses leakage-observed shape and queries to reproduce plaintext outputs and substitutes encrypted zeros for encrypted outputs.The passage attributes indistinguishability of the encrypted database and encrypted outputs to semantic security.Source: §A.4 · p. 19
B Concrete leakage profiles
StealthDB’s concrete leakage depends on the operation: arithmetic and string processing hide values apart from lengths, while relational indexes expose comparison information and access patterns.
B Concrete leakage profiles
- A TPC-C warehouse update using addition reveals no values from the w_ytd column during query execution.The example adds a constant to w_ytd for a row selected by w_id.Source: B Concrete leakage profiles · p. 19
- String operations such as substring and wildcards reveal only encrypted input and output lengths.Lengths are disclosed up to a multiple of 128.Source: B Concrete leakage profiles · p. 19
- Arithmetic operations reveal no intermediate values beyond encrypted-input and output lengths, while relational operations can expose index comparisons and accessed-row patterns.For indexed queries, the leakage depends on the explored index portions and DBMS execution and log-maintenance procedures.Source: B Concrete leakage profiles · p. 19