Dynamic Structurally-Encrypted Database Solutions for Large-Scale Data Management
Kaiping Xue, Yutao Guo, Jingjiang Yang, Feng Liu, Chunyi Zhang, Feng Wang, Qibin Sun, Jun Lu · IEEE Transactions on Dependable and Secure Computing · 2025
The widespread adoption of cloud storage has raised considerable data privacy concerns for outsourced databases. In recent years, Structured Encryption (STE) has emerged as a promising solution to build encrypted databases that efficiently handle queries while preserving privacy through underlying structures called Encrypted Multi-Maps (EMMs). However, current STE-based schemes primarily focus on static settings, and their direct extensions to dynamic settings introduce significant challenges in client storage overhead and update efficiency with join condition. In this paper, we present an efficient dynamic encrypted database scheme supporting large-scale data. To address the challenges in dynamic settings, we first propose a novel dynamic EMM design with constant client storage that utilizes a global counter to reduce client storage overhead. We then introduce an algorithm for dynamically handling join queries based on tags generated from values of the join attribute, significantly reducing update overhead. We implement our scheme and conduct comparative analyses with existing dynamic STE schemes. The experimental results demonstrate that our scheme offers significant advantages in terms of client storage overhead and update performance.