File(s) not publicly available

Recursive matrix oblivious RAM: An ORAM construction for constrained storage devices

journal contribution
posted on 04.04.2018, 00:00 by Steven Gordon, H Huang, A Miyaji, C Su, K Sumongkayothin, K Wipusitwarakun
Oblivious random access machine (ORAM) constructions can be used to hide a client’s access pattern from a trusted but curious storage server. The privacy provided comes at the cost of increasing communication overhead, storage overhead, and computation overhead of the system. Recursive matrix-based ORAM (RM-ORAM) is a new ORAM construction, which is designed for constrained storage space devices. RM-ORAM significantly reduces the client storage usage by using recursion, while the computational and bandwidth overhead are slightly increased as a tradeoff. However, it can achieve better overall asymptotic performance than other existing ORAM schemes, e.g., recursive Path ORAM. In this paper, we present the construction and its theoretical analysis. In addition, we present how to select the appropriate number of data blocks, which are being downloaded per level of recursion and the appropriate size of reserved space on the client. We provide theoretical security and performance analysis, as well as experimental results to illustrate how RM-ORAM satisfies security requirements and provides improved performance compared with other ORAM schemes.

Funding

Category 3 - Industry and Other Research Income

History

Volume

12

Issue

12

Start Page

3024

End Page

3038

Number of Pages

15

ISSN

1556-6013

Publisher

IEEE, USA

Peer Reviewed

Yes

Open Access

No

External Author Affiliations

Thammasat University, Thailand; University of Aizu, Japan; Fujian Normal University, China; Japan Advance Institute of Science and Technology, Japan;

Era Eligible

Yes

Journal

IEEE Transactions on Information Forensics and Security

Exports