Paper 2021/489

ROSE: Robust Searchable Encryption with Forward and Backward Security and Practical Performance

Peng Xu, Willy Susilo, Wei Wang, Tianyang Chen, Qianhong Wu, and Hai Jin


Dynamic searchable symmetric encryption (DSSE) has been widely recognized as a promising technique to delegate update and search queries over an outsourced database to an untrusted server while guaranteeing the privacy of data. Many efforts on DSSE have been devoted to obtaining a good tradeoff between security and performance. However, it appears that all existing DSSE works miss studying on what will happen if the DSSE client issues irrational update queries carelessly, such as duplicate update queries and delete queries to remove non-existent entries (that have been considered by many popular database system in the setting of plaintext). In this scenario, we find that (1) most prior works lose their claimed correctness or security, and (2) no single approach can achieve correctness, forward and backward security, and practical performance at the same time. To address this problem, we study for the first time the notion of robustness of DSSE. Generally, we say that a DSSE scheme is robust if it can keep the same correctness and security even in the case of misoperations. Then, we introduce a new cryptographic primitive named key-updatable pseudo-random function and apply this primitive to constructing ROSE, a robust DSSE scheme with forward and backward security. Finally, we demonstrate the efficiency of ROSE by analyzing its computation and communication complexities and testing its search performance. The experimental results show that ROSE has a very efficient search performance over a large dataset.

Available format(s)
-- withdrawn --
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.IEEE TIFS
Searchable Symmetric EncryptionForward and Backward SecurityRobustnessKey-Updatable Pseudo-Random Function
Contact author(s)
xupeng @ mail hust edu cn
wsusilo @ uow edu au
viviawangww @ gmail com
chentianyang @ mail hust edu cn
qianhong wu @ buaa edu cn
2022-03-08: withdrawn
2021-04-16: received
See all versions
Short URL
Creative Commons Attribution
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.