Paper 2017/014

ORAMs in a Quantum World

Tommaso Gagliardoni, 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.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Quantum securityPrivacy Enhancing TechnologiesOblivious RAMPath-ORAM
Contact author(s)
karvelas @ seceng informatik tu-darmstadt de
History
2017-02-27: revised
2017-01-11: received
See all versions
Short URL
https://ia.cr/2017/014
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/014,
      author = {Tommaso Gagliardoni and Nikolaos P.  Karvelas and Stefan Katzenbeisser},
      title = {ORAMs in a Quantum World},
      howpublished = {Cryptology ePrint Archive, Paper 2017/014},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/014}},
      url = {https://eprint.iacr.org/2017/014}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.