File(s) not publicly available

M-ORAM: A matrix ORAM with Log N bandwidth cost

chapter
posted on 06.03.2018, 00:00 authored by Steven GordonSteven Gordon, A Miyaji, C Su, K Sumongkayothin
Oblivious RAM can hide a client’s access pattern from an untrusted server. However current ORAM algorithms incur large communication or storage overheads. We propose a novel ORAM construction using a matrix structure for server storage where a client downloads blocks from each row, choosing the column randomly to hide the access pattern. Both a normal and recursive construction are presented, achieving bandwidth cost of O(1) and O(logN), respectively, and client storage similar to Path ORAM. We show under the same conditions, our matrix ORAM reduces bandwidth cost compared to Path ORAM by log N/2.

Funding

Category 3 - Industry and Other Research Income

History

Editor

Kim H; Choi D

Parent Title

Information Security Applications: 16th International Workshop, WISA 2015 Jeju Island, Korea, August 20–22, 2015 Revised Selected Papers

Volume

9503

Start Page

3

End Page

15

Number of Pages

13

eISSN

1611-3349

ISSN

0302-9743

ISBN-13

9783319318745

Publisher

Springer International

Place of Publication

Cham, Switzerland

Peer Reviewed

Yes

Open Access

No

External Author Affiliations

Japan Advance Institute of Science and Technology; Osaka University, Japan; apan Science and Technology Agency (JST) CREST

Era Eligible

Yes