Trustworthy, Privacy-Preserving, and Functional Data Outsourcing Systems

Abstract

Data outsourcing systems, e.g., Dropbox, Google Drive, and iCloud have become essential in our daily lives. They can reduce the storage burden on user devices, which have limited storage capacity. Also, they serve as backup places for user data to prevent data loss due to hardware failures. However, data misuse and breaches remain serious concerns. Even when the cloud provider is trusted, attacks on storage servers have exposed user data, threatening user privacy and the reputation of corporations. This dissertation develops and implements trustworthy, privacy-preserving, and functional data outsourcing systems. The contributions consist of two pieces. First, we design and implement a Proof of Retrievability scheme named Porla, an efficient technique allowing the user to audit their data to ensure its intactness. Our work features an optimal audit-proof size and low end-to-end audit latency in comparison with prior work. Second, we develop a series of novel searchable encryption techniques achieving high security guarantees and performance in various threat and system models. In particular, we start by designing new schemes for multi-user searchable encryption, MAPLE and MUSES, using state-of-the-art cryptographic tools and emerging distributed computation algorithms. Our MAPLE and MUSES offer high security guarantees while optimizing search complexity in terms of computation and communication costs. However, they rely on distributed computation for secure search, which incur expensive deployment and maintenance cost. Therefore, we turn our direction to deal with the security and performance issues in public-key searchable encryption (PKSE) and hybrid searchable encryption (HSE), which can support multi-user settings in practice more naturally, such as email and messaging systems. To this end, we design Hermes, which simultaneous resolves many open problems in PKSE/HSE settings, including preventing keyword-guessing attacks, achieving user-efficient epoch-based forward privacy, and optimizing server computation cost for keyword search. Finally, we observe that mitigating pattern leakages in PKSE/HSE has remained an open and unexplored research problem. Applying differential privacy (DP) is a potential approach as it achieves single-round search and small user-side storage, but the state-of-the-art work using DP still suffers from significant overhead to be applicable for practical applications. Our final work FROST devises a new approach for applying DP in encrypted search, showing a significant advance in terms of performance and communication cost. All the aspects addressed in this dissertation are essential for building practical encrypted data outsourcing systems that achieve both high performance and strong security guarantees.