S-ORAM: A Segmentation-based Oblivious RAM

Date
2013-01-01
Authors
Jinsheng, Zhang
Wensheng, Zhang
Qiao, Daji
Qiao, Daji
Journal Title
Journal ISSN
Volume Title
Publisher
Source URI
Altmetrics
Authors
Qiao, Daji
Person
Research Projects
Organizational Units
Computer Science
Organizational Unit
Journal Issue
Series
Abstract

As outsourcing data to remote storage servers gets popular, protecting user’s pattern in accessing these data has become a big concern. ORAM constructions are promising solutions to this issue, but their application in practice has been impeded by the high communication and storage overheads incurred. Towards addressing this challenge, this paper proposes a segmentation-based ORAM (S-ORAM). It adopts two segment-based techniques, namely, piece-wise shuffling and segment-based query, to improve the performance of shuffling and query by factoring block size into design. Extensive security analysis shows that S-ORAM is a provably highly secure solution with a negligible failure probability of O(NlogN).In terms of communication and storage overheads, S-ORAM out-performs the Balanced ORAM (B-ORAM) and the Path ORAM (P-ORAM), which are the state-of-the-art hash and index based ORAMs respectively, in both practical and theoretical evaluations. Particularly under practical settings, the communication overhead of S-ORAM is 12 to 23 times less than B-ORAM when they have the same constant-size user-side storage, and S-ORAM consumes 80% less server-side storage and around 60% to 72% less bandwidth than P-ORAM when they have the similar logarithmic-size user-side storage.

Description
Keywords
Citation
Collections