
We address the problem of dynamic symmetric searchable encryption (DSE), where encrypted data is stored on untrusted servers, enabling efficient search and updates while minimizing information leakage. Our focus is on achieving strong privacy notions—forward privacy (preventing linking updates to past queries) and backward privacy (limiting information about deleted entries in future queries). We introduce three novel schemes to address these challenges: Mitra, a lightweight and efficient scheme with Type-II backward privacy; Orion, the first implemented scheme with stronger Type-I backward privacy; and Horus, which improves query efficiency by reducing communication overhead while maintaining Type-III backward privacy. In addition to these, we propose OSSE, the first DSE scheme to achieve asymptotically optimal search time, significantly improving performance over prior work. We also develop LLSE, a scheme that, while slightly less optimal than OSSE, achieves faster deletions, smaller server storage, and still outperforms existing solutions. Furthermore, we extend our work to multi-user DSE (DMUSSE) by introducing µSE, the first provably secure scheme in this setting, with support for blockchain-based verifiability.

Researcher @ Huawei Hong Kong Research Center