Paper 2020/871
Quantum Immune One-Time Memories
Qipeng Liu, Amit Sahai, and Mark Zhandry
Abstract
One-time memories (OTM) are the hardware version of oblivious transfer, and are useful for constructing objects that are impossible with software alone, such as one-time programs. In this work, we consider attacks on OTMs where a quantum adversary can leverage his physical access to the memory to mount quantum ``superposition attacks'' against the memory. Such attacks result in significantly weakened OTMs. For example, in the application to one-time programs, it may appear that such an adversary can always “quantumize” the classical protocol by running it on a superposition of inputs, and therefore learn superpositions of outputs of the protocol. Perhaps surprisingly, we show that this intuition is false: we construct one-time programs from quantum-accessible one-time memories where the view of an adversary, despite making quantum queries, can be simulated by making only classical queries to the ideal functionality. At the heart of our work is a method of immunizing one-time memories against superposition attacks.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint. MINOR revision.
- Keywords
- quantum cryptographyone-time memoryone-time programoblivious transfer
- Contact author(s)
- qipengl @ cs princeton edu
- History
- 2020-07-12: received
- Short URL
- https://ia.cr/2020/871
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/871,
author = {Qipeng Liu and Amit Sahai and Mark Zhandry},
title = {Quantum Immune One-Time Memories},
howpublished = {Cryptology ePrint Archive, Paper 2020/871},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/871}},
url = {https://eprint.iacr.org/2020/871}
}
