Towards Simple and Useful One-Time Programs in the Quantum Random Oracle Model

1. Problem Statement

One-Time Programs (OTPs) are cryptographic primitives that allow a program to be executed exactly once, after which it becomes unusable. While theoretically powerful, constructing secure OTPs is impossible in the standard model without additional assumptions.

• The Challenge: Existing constructions often rely on complex assumptions (e.g., Indistinguishability Obfuscation, hidden subspace states) or restrictive physical models (e.g., stateless hardware tokens, bounded quantum storage with strict time limits).
• The Gap: Many current models restrict the adversary's ability to hold quantum memory or require immediate measurement, limiting the practical utility of OTPs (e.g., they cannot be stored in quantum memory for later use). There is a need for a scheme that:
  1. Uses simple, near-term quantum hardware (single-qubit operations).
  2. Allows the receiver to store the OTP in quantum memory.
  3. Remains secure against adversaries who can perform adaptive classical computation interleaved with bounded-depth quantum circuits.

2. Methodology and Construction

The author proposes a construction for One-Time Memories (OTMs), which imply OTPs, based on three core components:

A. Core Primitives

1. Wiesner States (Conjugate Coding): The scheme uses tensor products of independent single-qubit states. Each qubit is prepared in either the computational basis ($Z$) or the Hadamard basis ($X$) encoding a secret bit. Crucially, no multi-qubit entanglement is used.
2. Conjunction Obfuscation: The scheme utilizes distributional Virtual Black-Box (VBB) obfuscation for conjunctions (AND gates), instantiable from the Learning Parity with Noise (LPN) assumption. This obfuscation hides the specific positions of the basis choices and the decryption keys.
3. Random Oracle Model (ROM): A random oracle $\mathcal{H}$ is used to bind measurement outcomes to specific inputs, forcing the adversary to commit to classical values.

B. The Protocol (Scheme 2)

• Preparation:
  • The sender prepares $n$ independent blocks of $m$-qubit Wiesner states.
  • A random subset of positions $\Theta_X$ uses the $X$ basis, and the complement $\Theta_Z$ uses the $Z$ basis.
  • Secrets $s_i$ are hashed via $\mathcal{H}(i, s_i)$.
  • Two conjunction obfuscations ($\mathcal{O}_X, \mathcal{O}_Z$) are generated. Each checks if the hashed measurement outcomes for its specific subset match the expected hashes. If valid, they output a key $k_\alpha$.
  • Messages $m_X, m_Z$ are encrypted as $c_\alpha = k_\alpha \oplus m_\alpha$.
• Evaluation:
  • The receiver chooses a basis $\alpha \in \{X, Z\}$.
  • They measure the quantum state in basis $\alpha$.
  • They compute hashes of the outcomes and evaluate the corresponding obfuscated conjunction $\mathcal{O}_\alpha$.
  • If the conjunction accepts, the receiver recovers $k_\alpha$ and decrypts $m_\alpha$.

3. Key Technical Contributions

A. New POVM Bound (Sequential Conjugate Coding Security)

The paper proves a novel information-theoretic bound (Theorem 3.1) for $m$-qubit conjugate coding.

• Theorem: If a Positive Operator-Valued Measure (POVM) identifies computational basis states with probability $1-\epsilon$, the probability of guessing the conjugate (Hadamard) basis string is at most $\frac{1}{2^m} + O(\epsilon^{1/4})$.
• Significance: This bound is sequential. It holds even if the adversary measures first and then learns which basis to guess. This generalizes prior single-qubit results to the multi-qubit setting, ensuring that measuring correctly in one basis leaves the conjugate basis secrets with high min-entropy.

B. Classical-Query Security

The authors prove that the scheme is simulation-secure against quantum adversaries restricted to classical queries to the random oracle (Theorem 4.1).

• Mechanism: To evaluate an obfuscated conjunction, the adversary must provide valid hash inputs $\mathcal{H}(i, s_i)$. Since the oracle is classical, the adversary must irrevocably commit to specific measurement outcomes.
• Security Argument: Due to the POVM bound, if the adversary measures in basis $X$ to satisfy $\mathcal{O}_X$, their state becomes effectively random in basis $Z$. Consequently, they cannot guess the secrets required to satisfy $\mathcal{O}_Z$. The probability of satisfying both is negligible ($2^{-\Omega(\lambda^2)}$).

C. Adaptive Depth Security via Lifting

The paper argues for security against $\mathsf{BPPQNCBPP}^d$ adversaries (adversaries with polynomial classical time and polynomial quantum depth $d$ between oracle queries).

• Lifting Framework: The authors apply an informal adaptation of the lifting theorem by Arora et al. [1]. This framework suggests that depth-bounded quantum adversaries interacting with a specially constructed random oracle cannot maintain coherent superpositions across many queries; their interaction effectively collapses to a classical transcript.
• Conjecture: If the lifting theorem holds, the classical-query security proof extends to the adaptive quantum depth setting, allowing the OTP to be stored in quantum memory for later use.

4. Results

• Simplicity: The construction avoids complex entanglement and Indistinguishability Obfuscation (iO), relying only on single-qubit operations and LPN-based obfuscation.
• Security:
  • Proven secure against classical-query quantum adversaries.
  • Conjectured secure against adaptive depth-bounded quantum adversaries.
• Practicality: The scheme is designed for near-term implementation, as it does not require fault-tolerant quantum computing or long coherence times beyond the bounded depth constraint.

5. Significance and Future Directions

• Practical OTPs: This work bridges the gap between theoretical OTPs and practical implementation. By removing the need for complex entanglement and relying on bounded-depth assumptions (which are physically natural for non-fault-tolerant states), it enables "long-lived" OTPs that can be stored in quantum memory.
• Realistic Adversary Models: The focus on $\mathsf{BPPQNCBPP}^d$ captures realistic threats where an adversary has significant classical power but limited quantum processing depth due to noise accumulation.
• Open Problems:
  • Tighter Bounds: Improving the $O(\epsilon^{1/4})$ term in the POVM bound.
  • Noise Tolerance: Analyzing robustness against realistic depolarizing and dephasing noise.
  • Formal Lifting: Providing a rigorous formal proof that the Arora et al. lifting framework applies specifically to this OTM construction.

In summary, Stambler presents a conceptually simple, practically viable construction for One-Time Memories that leverages the physical limitations of quantum noise (bounded depth) and the hardness of LPN to achieve security against powerful, adaptive quantum adversaries.