Cryptology ePrint Archive: Report 2021/231

LL-ORAM: A Forward and Backward Private Oblivious RAM

Zhiqiang Wu and Xiaoyong Tang and Jin Wang and Tan Deng

Abstract: Oblivious RAM (ORAM) enables a user to read/write her outsourced cloud data without access-pattern leakage. Not all users want a fully functional ORAM all the time since it always creates inefficiency. We show that forward-private/backward-private (FP/BP) ORAMs are also good alternatives for reducing the search-pattern leakage of dynamic searchable encryption (DSE). We introduce the FP/BP-ORAM definitions and present LL-ORAM, the first FP/BP-ORAM that achieves near-zero client storage, single-round-trip read/write, worst-case sublinear search time, and an extremely simple implementation. LL-ORAM consists of a set of switchable protocols whose security can be switched among forward privacy, backward privacy, and perfect security at any time. The construction involves a novel tree data structure named LL-tree, whose advantage is that it supports fast computation in the cloud with an access-pattern-reduced leakage profile. LL-ORAM security is formally proven under forward and backward privacy. The experimental results demonstrate that LL-ORAM is efficient and can be practically employed by DSE applications.

Category / Keywords: secret-key cryptography / Cloud Computing, Dynamic Searchable Encryption, Oblivious RAM, Random Oracle

Date: received 1 Mar 2021

Contact author: wzq at csust edu cn

Available format(s): PDF | BibTeX Citation

Version: 20210302:203257 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]