Paper 2021/231

LL-ORAM: A Forward and Backward Private Oblivious RAM

Zhiqiang Wu, Xiaoyong Tang, Jin Wang, and Tan Deng


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.

Available format(s)
-- withdrawn --
Secret-key cryptography
Publication info
Preprint. Minor revision.
Cloud ComputingDynamic Searchable EncryptionOblivious RAMRandom Oracle
Contact author(s)
wzq @ csust edu cn
2021-08-26: withdrawn
2021-03-02: 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.