💻 computer science

Withdrawability in Fiat-Shamir with aborts constructions

This paper extends the concept of withdrawable signatures to the Fiat-Shamir with aborts paradigm by proposing an abstract construction with security proofs and providing a concrete instantiation based on a no-hint Dilithium-style scheme, while noting the minor adjustments required for production ML-DSA with hints.

Original authors: Ramses Fernandez-Valencia

Published 2026-07-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ramses Fernandez-Valencia

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 you have a very special, unbreakable digital stamp. Once you put this stamp on a document, it's usually permanent. You can't take it back, and no one can pretend you didn't sign it. This is how most digital signatures work today.

But what if you wanted a "soft" signature? One that you could take back if you changed your mind, before anyone else sees it, without destroying your ability to sign other things?

This paper introduces a new kind of digital signature called a "Withdrawable Signature." It's designed to work in a future where powerful quantum computers might break today's security, so it uses "lattice-based" math (think of it as a complex, multi-dimensional maze) instead of the old math that quantum computers can solve easily.

Here is how the paper breaks it down, using simple analogies:

1. The Problem: The "Permanent Stamp"

Usually, when you sign a digital contract, it's like stamping a document with wet ink that dries instantly. Once it's dry, it's there forever.

The Issue: Sometimes you need to change your mind. Maybe you signed a smart contract on a blockchain, but the deal fell through. Or maybe you cast a vote in a digital election but realized you made a mistake before the votes were counted.
The Goal: You need a way to say, "I signed this, but I'm taking it back," without revealing your secret password (private key) or messing up your other signatures.

2. The Solution: The "Magic Double-Envelope"

The authors created a system where a signature starts as a secret, withdrawable note and can later be turned into a public, confirmed stamp.

Think of it like this:

Step 1: The Withdrawable Signature (The Secret Note)
Imagine you write a note and put it inside a special, locked box. You give this box to a specific person (the "designated verifier").
- Only that specific person has the key to open the box and read the note.
- The Magic Trick: To anyone else (even a spy watching you), the box looks like random noise. They can't tell if you put the note in, or if the recipient wrote the note themselves and put it in the box. It's a perfect "he said, she said" situation. This is called Ambiguity.
- Because of this ambiguity, you can say, "I never signed that," and the recipient can't prove you did, unless you decide to confirm it.
Step 2: The Confirmation (The Public Stamp)
If you decide you do want the signature to be permanent, you perform a "Confirmation" step.
- You take the secret note out of the box and use your secret key to generate a standard, public signature that proves, "Yes, I definitely wrote this."
- Now, anyone can see it, and no one can deny it.

3. The "Quantum-Proof" Maze (Fiat-Shamir with Aborts)

The paper builds this system using a specific type of math called Fiat-Shamir with Aborts.

The Analogy: Imagine trying to solve a giant, complex maze to prove you know the way.
The "Abort" Part: Sometimes, you might take a wrong turn that accidentally reveals a secret about how you solved the maze. If that happens, you simply say, "Abort! I made a mistake," and you start over from the beginning. You keep trying until you find a path that proves you know the way without leaking any secrets.
This "try and retry" method is what makes the signature secure against quantum computers.

4. How They Built It (The "No-Hint" Dilithium)

The authors took a famous existing quantum-proof signature scheme called Dilithium (which is like a standard, high-security stamp) and modified it.

They stripped away a small "hint" feature that Dilithium usually uses to make things faster.
Why? Removing the hint makes the math "perfect." It ensures that the secret note is truly indistinguishable from a fake one, even to a supercomputer.
They wrapped this modified signature in an encryption layer. This is like putting the "Magic Double-Envelope" inside a secure courier service that only the intended recipient and the sender can open.

5. Why This Matters (According to the Paper)

The paper claims this construction achieves two main things:

Unforgeability: Even if a hacker steals the recipient's secret key, they still cannot forge a signature that looks like it came from the original signer. Only the original signer can turn the "withdrawable" note into a "confirmed" stamp.
Withdrawability: As long as you haven't confirmed the signature, no one (not even the recipient) can prove who wrote the note. It's a perfect tie.

Summary

The paper presents a new way to sign digital documents that allows you to revoke your signature before it becomes permanent. It uses a "secret note" that only a specific person can read, which can later be turned into a "public stamp." This system is built on "quantum-proof" math (lattices) and uses a "try-and-retry" method to ensure no secrets are leaked during the process.

Crucially, the paper focuses entirely on the mathematical construction and security proofs. It mentions that this could be useful for blockchain or voting systems, but it does not claim to have built a working blockchain or voting app yet; it only provides the secure "engine" that could power such things in the future.

Technical Summary: Withdrawability in Fiat–Shamir with Aborts Constructions

Problem Statement
Digital signatures traditionally provide permanence; once generated, a signature cannot be revoked without compromising the signer's private key or invalidating other signatures. This limitation poses challenges in dynamic environments such as blockchain smart contracts, decentralized e-voting, and escrow services, where participants may need to revoke commitments based on changing conditions. Liu, Baek, and Susilo [LBS23] introduced "withdrawable signatures," a primitive allowing a signer to generate a signature verifiable only by a designated verifier, which can later be transformed into a publicly verifiable signature. However, their construction relies on classical assumptions (Discrete Logarithm, Diffie-Hellman) vulnerable to quantum attacks.

