⚛️ quantum physics

On Best-Possible One-Time Programs

This paper establishes the impossibility of generic best-possible one-time programs, then introduces and constructs "testable" one-time programs for arbitrary quantum functionalities in the classical oracle model by leveraging generalized Single-Effective-Query security and stateful quantum indistinguishability obfuscation.

Original authors: Aparna Gupte, Jiahui Liu, Luowen Qian, Justin Raizes, Bhaskar Roberts, Mark Zhandry

Published 2026-03-03

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Aparna Gupte, Jiahui Liu, Luowen Qian, Justin Raizes, Bhaskar Roberts, Mark Zhandry

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "One-Time Use" Dream

Imagine you have a magical, super-secret recipe for the world's best chocolate cake. You want to sell this recipe to a baker, but you have a strict rule: They can use the recipe exactly once. After they bake one cake, the recipe must vanish forever. They shouldn't be able to copy it, memorize it, or bake a second cake.

In the world of cryptography, this is called a One-Time Program (OTP). The goal is to give someone a "black box" that does a specific job (like baking a cake or signing a document) one time, and then self-destructs so no one can learn how it works or use it again.

For a long time, scientists thought this was impossible without special hardware (like a tamper-proof chip). Then, they thought maybe quantum physics (the physics of tiny particles) could save the day because quantum states can't be copied. But recent research showed that even with quantum physics, you can't perfectly stop someone from "peeking" at the recipe multiple times using a trick called a "gentle measurement."

This paper asks a very deep question: If we can't make a perfect one-time program, what is the absolute best we can possibly do?

Part 1: The Bad News (The "Perfect" Dream is Dead)

The authors first tried to find a "Universal Best-Possible Compiler." Think of this as a magical machine that takes any secret recipe and turns it into a one-time program that is as secure as mathematically possible.

The Result: They proved this machine cannot exist.

The Analogy:
Imagine two different types of magic boxes:

Box A (The Constant Box): No matter what you put inside, it always spits out the same red marble.
Box B (The Secret Box): It looks like Box A from the outside, but inside, it actually changes the marble based on what you put in.

The problem is that to a computer, Box A and Box B look identical. You can't tell them apart just by looking at the outside.

However, to make a "perfect" one-time program:

For Box A, the best security is to just hand the user a red marble and say, "Here, eat this." (Because the output never changes).
For Box B, the best security is to give them a complex machine that actually calculates the marble.

If you try to build a "Best-Possible Compiler" that works for both, it gets confused. It has to act like a simple marble for Box A, but a complex machine for Box B. But since the computer can't tell the difference between the two boxes, it can't know which behavior to choose. If it chooses the wrong one, it breaks the security.

Conclusion: You cannot build a generic "best possible" one-time program for everything. The math simply doesn't allow it.

Part 2: The Good News (The "Testable" Compromise)

Since the "Perfect" dream is dead, the authors asked: "Can we find a specific type of one-time program where we can achieve the best possible security?"

They introduced a new concept called Testable One-Time Programs.

The Analogy:
Imagine you give a baker a recipe, but you also give them a magic mirror.

The recipe is the "program."
The magic mirror is a "reflection oracle."

Here is how it works:

