Search

Most of existing ORAM constructions have communication efficiency as the major optimization priority; the server storage efficiency, however, has not received much attention. Motivated by the observation that, the server storage efficiency is as important as communication efficiency when the storage capacity is very large and/or the outsourced data are not frequently accessed, we propose in this paper a new ORAMconstruction called Octopus ORAM. Through extensive security analysis and performance comparison, wedemonstrate that, Octopus ORAM is secure; also, it significantly improves the server storage efficiency,achieves a comparable level of communication efficiency as state-of-the-art ORAM constructions, at the cost of increased client-side storage, and the increased client-side storage should be affordable to the clients who adopt local facilities such as cloud storage gateways.

This paper proposes TSKT-oblivious RAM (ORAM), an efficient multi-server ORAM construction, to protect a client’s access pattern to outsourced data. TSKT-ORAM organizes each of the server storages as a k-ary tree and adopts XOR-based private information retrieval (PIR) and a novel delayed eviction technique to optimize both the data query and data eviction process. TSKT-ORAM is proven to protect the data access pattern privacy with a failure probability of 2 - 80 when system parameter k ≥ 128 . Meanwhile, given a constant-size local storage, when N (i.e., the total number of outsourced data blocks) ranges from 2 16 – 2 34 , the communication cost of TSKT-ORAM is only 22–46 data blocks. Asymptotic analysis and practical comparisons are conducted to show that TSKT-ORAM incurs lower communication cost, storage cost and access delay in practical scenarios than the compared state-of-the-art ORAM schemes.