(2026-03) Efficient Compilers for Verifiable Dynamic Searchable Symmetric Encryption
2026-03-25
We construct compilers to generically transform any dynamic Searchable Symmetric Encryption (DSSE) scheme that is secure against a semi-honest server into one that is secure against a malicious servers, thus yielding a Verifiable dynamic SSE (VDSSE). Our compilers achieve optimal overheads while preserving forward and backward privacy, which are the standard and widely accepted security notions for DSSE.
We focus on optimizing communication overheads and client storage requirements. Our first compiler incurs communication overhead between the client and the server, which is optimal, while incurring mild storage overhead at the client. Our second compiler incurs storage overhead at the client while incurring mild communication overhead. Towards this, we define a new authenticated data structure called a set commitment and we provide an efficient instantiation of this primitive.
We prototype implement our compilers and report on their performance over real-world databases. Our experiments validate that our compilers incur concretely low overheads on top of existing semi-honest DSSE schemes, and yield practically efficient VDSSE schemes that scale to very large databases.