Designing Leakage-Aware Mechanisms for Encrypted Search Systems

Abstract

Over the past two decades, encrypted search has evolved significantly, transitioning from static keyword matching to dynamic and sophisticated search systems. However, these systems exhibit inherent leakage patterns that were initially deemed necessary for efficient search processes and considered benign. Yet, these patterns have now become vulnerable to exploitation through leakage-abuse attacks, enabling adversaries to reconstruct the entire encrypted database with minimal observation of search interactions. Consequently, the design focus of encrypted search systems has shifted from being functionality-driven to security-driven. Despite the existing standard security notions being adept at formulating leakage, they fall short in adequately assessing the potential impacts of such leakage. Therefore, there arises a critical need to devise leakage-aware mechanisms that can comprehensively interpret, proactively estimate, and reactively intercept leakage to enhance the reliability of encrypted search systems.

This thesis delves into the exploration of three leakage-aware mechanisms aimed at proactively or reactively mitigating leakage in encrypted search systems. Each mechanism has a detailed explanation of its rationale, implementation, and evaluation. First, we propose a proactive encrypted query framework tailored for collaborative data analytics scenarios. It establishes a perturbed leakage profile before system deployment, emphasizing the coordination of dynamic databases and rich query functionality such as filtering, linking, and aggregation. Secondly, we propose a query control framework to reactively quantify and mitigate the long-term leakage post-system deployment. This framework focuses on conducting a fine-grained analysis of a particular query type, specifically zooming in on the range query. Thirdly, we propose a hybrid framework that amalgamates proactive leakage perturbation and reactive query control strategies, aiming to provide improved security and execution performance throughout the system’s life cycle.

Our research showcases the feasibility and necessity of seamlessly integrating proactive and reactive leakage mechanisms to enhance the security of encrypted search systems without compromising stringent functionalities and performance requirements. By establishing a solid groundwork for leakage analysis, we posit that our mechanisms play a pivotal role in driving the development of more secure and privacy-enhanced encrypted search systems in the future.

Date of Award	24 Apr 2025
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Cong WANG (Supervisor)