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.
Steven GORDON
Sirindhorn International Institute of Technology
Atsuko MIYAJI
Japan Advanced Institute of Science and Technology,Osaka University
Chunhua SU
Japan Advanced Institute of Science and Technology
Karin SUMONGKAYOTHIN
Sirindhorn International Institute of Technology,Japan Advanced Institute of Science and Technology
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Steven GORDON, Atsuko MIYAJI, Chunhua SU, Karin SUMONGKAYOTHIN, "A Matrix Based ORAM: Design, Implementation and Experimental Analysis" in IEICE TRANSACTIONS on Information,
vol. E99-D, no. 8, pp. 2044-2055, August 2016, doi: 10.1587/transinf.2015INP0012.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2015INP0012/_p
Copy
@ARTICLE{e99-d_8_2044,
author={Steven GORDON, Atsuko MIYAJI, Chunhua SU, Karin SUMONGKAYOTHIN, },
journal={IEICE TRANSACTIONS on Information},
title={A Matrix Based ORAM: Design, Implementation and Experimental Analysis},
year={2016},
volume={E99-D},
number={8},
pages={2044-2055},
abstract={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.},
keywords={},
doi={10.1587/transinf.2015INP0012},
ISSN={1745-1361},
month={August},}
Copy
TY - JOUR
TI - A Matrix Based ORAM: Design, Implementation and Experimental Analysis
T2 - IEICE TRANSACTIONS on Information
SP - 2044
EP - 2055
AU - Steven GORDON
AU - Atsuko MIYAJI
AU - Chunhua SU
AU - Karin SUMONGKAYOTHIN
PY - 2016
DO - 10.1587/transinf.2015INP0012
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E99-D
IS - 8
JA - IEICE TRANSACTIONS on Information
Y1 - August 2016
AB - 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.
ER -