SAP-SSE: Protecting Search Patterns and Access Patterns in Searchable Symmetric Encryption

Searchable symmetric encryption (SSE) enables users to search over encrypted documents in untrusted clouds without leaking the search keywords to the clouds. Existing SSE schemes achieve high search efficiency at the expense of leaking access patterns and search patterns, where clouds can recover a large percentage of queried keywords using the leaked access patterns and search patterns. To prevent clouds from recovering users' keywords, researchers have proposed a number of solutions to protect either search patterns or access patterns. However, none of them can protect both access patterns and search patterns. Moreover, existing SSE schemes cannot work in the generic database setting that allows multiple users to write or read over encrypted documents. In this paper, we propose an efficient searchable symmetric encryption scheme, called SAP-SSE, which protects both access patterns and search patterns in the generic database setting. The main idea of protecting search patterns is to leverage re-encryption cryptosystems to shuffle index entries over multiple clouds. To protect access patterns, we distribute secure indexes to multiple clouds and then propose an index redistribution protocol that allows users to renew index entries in clouds. Furthermore, SAP-SSE provides a configurable security policy to balance security and efficiency. Formal security analysis and experimental evaluation show that SAP-SSE can prevent pattern leakage with low overhead.

Automated summary

The proposed SAP-SSE scheme in this paper protects both access patterns and search patterns in a generic database setting by leveraging re-encryption cryptosystems to shuffle index entries over multiple clouds for protecting search patterns, and distributing secure indexes to multiple clouds along with an index redistribution protocol for protecting access patterns. Additionally, it provides a configurable security policy to balance security and efficiency while preventing pattern leakage with low overhead, as demonstrated by formal security analysis and experimental evaluation.