RO(SE)²: Search-Efficient Robust Searchable Encryption With Forward and Backward Security

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 propose RO(SE)², a novel robust DSSE scheme that simultaneously achieves ro bustness, forward-and-Type-III-backward security, and optimal search performance. RO(SE)² introduces 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)² employs a two-layer encryption mechanism to ensure forward security and supports efficient search result verification through its verifiable extension, RO(SE)²-v. Rigorous security analysis proves that RO(SE)² can achieve not only robustness, forward and backward security but optimal search efficiency as well. Comparative analysis reveals that RO(SE)² outperforms existing robust schemes in terms of search performance, while RO(SE)²-v outperforms the state-of the-art verifiable robust schemes in verification performance.