Paper 2018/851

More is Less: Perfectly Secure Oblivious Algorithms in the Multi-Server Setting

T-H. Hubert Chan, Jonathan Katz, Kartik Nayak, Antigoni Polychroniadou, and Elaine Shi

Abstract

The problem of Oblivious RAM (ORAM) has traditionally been studied in the single-server setting, but more recently the multi-server setting has also been considered. Yet it is still unclear whether the multi-server setting has any inherent advantages, e.g., whether the multi-server setting can be used to achieve stronger security goals or provably better efficiency than is possible in the single-server case. In this work, we construct a perfectly secure 3-server ORAM scheme that outperforms the best known single-server scheme by a logarithmic factor. In the process we also show, for the first time, that there exist specific algorithms for which multiple servers can overcome known lower bounds in the single-server setting.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in ASIACRYPT 2018
Keywords
oblivious RAMmuli-serverperfect security
Contact author(s)
hubert @ cs hku hk
jkatz @ cs umd edu
nkartik @ vmware com
antigoni @ cornell edu
runting @ gmail com
History
2018-09-20: received
Short URL
https://ia.cr/2018/851
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/851,
      author = {T-H.  Hubert Chan and Jonathan Katz and Kartik Nayak and Antigoni Polychroniadou and Elaine Shi},
      title = {More is Less: Perfectly Secure Oblivious Algorithms in the Multi-Server Setting},
      howpublished = {Cryptology ePrint Archive, Paper 2018/851},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/851}},
      url = {https://eprint.iacr.org/2018/851}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.