One-Time Memories Secure Against Depth-Bounded Quantum Circuits

Kyosuke Sekii, Takashi Nishide

TL;DR

This paper tackles the challenge of creating secure "one-time memories" (OTMs) that can only be accessed once, even in the face of quantum adversaries. They achieve this by introducing two novel OTM constructions that are secure against quantum computers with limited circuit depth, a practical assumption for current and near-future quantum technology.

What Problem Does This Paper Address?

The concept of a one-time memory (OTM) is a cryptographic primitive that, like a non-interactive oblivious transfer, allows a user to retrieve one of two stored messages but prevents them from accessing the other. Classically, and even in the quantum realm, it's been proven impossible to build secure OTMs without relying on specialized hardware that prevents quantum superposition queries. This paper aims to circumvent this impossibility by assuming that adversaries are limited to quantum circuits of a bounded depth. This assumption is motivated by the practical difficulty of building very deep quantum circuits, making it a more realistic security model for certain applications.

Methods

The paper presents two main constructions for OTMs:

  • First Construction: This construction is efficiently realizable and secure against adversaries restricted to constant-depth quantum circuits. It cleverly combines Wiesner states (a quantum primitive known for its unclonable properties) with obfuscation techniques based on the Learning With Errors (LWE) assumption. This approach avoids the need for hardware tokens and relies only on classical communication and quantum state transmission, making it more practical than previous methods. A key innovation here is designing the obfuscated program to tolerate small quantum measurement errors, a crucial aspect for NISQ-era quantum computers.
  • Second Construction: This is a feasibility result that achieves security against adversaries limited to $O(\lambda)$-depth quantum circuits (where $\lambda$ is the security parameter). It builds upon post-quantum indistinguishability obfuscation (iO) and utilizes hidden subspace states. The security relies on the unclonability and direct product hardness of these states. This construction extends security to adversaries with slightly deeper quantum capabilities, albeit with more complex machinery.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Depth-Boundedness as a Practical Security Assumption: The paper highlights that limiting adversaries to bounded-depth quantum circuits is a viable and practical approach to achieving cryptographic security, moving beyond the idealized assumption of arbitrary-depth quantum computation.
  • Tolerating Measurement Errors: The first construction's ability to handle non-negligible measurement errors is a significant step towards practical quantum cryptography, as current quantum computers are prone to such errors.
  • Combining Quantum Primitives and Obfuscation: The successful integration of Wiesner states and advanced obfuscation techniques (like compute-and-compare obfuscation and indistinguishability obfuscation) demonstrates a powerful paradigm for building secure quantum cryptographic primitives.
  • Circumventing Impossibility Results: By leveraging the depth-bounded adversary model, the authors successfully construct OTMs, which were previously shown to be impossible under more general quantum adversaries.

Key Results

  • The paper presents two OTM constructions: one secure against constant-depth adversaries and another against $O(\lambda)$-depth adversaries.
  • The first construction is efficiently realizable and tolerates realistic quantum measurement errors.
  • The constructions are entirely software-based, avoiding the need for specialized hardware tokens.
  • The security of the constructions is proven against quantum adversaries with bounded circuit depth, relying on standard cryptographic assumptions like LWE.

Limitations and Future Work

  • Depth Limitation: The primary limitation is the reliance on the depth-bounded adversary model. While practical, it doesn't offer security against adversaries with arbitrarily deep quantum circuits. The paper explicitly discusses a "bit-flipping attack" that highlights the limitations of their constructions when adversaries can perform deeper computations, suggesting that simply composing obfuscated programs doesn't necessarily extend security to higher depths.
  • Complexity of the Second Construction: The second construction, while achieving security against deeper adversaries, relies on more complex primitives like indistinguishability obfuscation, which might have higher overheads in practice.
  • Future Work: The paper implicitly suggests exploring constructions that might offer stronger security guarantees against deeper quantum circuits, potentially by investigating alternative quantum primitives or different obfuscation techniques. Further research into the precise bounds of depth-bounded security and its implications for other cryptographic primitives is also a natural direction.

Summary updated

BibTeX
@article{sekii2025one,
  author = {Kyosuke Sekii and Takashi Nishide},
  title = {{One-Time Memories Secure Against Depth-Bounded Quantum Circuits}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2025},
}

Loading related content...

Figure