⚛️ quantum physics

A Simple and Efficient One-Shot Signature Scheme

This paper presents a new, simple, and efficient one-shot signature scheme that significantly improves upon the Shmueli-Zhandry construction by reducing key and signature sizes from cubic to quadratic complexity, achieving perfect correctness, and enabling strong signature incompressibility to correct and recover applications from recent related work.

Original authors: Andrew Huang, Vinod Vaikuntanathan

Published 2026-07-28

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Andrew Huang, Vinod Vaikuntanathan

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

Imagine a world where the rules of physics allow for a very special kind of digital lock. In our current world, if you have a key to a safe, you can open it as many times as you want. But in the strange, quantum realm of future cryptography, scientists have discovered a way to make a "one-shot" key. Think of it like a magical, self-destructing ticket. You can use this ticket to unlock a door and prove you were there, but the moment you use it, the ticket turns into dust. You can't use it again, and you can't make a copy of it to use later. This isn't just a cool magic trick; it's a powerful tool that could lead to unbreakable digital money, unforgeable certificates of quantum power, and even a way to burn digital secrets so they can never be recovered.

For a long time, building these "one-shot signatures" was like trying to build a skyscraper out of toothpicks. It was theoretically possible, but the designs were incredibly clumsy, requiring massive amounts of quantum memory (like a library of books just to sign a single letter) and taking a long time to work. A recent breakthrough showed it could be done, but the resulting "keys" were huge and the process was slow. Now, a new paper by Andrew Huang and Vinod Vaikuntanathan from MIT has come along with a sleek, efficient redesign. They've figured out how to build these self-destructing digital tickets using much less space and time, making the whole idea practical for real-world use.

The Self-Destructing Ticket

The paper tackles a problem in quantum cryptography called "One-Shot Signatures" (OSS). To understand the achievement, imagine you are a spy trying to send a secret message. In the old, clumsy version of this spy game, the "signature" (the proof that you sent the message) was like a giant, heavy backpack. If you wanted to sign a short note, you had to carry a backpack full of $\Theta(\lambda^4)$ qubits (the quantum equivalent of bits). If you wanted to sign a longer message, the backpack got even bigger, and the process of signing was slow and complicated, often requiring the spy to perform a complex dance of quantum measurements just to get the job done.

The authors of this paper say, "We can do better." They have designed a new, streamlined system where the "backpack" is much smaller. Instead of a massive $\Theta(\lambda^4)$ qubit load, their new scheme only needs a backpack of $\Theta(\lambda^2)$ qubits. That's a huge reduction in size. Furthermore, the signatures they produce are also smaller, shrinking from $\Theta(\lambda^3)$ bits down to $\Theta(\lambda^2)$ bits.

How They Did It: The "Image" Trick

The previous method, created by Shmueli and Zhandry, was like trying to find a specific needle in a haystack by looking at the straw (the pre-image). It was a bit like trying to guess a password by working backward from the scrambled result, which required a lot of trial and error and a lot of quantum "rewinding" (trying again and again until you get it right). This process was inefficient and sometimes failed to produce a valid signature, meaning the spy might get stuck with a useless ticket.

