Paper 2021/1266

Update-Sensitive Structured Encryption with Backward Privacy

Zhiqiang Wu, Jin Wang, and Keqin Li


Many recent studies focus on dynamic searchable encryption (DSE), which provides efficient data-search and data-update services directly on outsourced private data. Most encryption schemes are not optimized for update-intensive cases, which say that the same data record is frequently added and deleted from the database. How to build an efficient and secure DSE scheme for update-intensive data is still challenging. We propose UI-SE, the first DSE scheme that achieves single-round-trip interaction, near-zero client storage, and backward privacy without any insertion patterns. UI-SE involves a new tree data structure, named OU-tree, which supports oblivious data updates without any access-pattern leakage. We formally prove that UI-SE is adaptively secure under Type-1$^-$ backward privacy, which is stronger than backward privacy proposed by Bost et al. in CCS 2017. Experimental data also demonstrate UI-SE has low computational overhead, low local disk usage, and high update performance on scalable datasets.

Available format(s)
Cryptographic protocols
Publication info
Preprint. Minor revision.
Backward PrivacyCloud ComputingDynamic Searchable EncryptionForward PrivacyOblivious RAM.
Contact author(s)
cxiaodiao @ hnu edu cn
2021-09-22: received
Short URL
Creative Commons Attribution


      author = {Zhiqiang Wu and Jin Wang and Keqin Li},
      title = {Update-Sensitive Structured Encryption with Backward Privacy},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1266},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.