Cryptology ePrint Archive: Report 2020/871

Quantum Immune One-Time Memories

Qipeng Liu and 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.

Category / Keywords: cryptographic protocols / quantum cryptography, one-time memory, one-time program, oblivious transfer

Date: received 10 Jul 2020

Contact author: qipengl at cs princeton edu

Available format(s): PDF | BibTeX Citation

Version: 20200712:125821 (All versions of this report)

Short URL: ia.cr/2020/871


[ Cryptology ePrint archive ]