Abstract
Searchable Encryption (SE) is a technique that allows Cloud Service Providers to search over encrypted datasets without learning the content of queries and records. In recent years, many SE schemes have been proposed to protect outsourced data. However, most of them leak sensitive information, from which attackers could still infer the content of queries and records by mounting leakage-based inference attacks, such as the count attack and file-injection attack.
In this work, first we define the leakage in searchable encrypted databases and analyse how the leakage is leveraged in existing leakage-based attacks. Second, we propose a Privacy-preserving Multi-cloud based dynamic symmetric SE scheme for relational Database (P-McDb). P-McDb has minimal leakage, which not only ensures confidentiality of queries and records but also protects the search, intersection, and size patterns. Moreover, P-McDb ensures both forward and backward privacy of the database. Thus, P-McDb could resist existing leakage-based attacks, e.g., active file/record-injection attacks. We give security definition and analysis to show how P-McDb hides the aforementioned patterns. Finally, we implemented a prototype of P-McDb and tested it using the TPC-H benchmark dataset. Our evaluation results show that users can get the required records in 2.16 s when searching over 4.1 million records.