Paper 2024/1483

Making Searchable Symmetric Encryption Schemes Smaller and Faster

Abstract

Searchable Symmetric Encryption (SSE) has emerged as a promising tool for facilitating efficient query processing over encrypted data stored in un-trusted cloud servers. Several techniques have been adopted to enhance the efficiency and security of SSE schemes. The query processing costs, storage costs and communication costs of any SSE are directly related to the size of the encrypted index that is stored in the server. To our knowledge, there is no work directed towards minimizing the index size. In this paper we introduce a novel technique to directly reduce the index size of any SSE. Our proposed technique generically transforms any secure single keyword SSE into an equivalently functional and secure version with reduced storage requirements, resulting in faster search and reduced communication overhead. Our technique involves in arranging the set of document identifiers $\mathsf{db}(w)$ related to a keyword $w$ in leaf nodes of a complete binary tree and eventually obtaining a succinct representation of the set $\mathsf{db}(w)$. This small representation of $\mathsf{db}(w)$ leads to smaller index sizes. We do an extensive theoretical analysis of our scheme and prove its correctness. In addition, our comprehensive experimental analysis validates the effectiveness of our scheme on real and simulated data and shows that it can be deployed in practical situations.