EncDB-FR$^{3}$3: An Encrypted Database With Fault Recovery and Rollback Resistance

Data breaches are the most common security challenges in cloud databases. Due to the lack of control over the underlying infrastructure of cloud databases, data owners can only rely on the trustworthiness and management capabilities of the cloud service provider for data security. This work introduces EncDB-FR<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$^{3}$</tex-math></inline-formula> – a novel encrypted database specifically designed for cloud scenarios. The primary focus of EncDB-FR<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$^{3}$</tex-math></inline-formula> is to address the vulnerabilities inherented in cloud service environments, particularly those posed by malicious entities with control over the software stack. By leveraging Trusted Execution Environments (TEE), EncDB-FR<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$^{3}$</tex-math></inline-formula> ensures the confidentiality, integrity, and freshness of data. The system architecture of EncDB-FR<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$^{3}$</tex-math></inline-formula> integrates a secure B+ Merkle tree structure along with a so-called <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">unique transaction commit process</i>. This process combines a trusted monotonic counter with redo logs to ensure robustness against rollback attacks while maintaining database durability. According to commonly used database benchmarks, EncDB-FR<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$^{3}$</tex-math></inline-formula> achieves strong security with low overhead, addressing a crucial gap in existing cloud database solutions. Compared to the widely adopted <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">FieldEnc</monospace> implementation (AE, SIGMOD'20, StealthDB, PoPETs'19, and Operon, VLDB'22), EncDB-FR<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$^{3}$</tex-math></inline-formula> demonstrates superior performance with a 1.16× throughput, a 0.85× average latency. Besides, the disk space utilized by EncDB-FR<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$^{3}$</tex-math></inline-formula> is only 10% of that used by <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">FieldEnc</monospace> w.r.t. the same dataset. Furthermore, to the best of our knowledge, EncDB-FR<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$^{3}$</tex-math></inline-formula> is the only disk-based encrypted relational database that can withstand rollback attacks.