Highly Scalable Searchable Symmetric Encryption from NTRU Lattice Trapdoors

Searchable symmetric encryption (SSE) enables privacy-preserving query execution over symmetrically encrypted databases. In order to support realistic query executions over encrypted document collections, one needs SSE schemes capable of supporting both conjunctive and disjunctive keyword queries. Unfortunately, existing solutions are either practically inefficient (incur large storage overheads and/or high query processing latency), or are quantum-unsafe due to their inherent reliance on public-key cryptographic techniques based on discrete log-hard groups. In this paper, we present the first practically efficient SSE scheme with fast conjunctive and disjunctive keyword searches, compact storage, and security based on the (plausible) quantum-hardness of well-studied lattice-based assumptions. As a first stepping stone, we first introduce NTRU-OQXT – a highly compact NTRU lattice-based conjunctive SSE scheme that outperforms all existing conjunctive SSE schemes in terms of search latency. We then present an extension of NTRU-OQXT that additionally supports disjunctive queries. The extended scheme, which we call TWINSSENTRU−OQXT, is the first lattice-based practically efficient and highly compact SSE scheme capable of supporting both conjunctive and disjunctive queries, while also being plausibly quantum-safe. Technically, both schemes rely on a novel oblivious search protocol based on highly optimized Fast-Fourier trapdoor sampling algorithms over NTRU lattices. While such techniques have been used to design other lattice-based cryptographic primitives (such as digital signatures), they have not been applied before in the context of SSE. We present prototype implementations of both schemes, and experimentally validate their practical performance over a large real-world dataset. Our experiments demonstrate that both schemes support extremely fast query processing while scaling smoothly to large datasets. In fact, NTRU-OQXT achieves at least 2× faster conjunctive keyword searches as compared to all other conjunctive SSE schemes (including the best quantum-unsafe conjunctive SSE schemes), and substantially outperforms many of these schemes in terms of storage requirements. These efficiency benefits also translate to TWINSSENTRU−OQXT, which is practically competitive with the best quantum-unsafe SSE schemes capable of supporting both conjunctive and disjunctive queries.