Title: Searchable Symmetric Encryption with Tunable Leakage Using Multiple Servers
Authors: Xiangfu Song, Dong Yin, Han Jiang and Qiuliang Xu
Abstract: Searchable symmetric encryption has been a promising primitive as it enables a cloud user to search over outsourced encrypted data efficiently by only leaking small amount of controllable leakage. However, recent leakage-abuse attacks demonstrate that those stand leakage profiles can be exploited to perform severe attacks - the attacker can recover query or document with high probability. Ideal defending methods by leveraging heavy cryptographic primitives, e.g. Oblivious RAM, Multiparty Computation, are still too inefficiency for practice nowadays. In this paper, we investigate another approach for countering leakage-abuse attacks. Our idea is to design SSE with tunable leakage, which provides a configurable way for trade-off between privacy and efficiency. Another idea is to share the leakage among multiple non-collude servers, thus a single server can only learn partial, rather than the whole leakage. Following the ideas, we proposed two SSE schemes. The first scheme uses two servers and is static, which serves as the first step to emphasize our design methodology. Then we propose a dynamic SSE scheme, by additionally use a third server to hold dynamic updates. We demonstrate that the leakage for the third server is only partial update history, a newly defined leakage notion that leaks limited information rather than the whole update history. Our schemes provide stronger security that hides search/access pattern in a tunable way as well as maintains forward and backward privacy. We also report the performance of our constructions, which shows that both schemes are efficient.
