  Searchable Encryption (SE) is a technique that allows Cloud Service Providers
(CSPs) 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 from CSPs. Unfortunately, most of them leak sensitive
information, from which the CSPs 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
(SSE) 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, access, and size patterns from CSPs. 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 test
it using the TPC-H benchmark dataset. Our evaluation results show the
feasibility and practical efficiency of P-McDb.
