Cryptology ePrint Archive: Report 2020/604

Perfectly Secure Oblivious Parallel RAM with $O(\log^3 N/ \log \log N)$ Overhead

T-H. Hubert Chan and Wei-Kai Lin and Kartik Nayak and Elaine Shi

Abstract: Oblivious RAM (ORAM) is a technique for compiling any program to an oblivious counterpart, i.e., one whose access patterns do not leak information about the secret inputs. Similarly, Oblivious Parallel RAM (OPRAM) compiles a parallel program to an oblivious counterpart. In this paper, we care about ORAM/OPRAM with perfect security, i.e., the access patterns must identically distributed no matter what the program's memory request sequence is. We show two novel results.

The first result is a new perfectly secure OPRAM scheme with $O(\log^3 N/\log \log N)$ expected overhead. In comparison, the prior literature has been stuck at $O(\log^3 N)$ for more than a decade.

The second result is a new perfectly secure OPRAM scheme with $O(\log^4 N/\log \log N)$ worst-case overhead. To the best of our knowledge, this is the first perfectly secure OPRAM scheme with polylogarithmic worst-case overhead. Prior to our work, the state of the art is a perfectly secure ORAM scheme with more than $\sqrt{N}$ worst-case overhead, and the result does not generalize to a parallel setting. Our work advances the theoretical understanding of the asymptotic complexity of perfectly secure OPRAMs.

Category / Keywords: cryptographic protocols / perfect oblivious RAM, oblivious PRAM

Date: received 21 May 2020, last revised 31 May 2020

Contact author: hubert at cs hku hk,wklin@cs cornell edu,kartik@cs duke edu,runting@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200531:220705 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]