More is less: Perfectly secure oblivious algorithms in the multi-server setting

Conference Paper

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.

Full Text

Duke Authors

Cited Authors

  • Chan, THH; Katz, J; Nayak, K; Polychroniadou, A; Shi, E

Published Date

  • January 1, 2018

Published In

Volume / Issue

  • 11274 LNCS /

Start / End Page

  • 158 - 188

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 13 (ISBN-13)

  • 9783030033316

Digital Object Identifier (DOI)

  • 10.1007/978-3-030-03332-3_7

Citation Source

  • Scopus