The baker uses the recipe once to bake a cake.
If they try to use the recipe a second time, the magic mirror checks: "Did you mess with the recipe? Is it still in its original, pristine state?"
If the recipe has been touched or copied, the mirror shatters, and the recipe stops working.
If the recipe is still perfect, the mirror lets them try again (but the security rules say they shouldn't need to).

Why is this special?
The "Testable" requirement forces the program to be in a very specific, clean state (a "pure state"). This removes the confusing "mixed up" scenarios that broke the "Perfect" compiler in Part 1.

The Result:
The authors proved that for these Testable programs, we can achieve the "Best Possible" security. They created a new security standard called SEQ (Single Effective Query).

SEQ means: "You can get the answer once. If you try to get the answer again, the system will notice you tried to 'undo' your first attempt and will reject you."

It's like a vending machine that gives you a soda. If you try to put the soda back in and ask for another one, the machine realizes you are trying to cheat and locks up.

Part 3: The Future (How to Build This in the Real World)

The paper shows that "Testable One-Time Programs" work perfectly if we have a "Magic Oracle" (a theoretical, perfect computer that everyone trusts). But we don't have those in real life yet.

So, the authors proposed a new tool called Stateful Quantum Indistinguishability Obfuscation (Stateful Quantum iO).

The Analogy:

Standard Obfuscation: Hiding the code of a program so no one can read it.
Stateful Obfuscation: Hiding the code of a program that changes its mind over time.

Imagine a spy who has a secret notebook.

Normal Spy: The notebook always says the same thing.
Stateful Spy: The notebook writes a new secret every time you ask a question, and then burns that page.

The authors showed that if we can build this "Stateful Spy Notebook" (Stateful Quantum iO), we can automatically build the "Testable One-Time Programs" we need.

They also showed that this "Stateful Spy Notebook" might be possible to build using current math assumptions (like the difficulty of solving certain puzzles), even without magic hardware.

Summary of the Takeaways

The "Perfect" is Impossible: You cannot build a universal "Best Possible" one-time program for every single type of software. The math proves it's impossible because some programs look identical but need to behave differently to be secure.
The "Testable" is Possible: If we restrict ourselves to programs that can "check themselves" (Testable One-Time Programs), we can achieve the highest level of security possible.
The Path Forward: To build this in the real world, we need to develop a new type of encryption called Stateful Quantum Obfuscation. This is a program that hides its secrets while allowing it to change its internal state (like burning a page after reading it).

In a Nutshell:
We can't make a "perfect" one-time program for everything. But, if we design our programs to be "self-checking" (Testable), we can make them as secure as physics allows. The key to building this in the real world is inventing a new kind of "shapeshifting" encryption that protects programs that change over time.

1. Problem Statement

One-Time Programs (OTPs) are cryptographic primitives that allow a user to evaluate a program on a single input of their choice while revealing no other information about the program's code or behavior.

The Challenge: Classical OTPs require hardware tokens. Even with quantum information, deterministic functionalities cannot be realized as OTPs due to "gentle measurement" attacks (Broadbent, Gutoski, Stebila, 2013), which allow an adversary to extract information without destroying the state.
Recent Progress: Recent works have achieved positive results for randomized functionalities with high-entropy outputs (e.g., signatures) without hardware assumptions. However, the fundamental limits of OTP security remain unclear.
The Core Question: Is there a generic "best-possible" one-time compiler? Analogous to "best-possible obfuscation" in classical cryptography (Goldwasser & Rothblum, 2007), this would be a transformation that, for any functionality, achieves the strongest possible one-time security that any construction could achieve for that specific functionality.

2. Methodology and Technical Approach

The authors employ a multi-pronged approach combining impossibility proofs, simulation-based security definitions, and obfuscation theory:

Impossibility Proofs via Lossy Encryption: To disprove the existence of a generic best-possible compiler, the authors construct two families of randomized programs that are computationally indistinguishable but require fundamentally different one-time protections. They leverage Lossy Public-Key Encryption (PKE) schemes (constructible from LWE or Group Actions), which have an "injective" mode (standard encryption) and a "lossy" mode (where ciphertexts are statistically independent of the message).
Testable One-Time Programs: Recognizing the impossibility of a generic solution, the authors introduce a restricted class of OTPs called Testable OTPs. These are programs augmented with a reflection oracle (or unitary) that allows the user to verify if the program state has been disturbed. This restriction prevents the use of mixed-state implementations that are only correct "on average," which was the loophole in the impossibility proof.
Single Effective Query (SEQ) Security: The authors generalize the SEQ security notion (originally for classical randomized functions) to all quantum channels. SEQ security posits that an OTP is secure if its output can be simulated by an ideal oracle that allows exactly one "effective" query. If a second query is attempted, the oracle refuses to cooperate unless the first query is perfectly "uncomputed" (reversed), which is impossible if the output was meaningfully measured.
Stateful Quantum Indistinguishability Obfuscation (iO): To achieve these goals in the "plain model" (without oracles), the authors propose a new primitive: Stateful Quantum iO. Unlike standard iO, which obfuscates static circuits, this obfuscates programs that maintain internal state and evolve over sequential queries.

3. Key Contributions and Results

A. Impossibility of Generic Best-Possible OTPs

Result: A generic best-possible one-time compiler does not exist, even for classical randomized functionalities.
Proof Mechanism: The authors define two function families, $D$ $D$ (lossy encryption) and $E$ $E$ (injective encryption).
- $D$ (lossy mode) produces outputs statistically independent of the input. The "best" protection for $D$ is a constant function (ignoring input).
- $E$ (injective mode) produces outputs dependent on the input. The "best" protection for $E$ must preserve this dependency.
- Since $D$ and $E$ are computationally indistinguishable (due to the security of Lossy PKE), a generic compiler cannot distinguish them. However, the optimal protection for $D$ (constant) and $E$ (injective) are mutually exclusive. A compiler forced to behave like the optimal for $D$ will fail correctness for $E$ , and vice versa.
Assumption: This holds assuming the existence of Lossy PKE (derived from LWE or weak pseudorandom group actions).

B. Best-Possible Security for Testable OTPs

Result: While generic best-possible compilers are impossible, best-possible testable one-time compilers are achievable in the oracle model.
Mechanism: The authors prove that SEQ security implies best-possible testable security.
- They show that for any testable program $P$ implementing a channel $\Phi$ , one can simulate the SEQ oracle using $P$ and its reflection oracle.
- Since SEQ security is achievable for all quantum channels in the classical oracle model (via ideal unitary obfuscation), this yields the first positive results for arbitrary quantum channels (beyond just randomized classical functions) without hardware assumptions.

C. Stateful Quantum Indistinguishability Obfuscation (Stateful iO)

Result: The authors propose Stateful Quantum iO as a promising path to constructing best-possible testable OTPs in the plain model.
Definition: Two stateful quantum programs are indistinguishably obfuscated if they produce the same output distributions over any sequence of sequential queries (not just a single query).
Significance:
- Stateful iO implies best-possible testable OTPs.
- Stateful iO is achievable in the classical oracle model (using quantum authentication schemes and ideal unitary obfuscation).
- This avoids the impossibility of standard VBB obfuscation because it accounts for state evolution, preventing "self-referential" attacks that distinguish programs based on their degradation over time.

4. Significance and Implications

Redefining the Limits of OTPs: The paper establishes a fundamental barrier: one cannot hope for a "one-size-fits-all" best-possible OTP compiler. Security must be tailored to the specific class of programs, and for general randomized functions, the "best" security is unattainable without restricting the class of implementations (e.g., to testable/pure states).
Unifying Quantum Security Notions: By introducing SEQ security for general quantum channels, the paper provides a unified, simulation-based security notion that captures the limitations imposed by quantum mechanics (gentle measurement) while remaining achievable in oracle models.
New Obfuscation Primitive: The concept of Stateful Quantum iO is a significant theoretical contribution. It bridges the gap between one-time security and many-time obfuscation, suggesting that to secure stateful quantum programs, one must consider their behavior over multiple queries, not just a single execution.
Practical Pathways: While the plain model construction remains open (requiring Stateful iO in the plain model), the results in the oracle model provide a concrete blueprint for what is achievable. The paper suggests that if Stateful iO can be constructed in the plain model (similar to how classical iO is pursued), then best-possible testable OTPs will follow.

Summary Table

Concept	Status	Key Insight
Generic Best-Possible OTP	Impossible	Requires distinguishing indistinguishable lossy/injective modes; impossible even for randomized classical functions.
Testable OTP	Achievable (Oracle)	Restricting to programs with reflection oracles allows for best-possible security via SEQ.
SEQ Security	Achievable (Oracle)	Generalized to all quantum channels; serves as the "best-possible" benchmark for testable OTPs.
Stateful Quantum iO	Achievable (Oracle)	A new primitive that obfuscates state-evolving programs; implies best-possible testable OTPs.
Plain Model Construction	Open	Requires constructing Stateful Quantum iO in the plain model (no oracles).

In conclusion, this paper provides a comprehensive map of the landscape for One-Time Programs in the quantum era. It definitively rules out generic best-possible compilers, identifies the correct security notion (SEQ) for testable programs, and proposes Stateful Quantum iO as the critical missing piece for realizing these programs in the real world.