Paper 2017/819

S3ORAM: A Computation-Efficient and Constant Client Bandwidth Blowup ORAM with Shamir Secret Sharing

Thang Hoang, Ceyhun D. Ozkaptan, Attila A. Yavuz, Jorge Guajardo, and Tam Nguyen

Abstract

Oblivious Random Access Machine (ORAM) enables a client to access her data without leaking her access patterns. Existing client-efficient ORAMs either achieve O(log N) client-server communication blowup without heavy computation, or O(1) blowup but with expensive homomorphic encryptions. It has been shown that O(log N) bandwidth blowup might not be practical for certain applications, while schemes with O(1) communication blowup incur even more delay due to costly homomorphic operations. In this paper, we propose a new distributed ORAM scheme referred to as Shamir Secret Sharing ORAM (S3ORAM), which achieves O(1) client-server bandwidth blowup and O(1) blocks of client storage without relying on costly partial homomorphic encryptions. S3ORAM harnesses Shamir Secret Sharing, tree-based ORAM structure and a secure multi-party multiplication protocol to eliminate costly homomorphic operations and, therefore, achieves O(1) client-server bandwidth blowup with a high computational efficiency. We conducted comprehensive experiments to assess the performance of S3ORAM and its counterparts on actual cloud environments, and showed that S3ORAM achieves three orders of magnitude lower end-to-end delay compared to alternatives with O(1) client communication blowup (Onion-ORAM), while it is one order of magnitude faster than Path-ORAM for a network with a moderate bandwidth quality. We have released the implementation of S3ORAM for further improvement and adaptation.

Note: fix some typos

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. ACM Conference on Computer and Communications Security (CCS) 2017
DOI
10.1145/3133956.3134090
Keywords
ORAMprivacy-enhancing technologiessecret sharingmulti-party computation
Contact author(s)
hoangmin @ oregonstate edu
History
2017-09-07: revised
2017-08-31: received
See all versions
Short URL
https://ia.cr/2017/819
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/819,
      author = {Thang Hoang and Ceyhun D.  Ozkaptan and Attila A.  Yavuz and Jorge Guajardo and Tam Nguyen},
      title = {S3ORAM: A Computation-Efficient and Constant Client Bandwidth Blowup ORAM with Shamir Secret Sharing},
      howpublished = {Cryptology ePrint Archive, Paper 2017/819},
      year = {2017},
      doi = {10.1145/3133956.3134090},
      note = {\url{https://eprint.iacr.org/2017/819}},
      url = {https://eprint.iacr.org/2017/819}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.