Huang and Vaikuntanathan flipped the script. Instead of looking for the needle in the straw, they decided to look for the straw in the needle. In their new construction, the "signature" is found directly in the "image" of the function. They use a clever quantum search algorithm (Grover's search) to find the right path through the data. This approach is like having a map that leads directly to the treasure, rather than digging randomly. Because they are looking in the right place, the process is "perfectly correct." This means that every single time you try to sign a message, the system guarantees it will work. There is no chance of failure, no "oops, the ticket didn't work" moments.

Why This Matters: The Quantum Fire

The paper doesn't just stop at making smaller backpacks. They show that their new, efficient signatures can be used to build something called "Quantum Fire." Imagine you have a digital document that you want to share with a friend, but you want to make sure that once they read it, the document is instantly and permanently destroyed, and no one can ever make a copy of it. This is the concept of "Quantum Fire."

Previous attempts to build this fire relied on the old, clumsy signatures. The authors point out that the old method had a fatal flaw: it wasn't "incompressible." In simple terms, a hacker could take the old, bulky signatures and squeeze them down into a tiny, compressed file that still contained enough information to forge new signatures later. It was like a fire that could be put out and re-lit.

The new scheme fixes this. Because their signatures are structured differently, they are "incompressible." You cannot shrink them down without losing the ability to verify them. This means the "Quantum Fire" they build is real and reliable. Once the digital secret is burned, it stays burned. They also use this to fix a bug in a recent paper by Çakan, Goyal, and Shmueli, recovering the ability to create these secure, uncopyable digital secrets.

The Bottom Line

The authors have proven that it is possible to create a one-shot signature scheme that is:

Efficient: It uses significantly less quantum memory ( $\Theta(\lambda^2)$ qubits) and produces smaller signatures ( $\Theta(\lambda^2)$ bits) compared to the previous best ( $\Theta(\lambda^4)$ and $\Theta(\lambda^3)$ ).
Simple: It avoids the complex, multi-step quantum circuits that made the old method slow and hard to understand.
Perfect: It works every single time, with zero chance of failure.
Secure: It prevents hackers from compressing the data to cheat the system, enabling the creation of "Quantum Fire" and other advanced security tools.

While the paper notes that there is still room for improvement (perhaps making the keys even smaller in the future), they have successfully moved the goalposts from "theoretically possible but impractical" to "efficient and ready for the next generation of quantum security." They have turned a clunky, self-destructing brick into a sleek, self-destructing feather.

Technical Summary: A Simple and Efficient One-Shot Signature Scheme

Problem Statement

One-shot signatures (OSS) are a uniquely quantum cryptographic primitive that allows a user to generate a public verification key ($pk$) and a secret quantum signing state ( $|sk\rangle$ ). The signing state enables the production of a valid signature for exactly one message of the user's choice; upon signing, the state "self-destructs," preventing the generation of a second signature. While OSS implies powerful primitives like quantum money, quantum lightning, and quantum fire, constructing them efficiently has remained a challenge.

The recent breakthrough by Shmueli and Zhandry (SZ) [SZ25] provided the first construction of OSS. However, their scheme suffers from significant inefficiencies:

Bit-by-bit Signing: The SZ construction inherently signs messages one bit at a time. To sign a $\lambda$ -bit message, the scheme requires parallel repetition, leading to a linear blowup in key and signature sizes.
Complex Amplification: To achieve strong security, SZ relies on the Dall'Agnol and Spooner (DS) [DS22] reduction, which uses complex quantum rewinding or Quantum Singular Value Transform (QSVT) circuits (specifically alternating projections/Marriott-Watrous style algorithms). This introduces an additional $\Theta(\lambda)$ overhead in the signing key size.
Imperfect Correctness: The SZ scheme has a negligible correctness error, meaning the signing algorithm may fail to produce a valid signature.
Resource Costs: In the oracle model, the SZ scheme results in signing keys of size $\Theta(\lambda^4)$ qubits and signatures of size $\Theta(\lambda^3)$ bits. In the plain model, these parameters are even larger.

Furthermore, a subsequent work by Çakan, Goyal, and Shmueli (CGS) [C¸GS25] attempted to use OSS to construct "public-key quantum fire" but relied on an incompressibility property that the SZ scheme does not satisfy.

Methodology

This work proposes a new, direct construction of one-shot signatures that avoids the complex reductions and parallel repetitions required by previous approaches. The core methodology involves a fundamental shift in how the signature is generated:

1. Direct Construction via Grover Search

Instead of the SZ approach, which searches for a preimage of a hash function starting with a specific bit (requiring complex amplification to handle the "sum-binding" problem), this work searches for a signature in the image of a function.

The Setup: The scheme utilizes a random permutation $\Pi$ and a family of subspaces defined by matrices $\mathbf{A}_y$ and vectors $\mathbf{b}_y$ . The signing state $|sk\rangle$ is a uniform superposition over an affine subspace (coset) defined by these parameters.
The Signing Process: To sign a bit $b$ , the algorithm does not look for a preimage starting with $b$ . Instead, it uses a Grover search algorithm to transform the initial superposition state into a state where the coset vectors have a specific prefix $b$ in their image under an auxiliary function $\mathcal{P}$ .
Oracle Usage: The signing algorithm iteratively applies two reflection oracles:
1. A phase oracle that marks states where the image prefix matches the message bit.
2. A dual oracle $\mathcal{D}$ that reflects across the dual of the subspace.
  By iterating this process $\ell$ times (where $\ell$ is the message length), the algorithm rotates the state to a superposition of valid signatures for the entire message. Measuring this state yields a valid signature.

2. Ensuring Perfect Correctness

The authors address the issue of imperfect correctness by carefully designing the sampling of the matrix $\mathbf{A}_y$ . They ensure that the first column of $\mathbf{A}_y$ is non-zero, guaranteeing that for any public key $y$ , the coset contains vectors starting with both 0 and 1. This structural guarantee ensures the Grover search always succeeds, achieving perfect correctness (probability 1).

3. Handling Polynomial-Length Messages

Rather than repeating the single-bit scheme $\lambda$ times (which causes the $\lambda$ blowup), the scheme signs the entire $\lambda$ -bit message in a single shot. The Grover search is adapted to sign bit-by-bit within a single execution, compressing the $\lambda$ signatures into a single signature of size $\Theta(\lambda^2)$ . For arbitrary polynomial lengths, a standard hash-and-sign transformation is applied.

4. Incompressibility and Quantum Fire

The paper identifies a flaw in the CGS [C¸GS25] claim that the SZ scheme satisfies "strong signature incompressibility." The SZ scheme fails this property because the signing algorithm requires access to both the forward and inverse oracles ( $\mathcal{P}$ and $\mathcal{P}^{-1}$ ), allowing an adversary to generate signatures for keys outside a compressed list.
The new construction modifies the scheme so that signing only requires the dual oracle $\mathcal{D}$ , while verification uses a separate oracle $\mathcal{D}_0$ . This separation enables a proof of strong signature incompressibility, thereby recovering the validity of the quantum fire applications proposed by CGS.

Key Contributions and Results

Efficiency Improvements

The paper achieves significant reductions in resource complexity compared to the SZ construction:

Signing Key Size: Reduced from $\Theta(\lambda^4)$ qubits to $\Theta(\lambda^2)$ qubits.
Signature Size: Reduced from $\Theta(\lambda^3)$ bits to $\Theta(\lambda^2)$ bits.
Public Key Size: Reduced from $\Theta(\lambda^3)$ bits (oracle model) and $\Theta(\lambda^5)$ bits (plain model) to $\Theta(\lambda^2)$ bits (oracle model) and $\Theta(\lambda^4)$ bits (plain model).
Runtime: The signing algorithm requires significantly fewer oracle queries, avoiding the $\Theta(\lambda)$ overhead associated with QSVT/rewinding circuits.

Security and Correctness

Perfect Correctness: Unlike SZ, the new scheme guarantees that a valid signature is produced with probability 1.
Strong Security: The scheme achieves strong unforgeability, meaning it is infeasible to produce a valid signature for a different message or a different signature for the same message.
Incompressibility: The scheme satisfies strong signature incompressibility, a property required for advanced applications like quantum fire.

Theoretical Results

The paper formalizes these improvements in two main theorems:

Theorem 1.1: Establishes the existence of efficient OSS schemes for polynomially long messages with perfect correctness in both the classical oracle model (unconditionally) and the plain model (assuming post-quantum indistinguishability obfuscation and LWE).
Theorem 1.2: Demonstrates that the new incompressible OSS scheme enables the construction of public-key quantum fire and key-fire schemes with perfect correctness, correcting the errors in the CGS [C¸GS25] work.

Significance

The paper claims to provide a "simple, direct, and efficient" alternative to the state-of-the-art one-shot signature schemes. By bypassing the complex reductions (DS [DS22]) and parallel repetition strategies used in previous works, the authors achieve a quadratic improvement in key and signature sizes.

The significance of this work is twofold:

Practical Efficiency: It makes quantum signature schemes significantly more feasible by reducing the qubit and bit requirements from quartic/cubic to quadratic scales.
Foundational Correction: It rectifies a critical gap in the literature regarding the incompressibility of OSS. By fixing the incompressibility property, the paper validates and enables the construction of "quantum fire" and related primitives, which were previously claimed to be possible but relied on a flawed assumption about the SZ scheme.

The authors note that while they have optimized the parameters significantly, further improvements to $\Theta(\lambda)$ in the oracle model may require entirely new techniques, as the current bottleneck lies in the analysis of the dual-free case. Similarly, improving the plain model parameters remains an open problem.