Cryptology ePrint Archive: Report 2017/014

ORAMs in a Quantum World

Tommaso Gagliardoni and Nikolaos P. Karvelas and Stefan Katzenbeisser

Abstract: We study the security of {\em Oblivious Random Access Machines (ORAM)} in the quantum world. First we introduce a new formal treatment of ORAMs, which is at the same time elegant and simpler than the known formalization by Goldreich and Ostrovsky. Then we define and analyze the notion of post-quantum security for ORAMs, i.e., classical ORAMs resistant against quantum adversaries. We show that merely switching %from classically secure to post-quantum secure encryption in a classically secure ORAM construction does not generally yield a post-quantum secure ORAM construction. On the other hand, we provide a post-quantum secure construction based on a modification of Path-ORAM, the most efficient general ORAM construction, introduced by Stefanov et al.

Furthermore, we initiate the study of {\em Quantum ORAMs (QORAMs)}, that is, ORAM constructions meant to be executed between quantum parties acting on arbitrary quantum data. We address many problems arising when formalizing Quantum ORAMs, and we provide a secure construction (based on Path-ORAM and a quantum encryption scheme introduced by Alagic et al.) which has the interesting property of making read and write operations {\em inherently equivalent}. In so doing, we develop a novel technique of quantum extractability which is of independent interest. We believe that QORAMs represent a natural and interesting step in the direction of achieving privacy in future scenarios where quantum computing is ubiquitous.

Category / Keywords: Quantum security, Privacy Enhancing Technologies, Oblivious RAM, Path-ORAM

Date: received 9 Jan 2017, last revised 27 Feb 2017

Contact author: karvelas at seceng informatik tu-darmstadt de

Available format(s): PDF | BibTeX Citation

Version: 20170227:145827 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]