Secure and efficient search over outsourced databases

The current trend towards outsourcing data storage and management to the cloud has largely been driven by the perceived simplicity and cost-effectiveness. Encrypting sensitive data before outsourcing preserves data privacy, but poses an obstacle to delegate search capabilities to the server. Symmetric searchable encryption (SSE) addresses this issue by allowing an untrusted server to answer queries over encrypted data while protecting the confidentiality of plaintext data and queries. The core of SSE is to meet three design goals, including a strong security guarantee, an efficient search performance and supporting rich types of queries. Usually, an SSE scheme needs to trade in security or efficiency for supporting more expressive queries. In this thesis, we study how to strike trade-offs among these design goals. As a motivation of strong security notions, we first study the potential risks of constructing SSE schemes based on an ad hoc security notion for the purpose of efficiently performing more expressive queries. We demonstrate several previous unknown security risks of widely used ad hoc secure SSE schemes to show that ad hoc security notion leaves room for unpredicted information leakage. To address this problem, our next two contributions focus on constructing practical SSE schemes with a formal security definition. Ciphertext indistinguishability is a notable formal security notion. SSE schemes achieving this notion can provide a strong security guarantee, but often result in less efficiency or reduced query expressiveness. In order to support equality conjunction queries in a sub-linear search performance, we argue that this notion is not necessary in practice and formalize a relaxed notion of ciphertext indistinguishability. We propose a novel SSE scheme for equality conjunction queries that meets the relaxed notion while minimizing the client and communication cost. Most SSE schemes achieving ciphertext indistinguishability leak access pattern (i.e., what documents are searched) and search pattern (i.e., whether two queries pertain to the same keyword) for efficiency. However, these patterns could lead to serious security risks. Our final contribution is the first practical dynamic SSE scheme that hides access and search patterns for single key search.