The challenge addressed by this paper is to extend the concept of withdrawable signatures to the post-quantum setting, specifically within the Fiat–Shamir with aborts paradigm. This paradigm is the foundation of leading post-quantum signature schemes like Dilithium (ML-DSA) and HAETAE. A specific structural hurdle exists: the original Liu–Baek–Susilo construction relies on a "free" Diffie-Hellman shared secret to achieve signer/verifier ambiguity and designation simultaneously. Lattice-based cryptography lacks a cheap, efficient analogue for this shared secret, necessitating a new architectural approach.

Methodology
The paper proposes a general abstract construction for withdrawable signatures based on the Fiat–Shamir with aborts paradigm, followed by a concrete instantiation.

Abstract Construction:
The authors define a framework comprising five algorithms: KeyGen, WSign (withdrawable signing), WSVerify (withdrawable verification), Confirm, and CVerify.
- Core Mechanism: The scheme utilizes a two-party Fiat–Shamir with aborts OR-proof. The withdrawable signature consists of two branches: one generated by the signer (using their secret key) and one simulated by the signer to mimic the verifier's branch.
- Ambiguity: Because both the signer and the designated verifier can generate a valid branch (the signer by simulating the verifier, and the verifier by simulating the signer), the origin of the signature is indistinguishable to third parties.
- Confirmation: To make the signature publicly verifiable, the signer runs the Confirm algorithm, which generates a standard, ordinary signature over the message, the public key set, and the withdrawable signature itself. This binds the withdrawable signature to the signer's identity without requiring the re-derivation of shared randomness (which is infeasible in lattice-based FS-with-aborts due to rejection sampling).
Strong Designated-Verifier (SDVS) Variant:
To ensure the withdrawable signature is not publicly verifiable (matching the Liu–Baek–Susilo model), the authors encrypt the public core of the signature using a Public Key Encryption (PKE) scheme (specifically, the CPA-secure module-LWE encryption underlying ML-KEM/Kyber).
- The signature is encrypted to both the designated verifier's public key and the signer's public key. This allows the verifier to decrypt and verify, and allows the signer to decrypt and perform the Confirm operation statelessly.
- This approach replaces the Diffie-Hellman shared secret with explicit encryption, acknowledging that lattice-based Non-Interactive Key Exchange (NIKE) is currently too inefficient for this purpose.
Concrete Instantiation:
The abstract framework is instantiated using a no-hint, full- $t$ Dilithium-style construction.
- The authors utilize a variant of Dilithium that does not use "hints" (the $t_1$ / $t_0$ split), ensuring that the simulator for the zero-knowledge proof is perfect ( $\varepsilon_{zk} = 0$ ).
- This choice simplifies the security proofs, particularly for the withdrawability property, by avoiding the small statistical errors associated with hint-based schemes.

Key Contributions

General Framework: The paper introduces the first abstract construction for withdrawable signatures based on the Fiat–Shamir with aborts paradigm, bridging the gap between the Liu–Baek–Susilo model and post-quantum lattice cryptography.
Security Proofs:
- Unforgeability: The scheme is proven unforgeable under insider corruption (where the adversary holds the verifier's secret key) in the (Quantum) Random Oracle Model (QROM). The proof reduces to the EUF-CMA security of the underlying lattice signature scheme (SelfTargetMSIS/MSIS assumptions).
- Withdrawability: The scheme is proven withdrawable, meaning an adversary cannot distinguish whether a signature was generated by the signer or the designated verifier. For the no-hint instantiation, this property is statistical (information-theoretic) with $\varepsilon_{zk} = 0$ , relying on the perfect non-abort honest-verifier zero-knowledge (naHVZK) of the underlying identification scheme and the min-entropy of commitments.
Adaptation to Post-Quantum Constraints: The paper explicitly addresses the lack of a lattice-based Diffie-Hellman shared secret. It demonstrates that designation can be achieved via Public Key Encryption (PKE) rather than NIKE, and that signer ambiguity can be achieved via OR-proofs rather than algebraic symmetry.

Results

Concrete Security: For the no-hint Dilithium instantiation, the paper provides concrete security bounds. The unforgeability advantage is bounded by the underlying scheme's security plus a negligible term related to random oracle programming ( $2^{-1024}$ ). The withdrawability advantage is bounded by $1/2$ plus a negligible statistical term, effectively achieving perfect ambiguity for the designated verifier in the no-hint case.
Comparison: The authors provide a detailed comparison with the Liu–Baek–Susilo scheme (Table 2). While the lattice construction requires additional key material (encryption keys) and results in larger signatures (due to encryption overhead), it gains two significant properties: the withdrawable signature is pseudorandom (hiding its existence from third parties), and non-transferability against the designated verifier is perfect (statistical) rather than computational.

Significance
The paper claims significance as a necessary adaptation of the withdrawable signature primitive to the post-quantum era. It establishes that withdrawability is achievable in lattice-based cryptography without relying on inefficient or non-existent lattice analogues of Diffie-Hellman. By separating the mechanisms of designation (encryption) and ambiguity (OR-proofs), the authors provide a robust, provably secure construction that maintains the security properties of underlying schemes like Dilithium while adding the critical flexibility of signature revocation. The work suggests that these constructions could enhance quantum resistance in blockchain systems where transaction revocation is desirable but traditionally difficult to implement.