Paper 2021/231
LL-ORAM: A Forward and Backward Private Oblivious RAM
Zhiqiang Wu, Xiaoyong Tang, 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.
Metadata
- Available format(s)
- -- withdrawn --
- Category
- Secret-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- Cloud ComputingDynamic Searchable EncryptionOblivious RAMRandom Oracle
- Contact author(s)
- wzq @ csust edu cn
- History
- 2021-08-26: withdrawn
- 2021-03-02: received
- See all versions
- Short URL
- https://ia.cr/2021/231
- License
-
CC BY