Rethinking Leakages in Dynamic Encrypted Database: Exploitation, Quantification, and Mitigation

Description

Encrypted databases promise to safeguard against increasing threats of data breaches and privacy infringements. Despite the progress, recent research highlights a notable concern: the seemingly harmless leakage patterns, officially allowed within the encrypted search algorithms, can be exploited to uncover queries and compromise the system's privacy assurances. Although various countermeasures have been proposed, almost all prior studies are centered around static databases, leaving the understanding of leakages in more challenging dynamic settings, where operations like addition and deletion are allowed, largely underexplored. Our preliminary results show there are inherent structural limitations in dynamic encrypted search constructions, making encrypted databases in dynamic operations also susceptible to leakage-abuse vulnerabilities previously found only in static scenarios. These insights introduce entirely new perspectives for rethinking the security of encrypted databases, particularly in dynamic settings. In this project, we will revisit the leakages in dynamic encrypted databases, with new theories, algorithms, and schemes on leakage exploitation, privacy risk quantification, and the corresponding mitigation strategies. Our plan includes three tasks: 1) Investigating why leakages in current dynamic encrypted search schemes are fundamentally exploitable. We will review cutting-edge dynamic constructions and assess the severity of leakages therein under various threat models. Given our insight on the inherent structural limitations, we expect to bridge the security gap between dynamic encrypted search and static constructions and further reconstruct the relationships between keywords and queries. Following this roadmap, we hope to lay a solid groundwork to understand the privacy risks of dynamic encrypted database and establish effective countermeasures. 2) Quantifying the privacy risks of leakage exploitation. Our initial findings highlight the inadequacy of conventional security notions: only capturing revealed leakages in dynamic encrypted databases is insufficient, as it does not convey any privacy exposure risks. Accordingly, we will develop a quantifiable privacy estimator using information theory to not just capture leakages from dynamic encrypted databases but further assess their potential privacy risks. We will then utilize this estimator to build a revamped security notion for dynamic encrypted databases. 3) Establishing provably secure mitigation strategies. With findings from previous two tasks, we will focus on developing tailored countermeasures and security enhancements for dynamic encrypted databases. These include both proactive leakage obfuscation strategies measured by the privacy estimator, and more reactive strategies with on-demand database reconstructions under the continuous privacy risk monitoring. We believe our research will ultimately contribute to more robust and resilient encrypted database systems that support data dynamics.