RO(SE)2: Search-Efficient Robust Searchable Encryption With Forward and Backward Security
Xu Yang, Qiuhao Wang, Saiyu Qi, Ke Li, Yong Qi · IEEE Transactions on Computers · 2025
Dynamic searchable symmetric encryption (DSSE) enables clients to store encrypted data on untrusted servers while retaining the ability to search and update the data efficiently. However, most existing DSSE schemes are vulnerable to incorrect update queries, such as duplicated insertions or invalid deletions, which can compromise both security and availability. Although existing robust schemes have made progress in addressing these issues, they still suffer from significant search inefficiencies, particularly when handling large numbers of updates. To overcome these limitations, we proposeRO(SE)2, a novel robust DSSE scheme that simultaneously achieves robustness, forward-and-Type-III-backward security, and optimal search performance.RO(SE)2introduces a hierarchical binary tree structure combined with an oblivious map (OMAP) to handle incorrect updates during the update phase, eliminating the need for filtering during search queries and significantly improving search efficiency. Additionally,RO(SE)2employs a two-layer encryption mechanism to ensure forward security and supports efficient search result verification through its verifiable extension,RO(SE)2-v. Rigorous security analysis proves thatRO(SE)2can achieve not only robustness, forward and backward security but optimal search efficiency as well. Comparative analysis reveals thatRO(SE)2outperforms existing robust schemes in terms of search performance, whileRO(SE)2-v outperforms the state-of-the-art verifiable robust schemes in verification performance.