Cryptology ePrint Archive: Report 2018/851

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

T-H. Hubert Chan and Jonathan Katz and Kartik Nayak and 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.

Category / Keywords: oblivious RAM, muli-server, perfect security

Original Publication (in the same form): IACR-ASIACRYPT-2018

Date: received 8 Sep 2018

Contact author: hubert at cs hku hk, jkatz at cs umd edu, nkartik at vmware com, antigoni at cornell edu, runting at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20180920:185833 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]