Towards Full Accounting for Leakage Exploitation and Mitigation in Encrypted Databases

Under active research for years, encrypted databases are considered as a primary line of defence against the ever-growing data and privacy breaches. They allow users to make confidential queries directly over encrypted data, reducing information disclosure to well-defined leakage profiles. Despite the fruitful progress on enriched query types and improved efficiency, encrypted databases have not yet achieved widespread adoption for commercialization, because they may not be as secure as claimed in practice. Recent studies revealed that the legitimately admitted leakage profiles, while seemingly innocent, can be exploited to recover the queries and eventually devastate the system's privacy guarantee. Several countermeasures were subsequently proposed to patch the exploitations, but still with limits in theoretical account on either security or efficiency. Moreover, today's scientific knowledge on how the well-defined leakage relates to the broader privacy risk is still lacking. Our preliminary findings have shown potentials to fill such knowledge gap, and, surprisingly, further suggest possible pathways towards stronger attacks and defences. These insights open up completely new perspectives for reasoning the security of encrypted databases.In this proposal, we will conduct systematic investigations on leakage exploitation and corresponding mitigation in modern encrypted searchable databases. Our plan involves two parts: 1) understanding why the leakage is fundamentally exploitable; 2) investigating how to harden encrypted databases accordingly. We begin with the investigation on new algebraic approaches to model the indexing information transformation between the original and encrypted databases, and explain the inherent privacy risks mathematically. Grounded on these theoretical results, we will then develop a systematic leakage-abuse attack procedure that aims to improve and generalize all existing ones. With these findings, we hope to further establish an information-theoretic framework to quantitatively measure the privacy risks and guide the design of effective mitigation techniques. In the second half, we will study how to refine the security definitions of existing encrypted search schemes, by formally capturing the security against attackers capable of mounting leakage-abuse attacks. We will then investigate proactive defence strategies, by designing self-adjustable probabilistic perturbation mechanisms, to construct encrypted databases with stronger security against generalised attacks. Besides, we will also explore a reactive protection strategy with possibly better efficiency, which avoids the cost of perturbation and on-demand rebuilds the encrypted database through privacy risk monitoring.Our results will establish theoretical foundations for exploring the fundamental security limit of encrypted databases, provide effective hardening techniques, and push forward the scientific frontier of this research area.