DDR-SSE: Duplicated Retrieval of Documents for System-wide Secure Searchable Symmetric Encryption

Searchable Symmetric Encryption (SSE) schemes enable efficient keyword searches over encrypted documents at the cost of some leakage. An SSE scheme is said to be system-wide secure if it resists cryptanalysis by an adversary with access to leakage from retrieval of both encrypted indices and encrypted documents. The vast majority of state-of-the-art SSE schemes are, in fact, not system-wide secure (Gui et al., IEEE S&P 2023). Currently, the only efficient system-wide secure SSE scheme is SWiSSSE (Gui et al., PoPETS 2024). However, SWiSSSE requires a client state that is updated per query (which hinders adoption in various practical settings), and its leakage is hard to characterize precisely (thus making security analysis harder). In this paper, we present DDR-SSE -a practically efficient, system-wide secure SSE scheme that only requires a static client state, and has a simple leakage profile. Technically, we introduce a novel encrypted document retrieval scheme that uses duplicated document storage and randomized document retrieval to suppress access pattern leakage without compromising on practical efficiency. A remarkable feature of our scheme is its conceptual simplicity (unlike SWiSSSE, which uses an extremely involved document retrieval mechanism). We present a simulation-based security proof for DDR-SSE with respect to a rigorously formal system-wide leakage profile. Through extensive leakage cryptanalysis, we establish that DDR-SSE is resilient to query reconstruction attacks (even under "unrealistically" strong attack assumptions). Finally, we benchmark a prototype implementation of DDR-SSE and show that it scales smoothly to large databases of the size seen in real-world applications. schemes for keyword search can be broadly divided into two groups: static SSE schemes that do not allow updates to the document collection, and dynamic SSE schemes that allow the document collection to be updated on-the-fly. Leakage vs Efficiency. The main security goal of SSE is to ensure data and query privacy of the client by minimizing information "leakage" to the (untrusted) server. An ideal SSE scheme would be provably leakage-free; however, achieving this typically requires heavy cryptographic machinery such as Oblivious RAM (ORAM) [5, 6, 7, 8, 9, 10, 11] or Private Information Retrieval (PIR) [12, 13, 14, 15, 16] that are not practically efficient at the required scale (see Appendix B for a more detailed discussion). It is common in the SSE literature to design schemes that trade-off some leakage for gains in efficiency. The leakage can be formalised, and it can be proven that a given scheme leaks no more than some specified leakage. However, this leaves open the possibility of cryptanalytic attacks exploiting the leakage [17, 18, 19, 20, 21, 22, 23, 24, 25] . It is challenging to design practically efficient SSE schemes that also resist leakage cryptanalysis.