International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
T.-H. Hubert Chan
Jonathan Katz
Kartik Nayak
Antigoni Polychroniadou
Elaine Shi
Download:
DOI: 10.1007/978-3-030-03332-3_7
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2018
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.
BibTeX
@inproceedings{asiacrypt-2018-29188,
  title={More is Less: Perfectly Secure Oblivious Algorithms in the Multi-server Setting},
  booktitle={Advances in Cryptology – ASIACRYPT 2018},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  volume={11274},
  pages={158-188},
  doi={10.1007/978-3-030-03332-3_7},
  author={T.-H. Hubert Chan and Jonathan Katz and Kartik Nayak and Antigoni Polychroniadou and Elaine Shi},
  year=2018
}