Cryptology ePrint Archive: Report 2021/1266

Update-Sensitive Structured Encryption with Backward Privacy

Zhiqiang Wu and Jin Wang and Keqin Li

Abstract: 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.

Category / Keywords: cryptographic protocols / Backward Privacy, Cloud Computing, Dynamic Searchable Encryption, Forward Privacy, Oblivious RAM.

Date: received 21 Sep 2021

Contact author: cxiaodiao at hnu edu cn

Available format(s): PDF | BibTeX Citation

Version: 20210922:151355 (All versions of this report)

Short URL: ia.cr/2021/1266


[ Cryptology ePrint archive ]