A Matrix Based ORAM: Design, Implementation and Experimental Analysis

Steven GORDON  Atsuko MIYAJI  Chunhua SU  Karin SUMONGKAYOTHIN  

IEICE TRANSACTIONS on Information and Systems   Vol.E99-D   No.8   pp.2044-2055
Publication Date: 2016/08/01
Publicized: 2016/05/31
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2015INP0012
Type of Manuscript: Special Section PAPER (Special Section on Security, Privacy and Anonymity of Internet of Things)
ORAM,  secure communication,  secure access pattern,  secure protocol,  

Full Text: PDF>>
Buy this Article

Oblivious RAM is a technique for hiding the access patterns between a client and an untrusted server. However, current ORAM algorithms incur large communication or storage overhead. We propose a novel ORAM construction using a matrix logical structure for server storage where a client downloads blocks from each row, choosing the column randomly to hide the access pattern. Both a normal construction and recursive construction, where a position map normally stored on the client is also stored on the server, are presented. We show our matrix ORAM achieves constant bandwidth cost for the normal construction, uses similar storage to the existing Path ORAM, and improves open the bandwidth cost compared to Path ORAM under certain conditions in the recursive construction.