arXiv CSopen access

Withdrawability in Fiat-Shamir with aborts constructions

Withdrawability in Fiat–Shamir with aborts constructions Ramses Fernandez

arXiv:2607.05831v1 [cs.CR] 7 Jul 2026

Fairgate Labs

Abstract. This article presents an extension of the work performed by Liu, Baek and Susilo [LBS23] on withdrawable signatures to the Fiat–Shamir with aborts paradigm. We introduce an abstract construction, and provide security proofs for this proposal. As an instantiation, we provide a concrete withdrawable signature scheme based on a no-hint, full-t Dilithium-style Fiat–Shamir-with-aborts construction [DLL+ 18]; adapting to production ML-DSA (with hints) introduces a small εzk term. Keywords: Withdrawability · Digital signatures · Module Learning with Errors

1

Introduction

Digital signatures serve as a fundamental cryptographic mechanism that enables entities to bind their identities to pieces of information. The essential purpose of a digital signature is to allow a signer, who has established a public key pk, to sign messages using their private key sk in a way that enables anyone knowing pk to verify both the message’s origin and its integrity during transit. An important paradigm for the creation of digital signatures is the Fiat–Shamir transform, which converts interactive identification protocols into non-interactive digital signature schemes. Starting with a three-move identification protocol, where a prover demonstrates knowledge to a verifier through commitment, challenge, and response steps, the transform replaces the verifier’s random challenge with a hash function applied to both the commitment and the message. This creates a digital signature scheme where the signing algorithm computes a commitment, generates a challenge by hashing the commitment with the message, and produces a response using the secret key. The Schnorr signature scheme is perhaps the most well-known application of the Fiat– Shamir transform, which has gained particular attention due to its security characteristics and its valuable properties, such as signature aggregation. These advantages make Schnorr signatures especially attractive for blockchain applications where transaction size reduction and privacy enhancement are crucial considerations. The impact of digital signatures is particularly important in blockchain technology, where this primitive extends beyond basic transaction authentication, enabling sophisticated smart contract interactions, multi-signature schemes for enhanced security, and threshold signature systems for distributed key management. Furthermore, innovations in signature aggregation and batch verification techniques have contributed significantly to blockchain scalability solutions. E-mail: [email protected] (Ramses Fernandez)

2

Withdrawable FS

Current public-key cryptographic algorithms serve as the foundation for protecting sensitive electronic information from unauthorized access. These algorithms have successfully withstood attacks from conventional computing systems for decades, due to the hardness of their underlying mathematical problems, prime factorization and the computation of discrete logarithms. However, the emergence of quantum computing presents a significant challenge to this security paradigm, as Shor’s algorithm demonstrates the potential to solve both the prime factorization and the computation of discrete logarithms efficiently. This means that quantum computers possess computational capabilities that could potentially compromise current cryptographic methods, exposing vulnerable data and information. To address this impending challenge, new cryptographic approaches are being designed to withstand attacks from both traditional computers and future quantum systems. These methods rely on problems, such as lattices, error-correcting codes or isogenies of elliptic curves, which have enhanced mathematical structure, leading to computational problems assumed to be hard both for classical and quantum computers. This framework is known as post-quantum cryptography, which represents a critical advancement in information security, ensuring that digital assets remain protected against evolving technological threats. The Fiat–Shamir transform can be extended to lattices, leading to the Fiat–Shamir with aborts paradigm due to Lyubashevsky [Lyu09]. Fiat–Shamir with aborts provides a framework for constructing digital signature schemes with provable security. This methodology addresses the challenge of generating signatures from lattice-based one-way functions by introducing a controlled rejection sampling technique, aborting. When a potential signature might reveal information about the secret key, the signing algorithm simply aborts and restarts the process. This paradigm converts an interactive identification protocol with a non-negligible probability of aborting into a signature scheme through iterative execution until a successful completion occurs, the aborting procedure. This transformation eliminates the need for interaction by substituting the verifier’s challenge with a hash function evaluation, which security analyses treat as a random oracle. Amongst the main constructions based on the Fiat–Shamir with aborts mechanism, we find Dilithium [DLL+ 18] and HAETAE [CCD+ 24]. Dilithium derives its security from the difficulty of solving certain lattice problems, specifically the Module Learning with Errors and Module Short Integer Solution problems. The importance of the scheme comes from the effective balance between security, signature size, and computational efficiency, making it practical for real-world implementations. HAETAE has been specifically designed to produce more compact and efficiently maskable signatures. While built upon the Fiat– Shamir with aborts paradigm underpinning Dilithium, HAETAE introduces design choices that optimize the complexity-to-compactness ratio, which is particularly important in space-constrained implementation scenarios. Digital signatures are designed to provide authenticity, integrity, and non-repudiation for signed messages. Once a signature is created, it remains valid indefinitely, and the signer cannot rescind it. This permanence, while typically considered a feature, raises an important question: is it possible for signers to efficiently revoke their signatures without compromising their private keys or affecting the validity of their other signatures? Liu, Baek, and Susilo address this challenge by introducing the concept of withdrawable signatures [LBS23], offering a practical and secure mechanism for signature revocation in situations where this capability is desirable. The practical applications of withdrawable signatures span multiple domains where signature revocation capability is essential without compromising the signer’s private key. In blockchain-based smart contracts, these signatures enable participants to commit to contract conditions while maintaining the ability to revoke their commitment, particularly

Ramses Fernandez

3

valuable when contract fulfillment depends on multiple parties or external conditions. Within decentralized e-voting systems, withdrawable signatures provide voters the security to cast their votes while retaining the flexibility to modify their choices before final vote tabulation, allowing voters to respond to new information or developments during the voting period. Additionally, in decentralized escrow services, these signatures facilitate multi-party transactions by allowing participants to revoke their signatures if circumstances change or disputes arise, without compromising the security of other parties’ signatures.

1.1

Contributions

This paper builds upon the research conducted by Liu, Baek, and Susilo on withdrawable signatures [LBS23] to present a general methodology for constructing post-quantum withdrawable signatures based on Lyubashevsky’s Fiat–Shamir with aborts paradigm [Lyu09]. The work first introduces a comprehensive abstract construction that takes a mechanism based on the Fiat–Shamir with aborts paradigm as its starting point and extends it to incorporate withdrawability features. To demonstrate the practical applications of this abstract framework, the paper presents a concrete withdrawable construction from a no-hint, full-t Dilithium-style variant [DLL+ 18]; the no-hint variant keeps the naHVZK proof exact (perfect, εzk = 0), whereas production ML-DSA requires handling hints and incurs a small εzk . The integration of withdrawability features with post-quantum cryptography addresses two crucial challenges in modern cryptographic systems. First, it provides the flexibility to revoke signatures when needed, a capability increasingly important in dynamic digital environments. Second, it ensures this functionality remains secure against quantum computing threats.

1.2

Related work

The research in this paper revolves around three gravity centres, namely: the work done by Lyubashevsky, the construction of Liu, Baek and Susilo, and the digital scheme Dilithium. The Fiat–Shamir heuristic [FS] provides a method for transforming public-coin interactive proof systems into digital signatures. This transformation works by substituting the verifier’s public coin tosses with hash function evaluations. In the random oracle model (ROM), these hash functions are treated as uniform functions that adversaries can access through classical computing methods. Schnorr’s signature scheme stands as a prominent implementation of the Fiat–Shamir heuristic, with its security fundamentally based on the discrete logarithm problem. However, the emergence of quantum computing necessitates two critical adaptations to this framework. First, the discrete logarithm hardness assumption must be replaced with quantum-resistant alternatives. Second, the security model must account for quantum access to the random oracle (QROM), as quantum adversaries can query the hash function in superposition. Lyubashevsky’s work [Lyu09] introduced an innovative lattice-based signature scheme that builds upon Schnorr’s design while incorporating abortion as a crucial modification. The abort mechanism ensures that the signature distribution remains independent of the signing key, preventing potential attacks against the signature scheme. The protocol manages these aborts through a loop structure, continuing iterations until a successful execution occurs without an abort. This modified approach, known as Fiat–Shamir with aborts, maintains the fundamental concept of replacing non-final verifier steps with hash function evaluations while adapting

4

Withdrawable FS

to the requirements of lattice-based cryptography. The integration of the abort mechanism represents a significant advancement in developing quantum-resistant signature schemes, providing a robust framework for cryptographic security in the post-quantum era. On the other hand, Liu, Baek and Susilo propose a designated-verifier signature scheme that introduces withdrawability to digital signatures. Their construction generates a withdrawable signature σ for a message µ, distinct from conventional signature schemes. The scheme’s construction centers on a transformation mechanism. When a signer generates a withdrawable signature, it remains verifiable only by the designated verifier. The signature can then follow two paths: it either remains in its withdrawable state through signer inaction, effectively withdrawing the signature, or undergoes transformation through a “Confirm” algorithm. This algorithm converts the withdrawable signature σ into a confirmed signature σ̃, which becomes verifiable through both parties’ public keys while maintaining a deterministic relationship to σ. The formal construction involves two entities, signer and verifier, with their public keys comprising a set π = {pks , pkv }, respectively. The scheme utilizes the underlying signature structure to construct a withdrawable signature σ specifically designated for the verifier. Subsequently, using the secret key sks and σ, the signer can generate a verifiable signature for µ through the public key set π. This confirmed signature σ̃ maintains a cryptographic link to the original withdrawable signature σ via the public key set π, ensuring the signature transformation’s verifiability and traceability. Finally, we find Dilithium [DLL+ 18], which builds upon the Fiat–Shamir with aborts paradigm. The scheme operates over module lattices, specifically using the module learning with errors (MLWE) and the module short integer solution (MSIS) problems as its primary security foundations. Its construction employs a ring Rq = Zq [x]/(xn + 1) with carefully chosen parameters n and q. The signature scheme utilizes matrices and vectors over this ring, with dimensions selected to balance security and efficiency. The key generation in Dilithium produces a public key containing a matrix A ∈ Rqk×l and a vector t = As1 + s2 , where s1 and s2 are secret vectors with small coefficients. The signing process involves generating a masking vector y, computing w = Ay, and using a challenge value c derived from the message and w to produce the signature. The scheme incorporates rejection sampling to ensure signature security, leading to probabilistic signature generation.

2

Preliminaries

2.1

Notation

We write R and Rq to denote the rings Z[x]/(xn + 1) and Zq [x]/(xn + 1) respectively, where q is an integer. We will denote vectors by bold letters, and regular font letters denote elements in R or Rq . Unless otherwise specified, all vectors are assumed to be column vectors. Bold upper-case letters denote matrices. $

If S is a set, then a ← − S means that a is chosen uniformly at random from S. All logarithms are assumed to be base 2, and the hash function H(·, ·) will operate on the concatenation of its arguments. For any even positive integer α, we define r′ = r mod± α to be the unique element r′ in the range − α2 < r′ ≤ α2 such that r′ ≡ r mod α. For any odd positive integer α, we α−1 ′ define r′ = r mod± α to be the unique element r′ in the range − α−1 2 ≤ r ≤ 2 such that ′ r ≡ r mod α. We refer to these operations as centered reductions modulo α.

Ramses Fernandez

5

For any positive integer α, we define r′ = r mod + α to be the unique element r′ in the range 0 ≤ r′ < α such that r′ ≡ r mod α. When the specific representation is not significant, we simply write r mod α. Pn−1 ± i For an element w ∈ Zq , we denote ∥w∥∞ to mean p |w mod q|. For w = i=0 wi x ∈ 2 2 R, we define ∥w∥∞ = maxi ∥wi ∥∞ and ∥w∥ = ∥w p0 ∥∞ + · · · + ∥wn−1 ∥∞ . For w = k 2 (w1 , . . . , wk ) ∈ R : ∥w∥∞ = maxi ∥wi ∥∞ and ∥w∥ = ∥w1 ∥ + · · · + ∥wk ∥2 . We denote by Sα the set of all elements w ∈ R such that ∥w∥∞ ≤ α for α ∈ R. There will be an abuse of notation: we write S, with no subindex, to indicate that bounds in this case are given by the underlying scheme. From [DLL+ 18] we set β as the maximum possible coefficient of csi , γ1 is large enough so the signature does not reveal the secret key and small enough so that the signature is not forged, γ2 is the low-order rounding bound with 2γ2 | q − 1 (concretely γ2 = (q − 1)/88 for level 2 and (q − 1)/32 for levels 3 and 5, so γ2 = ̸ γ1 /2 in general), and η is a small integer. We write C = Bτ for the challenge set of weight τ (Definition 10); the
concrete weights are τ ∈ {39, 49, 60} for the three parameter sets, and M = |C| = 2τ nτ . Fix an efficiently invertible bijection ι : ZM → C (for instance the indexing underlying SampleInBall), with inverse ι−1 : C → ZM . We use a challenge hash HM : {0, 1}∗ → ZM . Let HB(·) denote the recoverable (high-order) part of a commitment, i.e. for every accepted transcript HB(Az − ct) = HB(Ay); in Dilithium HB(·) = HighBits(·, 2γ2 ). Let PKE = (KGene , Enc, Dec) be a public-key encryption scheme satisfying ciphertext pseudorandomness: for honestly generated ek and any message K, Enc(ek, K) is computationally indistinguishable from a uniform element of the ciphertext space given ek (but not dk); we write its advantage Advpr PKE . Ciphertext pseudorandomness implies both IND- CPA and key-privacy (anonymity), but neither of those implies it. We use PKE to encrypt a chosen symmetric key K. The CPA-secure module-LWE encryption underlying ML-KEM (Kyber) is a candidate instantiation: its ciphertext components are pseudorandom under decisional MLWE, and pseudorandomness is understood with respect to the actual (compressed) ciphertext encoding space, up to the standard compression/statistical terms. Let G : {0, 1}κ → {0, 1}∗ be a pseudorandom generator (XOF). Each party holds, in addition to its lattice keys, an encryption key pair (ek, dk) ← KGene (1κ ); for a key set π = {pks , pkv } we write eks , ekv (resp. dks , dkv ) for the signer’s and verifier’s encryption keys. Public parameters pp ← Setup(1κ ) fix the common matrix A ∈ Rqk×l (with the PKE and PRG descriptions); every key pair is generated as (pk, sk) ← KeyGen(pp) relative to the same A, so the two OR-proof branches share a module matrix.

2.2

Basic definitions

A withdrawable signature scheme involves two participating parties: signers and verifiers. The scheme operates in two primary stages: first, the generation of a withdrawable signature, and second, its transformation into a confirmed signature. Both stages are executed by the signer. Concerning the security of a withdrawable signature scheme W S, it is established through three properties, namely: correctness, unforgeability under insider corruption, and withdrawability. 1. Correctness establishes a strong relation between the verification algorithms: if a withdrawable signature σ is successfully verified through the WSVerify algorithm, then its corresponding confirmed signature σ̃ must also be verifiable through the CVerify algorithm. 2. Unforgeability under insider corruption ensures that only the original signer possesses

6

Withdrawable FS

the capability to transform a verifiable withdrawable signature σ (generated using sks for verifier pkv ) into its corresponding confirmed signature σ̃. This requirement holds even when an adversary has obtained the verifier’s secret key skv , maintaining the exclusive control of the signer over the confirmation process. 3. Finally, withdrawability establishes the indistinguishability of signature origin. Specifically, given a verifiable withdrawable signature σ, no PPT adversary A should be able to determine whether the signature was generated by the signer or the verifier, provided that the Confirm algorithm has not been executed on σ. This property effectively ensures that both the signer and the designated verifier possess equivalent capabilities in generating withdrawable signatures. Threat model. All results are in the (quantum) random-oracle model, stated for the classical ROM with the QROM variant noted in Remark 3. Keys are honestly generated unless stated otherwise: withdrawability is proved for honest keys (Theorem 3), and Remark 5 treats an adversarially chosen verifier key at the cost of a decisional-MLWE term. Unforgeability (Theorem 2) is under insider corruption, i.e. the adversary may hold the designated verifier’s secret key. For withdrawability we distinguish third-party adversaries (holding no secret key), defeated by the encryption layer of Section 3.3, from the designated verifier (holding dkv ), defeated by the origin ambiguity of the public core. Definition 1 ([LBS23], Section 3.2). A withdrawable signature scheme is composed of five polynomial-time algorithms KeyGen, WSign, WSVerify, Confirm, CVerify, defined as follows: • pp ← Setup(1κ ), (pk, sk) ← KeyGen(pp): Setup fixes public parameters pp, in particular the common matrix A shared by all users, and KeyGen(pp) outputs one key pair. The signer and verifier keys (pks , sks ), (pkv , skv ) are two independent invocations of KeyGen(pp) and thus share A; by convention each secret key embeds its own public key, i.e. sk = (pk, s1 , s2 , dk), so that a party can reconstruct π from its own sk. • σ ← WSign(µ, sks , π): given a message µ, a signer’s secret key sks , and a tuple π = {pks , pkv } containing both the signer’s public key pks and a designated verifier’s public key pkv from the set of all public keys P K (those output by KeyGen), the withdrawable signing algorithm generates a withdrawable signature σ. This signature is specifically bound to message µ under the signer’s identity and can only be verified by the designated verifier pkv . • 1/0 ← WSVerify(µ, skv , pks , σ): the withdrawable signature verification algorithm uses the designated verifier’s secret key skv (which includes dkv ) to return 1 iff σ is a valid withdrawable signature on µ under π = {pks , pkv }, and 0 otherwise. Among third parties only the designated verifier can run it; the signer may also recover the public core (via dks ) for confirmation. The signature is not publicly verifiable. • σ̃ ← Confirm(µ, sks , π, σ): the confirmation algorithm transforms a withdrawable signature σ into a confirmed signature σ̃. It takes as input the original message µ, the signer’s secret key sks , the public key set π, and the withdrawable signature σ. The resulting confirmed signature σ̃ serves as a publicly verifiable signature with respect to the key set π. • 1/0 ← CVerify(µ, π, σ, σ̃): the confirmed signature verification algorithm validates the authenticity of a confirmed signature σ̃ on message µ with respect to the public key set π. It takes as additional input the original withdrawable signature σ from which the confirmed signature was derived. The algorithm outputs 1 if the confirmed signature is valid and 0 otherwise.

Ramses Fernandez

7

Definition 2. A withdrawable signature scheme W S is correct if, for any security parameter κ, any public key set π, and any message µ ∈ {0, 1}∗ , when executing the sequence KeyGen, WSign, and Confirm, then the corresponding verification algorithms satisfy: WSVerify(µ, skv , pks , σ) = 1

and

CVerify(µ, π, σ, σ̃) = 1

with overwhelming probability (in the security parameter κ). Definition 3. For a PPT adversary A and security parameter κ, we define the unforgeability under insider corruption experiment ExpEUF-CMA (1κ ) using the three oracles in W S,A Algorithms 1–3. Algorithm 1 Corruption oracle OiCorrupt (·) 1: if i ̸= s then CO ← CO ∪ {i} 2: return ski 3: else return ⊥ 4: end if WSign (µ) Algorithm 2 Withdrawable signing oracle Osk s ,π

1: if (pks ∈ π) ∧ (s ∈ / CO) then 2: σ ← WSign(µ, sks , π) 3: W ← W ∪ {σ} 4: return σ 5: else return ⊥ 6: end if

Confirm (µ, σ) Algorithm 3 Confirmation oracle Osk s ,π

1: if σ ∈ W then 2: M ← M ∪ {µ} 3: σ̃ ← Confirm(µ, sks , π, σ) 4: return σ̃ 5: else return ⊥ 6: end if

Using these three oracles, we define the unforgeability experiment ExpEUF-CMA (1κ ) as W S,A follows: A withdrawable signature scheme W S is considered unforgeable under insider corruption with EUF-CMA security if, for all PPT adversaries A, there exists a negligible function negl such that: Pr[ExpEUF-CMA (1κ ) = 1] ≤ negl(1κ ). W S,A Definition 4. Let (pk0 , sk0 ), (pk1 , sk1 ) ← KeyGen(pp) be two generated public/secret key $

pairs, and let π = {pk0 , pk1 }. For a randomly selected bit b ← − {0, 1}, a security parameter κ, and a PPT adversary A, we build the withdrawability experiment ExpWithdraw (1κ ) with W S,A the oracle of Algorithm 5. With this signing oracle, we have the following experiment: A withdrawable signature scheme W S is withdrawable if, for any PPT adversary A, and in the absence of the execution of the Confirm algorithm, there exists a negligible function negl such that: Pr[ExpWithdraw (1κ ) = 1] ≤ 12 + negl(1κ ). W S,A

8

Withdrawable FS

Algorithm 4 Unforgeability experiment ExpEUF-CMA (1κ ) W S,A 1: pp ← Setup(1κ ) 2: for i = 1 to m do (pki , ski ) ← KeyGen(pp) 3: end for 4: Select s, v ∈ {1, . . . , m} where v ̸= s 5: Initialize empty sets CO ← ∅, W ← ∅, M ← ∅ O Corrupt (·), O WSign (·), O Confirm (·,·)

sks ,π sks ,π 6: (µ∗ , σ ∗ , σ̃ ∗ ) ← A i (1κ , π ∗ ) ∗ ∗ 7: if (π = {pks , pkv }) ∧ (v ∈ CO) ∧ (µ ∈ / M ) then 8: if (WSVerify(µ∗ , skv , pks , σ ∗ ) = 1) ∧ (CVerify(µ∗ , π ∗ , σ ∗ , σ̃ ∗ ) = 1) then return 1 9: end if

10: end if 11: return 0

WSign Algorithm 5 Signing oracle Osk (·) for the withdrawability experiment b ,π

1: if π = {pk0 , pk1 } then 2: σb ← WSign(µ, skb , π) 3: M ← M ∪ {µ} 4: return σb 5: else return ⊥ 6: end if

(1κ ) Algorithm 6 Withdrawability experiment ExpWithdraw W S,A 1: pp ← Setup(1κ ); for i = 0, 1: (pki , ski ) ← KeyGen(pp) $

2: π ← {pk0 , pk1 }; b ← − {0, 1}; M ← ∅ WSign Osk b ,π

(pp, π) 3: (µ∗ , st) ← A 4: σb ← WSign(µ∗ , skb , π) O WSign

5: b′ ← A skb ,π (st, σb ) 6: if (b = b′ ) ∧ (µ∗ ∈ / M ) then return 1 7: end if 8: return 0

▷ stage 1: choose challenge message ▷ stage 2: guess

Ramses Fernandez

2.3

9

Security definitions and computational assumptions

Definition 5. For a signature scheme DS = (KeyGen, Sign, Verify) and a PPT adversary A, consider the following experiment ExpEUF-CMA : A 1. The challenger B generates a key pair (pks , sks ) ← KeyGen(pp) using the system parameters SP . It provides pks to A while retaining sks to handle signature queries. Sign 2. A receives access to the signing oracle Osk (·) that computes σ ← Sign(µ, sks ) upon s request.

3. Eventually, A outputs a forgery attempt (µ∗ , σ ∗ ). Sign 4. A succeeds if Verify(µ∗ , pks , σ ∗ ) = 1 and µ∗ was not previously queried to Osk (·). s

We say that DS is (t, qs , ε)-secure under EUF-CMA if no adversary running in time t and making at most qs signing queries can succeed with probability greater than ε. Definition 6. A designated-verifier signature scheme DV S consists of four probabilistic polynomial-time algorithms operating on key pairs (pks , sks ) for signers and (pkd , skd ) for designated verifiers:   (pk, sk) ← KeyGen(pp)       σ ← Sign(µ, pk , sk )  d s DV S =   σ ← Simul(µ, pks , skd )       0/1 ← Verify(µ, pks , skd , σ) The key security property of DV S schemes is non-transferability, which states that for any message-signature pair (µ, σ) that validates under Verify, it should be computationally infeasible to determine whether σ was produced by the signer using Sign or simulated by the designated verifier using Simul, without access to the signer’s secret key sks . The formal definition of this property follows: Definition 7 (Non-transferability). For a designated-verifier signature scheme and a PPT adversary A, consider the non-transferability experiment ExpSign NonTrans,DV,A : κ Algorithm 7 Non-transferability experiment ExpSign NonTrans,DV,A (1 )

1: (pks , sks ), (pkd , skd ) ← KeyGen(pp) 2: Provide A access to oracles: Sign 3: Osk ,pk (·) : σ0 ← Sign(µ, sks , pkd ) s

d

Simul 4: Osk (·) : d ,pks

σ1 ← Simul(µ, pks , skd )

5: A outputs message µ∗ 6: σ0∗ ← Sign(µ∗ , pkd , sks );

σ1∗ ← Simul(µ∗ , pks , skd )

$

7: b ← − {0, 1} 8: Provide A with signature σb∗ 9: A outputs bit b′ 10: if b′ = b then return 1 11: else return 0 12: end if

A DV S achieves non-transferability if for any PPT adversary A, there exists a negligible function negl such that: κ κ 1 Pr[ExpSign NonTrans,DV,A (1 ) = 1] ≤ 2 + negl(1 ).

The security of our scheme rests upon three fundamental lattice-based hardness assumptions. The Module Learning With Errors (MLWE) assumption provides protection against

10

Withdrawable FS

key-recovery attacks, ensuring the confidentiality of secret keys. The SelfTargetMSIS assumption establishes the security foundation against new message forgery attempts, preventing adversaries from generating valid signatures for previously unsigned messages. Finally, the MSIS assumption is essential for achieving strong unforgeability, which prevents even slight modifications of existing signatures. Definition 8 (Module Learning With Errors (MLWE)). For integers m, k and a probability distribution D : Rq → [0, 1], the advantage of an algorithm A in solving the decisional MLWEm,k,D problem over the ring Rq is defined as: m×k AdvMLWE ; t ← Rqm ; b ← A(A, t)] m,k,D := Pr[b = 1 | A ← Rq

− Pr[b = 1 | A ← Rqm×k ; s1 ← Dk ; s2 ← Dm ; b ← A(A, As1 + s2 )] . Definition 9 (Module Short Integer Solution (MSIS)). For an algorithm A, we define its advantage function AdvMSIS m,k,γ in solving the (Hermite Normal Form) MSISm,k,γ problem over the ring Rq as:   m×k AdvMSIS ; y ← A(A) . m,k,γ (A) := Pr 0 < ∥y∥∞ ≤ γ ∧ [ I | A ] · y = 0 A ← Rq Let Bh denote the subset of elements in R that have exactly h coefficients equal to either −1 or 1, with
all remaining coefficients being 0. The cardinality of this set is given by |Bh | = 2h · nh . Definition 10 (SelfTargetMSIS). Let H : {0, 1}∗ → Bh be a cryptographic hash function. For an algorithm A, we define its advantage function as: " #
0 ≤ ∥y∥∞ ≤ γ1 ∧ H [ I | A ] · y M = c SelfTargetMSIS AdvH,m,k,γ1 (A) := Pr . A ← Rqm×k ; (y := (r, c), M ) ← A⟨H(·)⟩ (A) The above problems are hard if, for any PPT adversary A, the respective advantages are negligible. The intuition is that the MLWE assumption protects against key-recovery attacks, the SelfTargetMSIS is the assumption upon which new message forgery is based, and the MSIS assumption is needed for strong unforgeability. The decisional MLWE will be used to prove withdrawability.

3

Withdrawable signature schemes

3.1

The abstract construction

In this section we provide a global construction for withdrawable signatures based on the Fiat–Shamir with aborts paradigm and prove the unforgeability and withdrawability as described in Definition 1. This construction follows the paradigm described in [Lyu09] combined with ideas in [LBS23]. Let C = Bh be the (bounded) challenge set and H : {0, 1}∗ → C a random oracle. Sampling uniformly from R is not well defined, and the challenge must be small enough that z = y + cs1 ∈ S l . Theorem 1 ([Lyu09], Theorem 2). Let n be an integer which is a power of 2. If the above signature scheme is not strongly unforgeable, then there is a polynomial-time algorithm that can solve SVPε (Λ), for ε = Õ(n2 ) and for every lattice Λ corresponding to an ideal in the ring Z[x]/(xn + 1).

Ramses Fernandez

11

Algorithm 8 Fiat–Shamir with aborts signature 1: procedure KeyGen(1κ ) 2: A ← Rqk×l , s1 ← S l , s2 ← S k 3: t = As1 + s2 4: return pk = (A, t), sk = (s1 , s2 ) 5: end procedure 6: procedure Sign(µ, sk, t) 7: repeat y ← S l , w = HB(Ay), c = H(µ, w), z = y + cs1 8: until z ∈ S l and the recoverability bound holds 9: return σ = (z, c) 10: end procedure 11: procedure Verify(µ, σ, pk) 12: w′ = HB(Az − ct) 13: if (z ∈ S l ) ∧ (c = H(µ, w′ )) then return 1 14: end if 15: end procedure Algorithm 9 KeyGen(pp) 1: parse A from pp 2: s1 ← S l , s2 ← S k 3: t = As1 + s2 4: (ek, dk) ← KGene (1κ ) 5: return pk = (A, t, ek), sk = (pk, s1 , s2 , dk) Algorithm 10 WSignpub (µ, sks , π) 1: π = {pks , pkv } 2: repeat ▷ simulate verifier branch from the accepted distribution $ $ 3: cv ← − C; zv ← − S l ; wv = HB(Azv − cv tv ) 4: until the low-order recoverability test on Azv − cv tv holds 5: repeat $ 6: y← − S l ; ws = HB(Ay)
7: g = HM (µ, ws , wv , π); cs = ι (g − ι−1 (cv )) mod M 8: zs = y + cs s1 ▷ sks = (pks , s1 , s2 , dks ) 9: until zs ∈ S l and the recoverability bound holds 10: return σ = (cs , cv , zs , zv ) Algorithm 11 WSVerifypub (µ, π, σ) 1: σ = (cs , cv , zs , zv ) 2: ws′ = HB(Azs − cs ts ); wv′ = HB(Azv − cv tv ) 3: g = HM (µ, ws′ , wv′ , π) 4: if (ι−1 (cs ) + ι−1 (cv ) ≡ g (mod M )) ∧ (zs , zv ∈ S l ) then return 1 5: end if Algorithm 12 Confirmpub (µ, sks , π, σ) 1: return σ̃ ← Signsks (µ ∥ π ∥ σ) Algorithm 13 CVerifypub (µ, π, σ, σ̃) 1: if WSVerify 2: end if

pub

(µ, π, σ) = 1 ∧ Verifypks (µ ∥ π ∥ σ, σ̃) = 1 then return 1

12

Withdrawable FS

Taking the above scheme as starting point, we define a withdrawable lattice-based scheme as follows: The proofs for Theorem 2 and Theorem 3 below closely follow the structure of their analogous Theorems 12 and 13 in [LBS23]. The fundamental arguments remain valid when adapting the security assumptions to our context, with the primary distinction being the underlying signature scheme. Assumption 1 (Commitment min-entropy). The commitment pair (ws , wv ) produced by an accepted run of WSign has min-entropy at least α; for the concrete Dilithium parameter sets α ≥ 1024 (and α ≥ 1397 at level 2), so 2−α ≤ 2−1024 . Remark 1 (Heuristic support for Assumption 1). Let ws [1] = a1·y be one output coordinate (a1 ∈ Rql the first row of A). The input min-entropy H∞ (y) = l n log2 (2γ1 ) exceeds log2 |Rq | = n log2 q by ≥ 12544 (level 2), 19712 (level 3), 29952 (level 5) bits, so under the module regularity of the SIS map (a1 , a1 ·y) is statistically close to (a1 , U(Rq )), and HighBits(ws [1], 2γ2 ) has min-entropy ≈ n log2 ((q − 1)/2γ2 ) ≥ 1024. Conditioning on the constant-probability rejection event lowers this by O(1) bits. A fully rigorous bound needs a regularity lemma over Rq with exact conditions for a completely split q and the rejection-conditioned law of y; we therefore record the value as Assumption 1. Lemma 1 (Witness-free simulatability / naHVZK). There is a PPT algorithm Sim(µ, π), taking no secret key and fixing HM at a single point, such that for all honestly generated π = {pks , pkv } and all µ, the output of Sim(µ, π) together with its induced HM -entry is within statistical distance εzk of a genuine pair (WSign(µ, sks , π), HM -entry), conditioned $

on the programmed point being fresh. Concretely Sim repeatedly samples cs , cv ← − C and $ l zs , zv ← − Sγ1 −β−1 until both ∥LowBits(Azs − cs ts , 2γ2 )∥∞ < γ2 − β and ∥LowBits(Azv − cv tv , 2γ2 )∥∞ < γ2 −β (the same low-order test as WSign); it then sets ws = HighBits(Azs − cs ts , 2γ2 ), wv = HighBits(Azv − cv tv , 2γ2 ), programs HM (µ, ws , wv , π) := (ι−1 (cs ) + ι−1 (cv )) mod M , and returns (cs , cv , zs , zv ). Proof. The verifier branch is produced by exactly this simulation already in WSign, so it is identical in both distributions. The signer branch is one FS-with-aborts transcript; by the non-abort honest-verifier zero-knowledge of the base scheme its accepted output (cs , zs ) $

is within statistical distance εzk of (cs ← − C, zs short, ws = HighBits(Azs − cs ts , 2γ2 )). Finally the law of (cs , cv , g) agrees: in the real scheme cv and g = HM (· · · ) are uniform and independent and cs = ι((g − ι−1 (cv )) mod M ); in Sim both cs , cv are uniform and g is set to ι−1 (cs ) + ι−1 (cv ). Both yield (cs , cv ) ∼ U(C)2 with g determined by the constraint. Theorem 2. If the underlying signature scheme Sign is EUF-CMA secure, then the publicly-verifiable core of Algorithms 9–13 is unforgeable under insider corruption in the (Q)ROM (the full designated scheme of Section 3.3 inherits this via Proposition 1). For any adversary A making qW signing, qC confirmation and qHM random-oracle queries, there is an adversary B such that, in the random-oracle model, AdvEUF-CMA-ic (A) ≤ AdvEUF-CMA (B) + qW εzk + WS Sign

qW (qHM + qW ) , 2α

where εzk is the per-proof simulation error of Lemma 1 and α the commitment min-entropy (Assumption 1). The last term is the random-oracle programming loss; in the quantum random-oracle model it is replaced by the adaptive-reprogramming term of Remark 3. The reduction incurs no multiplicative qH factor. Remark 2. Algorithms 9–13 form the publicly-verifiable core: Theorem 3 establishes its origin ambiguity and Theorem 2 the unforgeability of its confirmation. The designated

Ramses Fernandez

13

withdrawable signature of Definition 1 is the strong designated-verifier scheme of Section 3.3, which wraps this core and inherits both properties (Proposition 1). Proof. We use a short sequence of games; Pr[Gi ] is the probability that game Gi outputs 1. Throughout, HM (the OR-proof challenge oracle) is domain-separated from the random oracle of the underlying scheme DS of Definition 5; recall Confirm(µ, sks , π, σ) = Signsks (µ∥π∥σ) and CVerify(µ, π, σ, σ̃) = 1 iff WSVerifypub (µ, π, σ) = 1 and Verifypks (µ∥π∥σ, σ̃) = 1, with ⟨·⟩ an injective encoding. Game G0 . The experiment ExpEUF-CMA-ic (1κ ) of Definition 3 (Algorithm 4). Thus W S,A EUF-CMA-ic Pr[G0 ] = AdvW S (A). Game G1 . As G0 , but OWSign is answered by Sim(µ, π) of Lemma 1, programming the one induced HM -entry; if that entry is already defined the game raises bad and aborts. By a hybrid over the qW signing queries, each replacement changes A’s view by at most εzk (Lemma 1) unless the programmed point (µ, ws , wv , π) already occurs in the HM -table; at that moment the table has at most qHM + qW entries and, by Definition 1, (ws , wv ) is unpredictable with min-entropy ≥ α, so a collision occurs with probability at most (qHM + qW )/2α . Hence Pr[G0 ] − Pr[G1 ] ≤ qW εzk +

qW (qHM + qW ) . 2α

In G1 the signer key sks is used only inside OConfirm , via Signsks (⟨µ, π, σ⟩): OCorrupt never returns sks ; OWSign now runs Sim (no secret key); the oracles H, HM are key-independent; and the keys of parties i ̸= s are independent of sks . We build B against the EUF-CMA-security of DS (Definition 5). B gets a challenge key pk ∗ , a signing oracle Signsk∗ (·) and access to DS’s random oracle H. It generates a fresh encryption key pair (eks , dks ) ← KGene (1κ ) itself and sets pks := (pk ∗ , eks ), so that Verifypks parses and uses only the signing component pk ∗ while eks enters π exactly as in an honest key; it never uses dks . It runs (pki , ski ) ← KeyGen(pp) for all i = ̸ s (so it holds skv ), sets π := {pks , pkv }, and runs A, answering: OCorrupt (i) by ⊥ if i = s and by ski otherwise (in particular it can deliver skv ); HM by lazy sampling consistent with programming; H by relaying to its own oracle (it never programs H); OWSign (µ) by Sim(µ, π) (aborting on bad); and OConfirm (µ, σ), for (µ, σ) ∈ W , by setting M ← M ∪ {µ} and returning σ̃ ← Signsk∗ (⟨µ, π, σ⟩). This is a perfect emulation of G1 . When A outputs (µ∗ , σ ∗ , σ̃ ∗ ), B outputs (⟨µ∗ , π, σ ∗ ⟩, σ̃ ∗ ). If A wins G1 then CVerify(µ∗ , π, σ ∗ , σ̃ ∗ ) = 1, hence Verifypk∗ (⟨µ∗ , π, σ ∗ ⟩, σ̃ ∗ ) = 1. The only messages B sent to its signing oracle are ⟨µj , π, σj ⟩ for the confirmation queries j, each of which placed µj into M . Since µ∗ ∈ / M , we have µ∗ ̸= µj for all j, so by injectivity of ⟨·⟩ ∗ ∗ the forgery message ⟨µ , π, σ ⟩ is new. Thus B wins, giving Pr[G1 ] ≤ AdvEUF-CMA (B); B DS makes at most qC signing queries. Combining, AdvEUF-CMA-ic (A) ≤ AdvEUF-CMA (B) + qW εzk + WS DS

qW (qHM + qW ) . 2α

The reduction never rewinds A and never extracts from the OR-proof (only its simulatability is used), so there is no multiplicative qH loss. Insider corruption is captured: B holds skv and may hand it to A, yet confirmation still needs sks = sk ∗ , which B never knows. Remark 3 (QROM). In the QROM the only changes are: (i) the simulation of OWSign programs HM at an adaptively chosen, high-min-entropy point under superposition queries,

14

Withdrawable FS

which is handled by the adaptive reprogramming lemma of Grilo–Hövelmanns–Hülsing– p Majenz [GHHM21], turning the term qW (qHM + qW )/2α into 32 qW (qHM + qW + 1)/2α ; and (ii) Definition 5 is taken in the QROM, which for Dilithium follows from SelfTargetMSIS and MSIS [DLL+ 18; KLS18]. The reduction B is unchanged, as it relays H to the (quantum) DS challenger and never programs it. Theorem 3. The scheme of Algorithms 9–13 is withdrawable. For any computationally unbounded adversary A making at most qW signing and qHM random-oracle queries,   AdvWithdraw (A) := Pr ExpWithdraw (1κ ) = 1 ≤ WS W S,A

(qW +1)(qHM +qW +1) 1 , 2 + (qW +1) εzk + 2α

where qW is the number of signing-oracle queries, qHM the number of queries to HM , and εzk , α are as in Lemma 1 and Definition 1. The bound is statistical, so it holds against computationally unbounded adversaries making at most qHM random-oracle queries (assuming both key pairs are generated honestly by the experiment, as in Definition 4). If instead pkv may be chosen by A, the bound gains an additive AdvMLWE term (Definition 8), see Remark 5. Proof. We bound Pr[ExpWithdraw (1κ ) = 1] of Definition 4 (Algorithm 6). The experiment W S,A $

generates both key pairs honestly, sets π = {pk0 , pk1 }, draws b ← − {0, 1}, and gives A the WSign challenge σb = WSign(µ∗ , skb , π) together with the signing oracle Osk of Algorithm 5; b ,π ′ ′ finally A outputs a guess b and wins iff b = b. Let Sim(µ, π) be the witness-free simulator of Lemma 1; crucially Sim depends only on the set π (it simulates both branches), not on which party is the prover. The whole view of A consists of N := qW + 1 withdrawable signatures, all produced under the witness skb (the challenge and the qW oracle replies), plus A’s qHM queries to HM . Game S (witness-free). Modify the experiment so that each of these N signatures is produced by Sim(·, π), programming the single induced HM -entry (and aborting on a clash). Since Sim uses neither sk0 nor sk1 , the entire experiment S – and hence the joint ′ distribution of A’s view and output b′ – is independent
1of b. Writing pS := Pr[b = 1 | S], 1 ′ independence gives Pr[b = b | S] = 2 (1 − pS ) + pS = 2 . For b ∈ {0, 1} let Gb be the real experiment conditioned on that bit, and pb := Pr[b′ = 1 | Gb ]. We pass from Gb to S by replacing the N signatures one at a time. Each step turns one WSign(·, skb , π) into one Sim(·, π); by Lemma 1, applied with party b as the real prover (valid because pkb is honest, so skb is a genuine witness), the two are within statistical distance εzk , provided the programmed point (µ, ws , wv , π) is fresh. By Definition 1 the commitment pair has min-entropy ≥ α, so at any step the freshness fails with probability at most (qHM + N )/2α (the HM -table holds at most qHM + N points). Summing over the N hybrids, N (qHM + N ) pb − pS ≤ δ := N εzk + , b ∈ {0, 1}. 2α Using Pr[b′ = 0 | G0 ] = 1 − p0 ,
Pr[ExpWithdraw = 1] = 12 Pr[b′ = 0 | G0 ] + Pr[b′ = 1 | G1 ] = 21 + 12 (p1 − p0 ). W S,A By the triangle inequality |p1 − p0 | ≤ |p1 − pS | + |pS − p0 | ≤ 2δ, hence Pr[ExpWithdraw = 1] ≤ W S,A

(qW + 1)(qHM + qW + 1) 1 1 . 2 + δ = 2 + (qW + 1)εzk + 2α

Every step is information-theoretic, so the bound holds against computationally unbounded adversaries that make at most qHM random-oracle queries.

Ramses Fernandez

15

Remark 4 (Theorem 3 in the QROM). Theorem 3 is stated in the classical ROM. Its only use of the random oracle is the witness-free simulation of WSign, which programs HM at the adaptively chosen, high- min-entropy point (µ, ws , wv , π) (Assumption 1). In the QROM the adaptive-reprogramming lemma of Grilo–Hövelmanns–Hülsing–Majenz [GHHM21] (q +1)(qHM +qW +1) applies exactly as in Remark 3, replacing the classical freshness term W by 2α p 3 α ; the statistical, information-theoretic core of the argument (q +1) (q +q +1)/2 HM W 2 W is unchanged. For the no-hint instantiation the two real signing distributions are identical (Lemma 2), so the dkv /skv bound of Proposition 1 is exact in both models and incurs no reprogramming term. Remark 5 (Adversarial pkv ; strong-DV variant). Definition 4 generates both keys honestly, so the proof is statistical. In the stronger model where A chooses pkv , Sim still simulates for any pkv , but the two real provers require both statements to admit short witnesses; bridging an honestly generated pkv to an adversarial one costs one decisional-MLWE step (Definition 8), adding AdvMLWE to the bound. For the strong designated-verifier scheme of Section 3.3, the same hybrid first replaces every signature by a simulated one and then replaces the two ciphertexts and the one-time pad by uniform strings; this yields (q +1)(qHM +qW +1) prg
Pr[ExpWithdraw = 1] ≤ 12 + (qW +1)εzk + qW 2 Advpr + W , i.e. PKE + AdvG 2α withdrawability against third parties as in Proposition 1, now made quantitative; nontransferability against the designated verifier is exactly the statistical statement proved above.

3.2

An instantiation

The general construction of Section 3.1 for a withdrawable digital signature scheme whose underlying scheme is built using the Fiat–Shamir with aborts paradigm was proven to be unforgeable under insider corruption and withdrawable. As a direct application of this proposal, in this section we present a withdrawable signature scheme based on a no-hint, full-t Dilithium-style Fiat–Shamir-with-aborts signature [DLL+ 18]; adapting to production ML-DSA (with hints, and a nonzero εzk ) is discussed after Corollary 1. The verification algorithm below is public; it serves as a building block (WSVerifypub ) that Section 3.3 encrypts to the designated verifier to obtain the strong designated-verifier withdrawable signature of Definition 1. Taking the above algorithm as starting point and following the general construction in Section 3.1, it is straightforward to set a withdrawable digital signature based on Dilithium. Since Dilithium relies on the hardness of MSIS, Theorem 2 applies to prove that the proposal below is unforgeable under insider corruption. Theorem 3 then proves withdrawability of the honest-key public core statistically, under Assumption 1 and perfect naHVZK; the hardness of the decisional MLWE problem is used only for adversarially chosen verifier keys (Remark 5) and for the privacy of the encryption layer in Section 3.3. Below follows the withdrawable signature based on Dilithium: Throughout, the signer instance of a key pair is written sks = (pks , s′1 , s′2 , dks ) with pks = (A, ts , eks ), and the verifier instance skv = (pkv , s′′1 , s′′2 , dkv ); the primes are the per-party renaming of the generic (s1 , s2 ) output by KeyGen(pp). Remark 6. WSignpub is invoked by either party: the caller runs its own branch for real (with the rejection loop) and simulates the other from the accepted distribution above. A verifier signs by swapping the roles of s and v. Because both branches are now drawn from the accepted low-order distribution, the two invocations produce identically distributed σ (Lemma 2, εzk = 0), and the public predicates ∥LowBits(Azs − cs ts , 2γ2 )∥∞ < γ2 − β and

16

Withdrawable FS

Algorithm 14 Dilithium signature [DLL+ 18] 1: procedure KeyGen(1κ ) $

$

A← − Rqk×l , (s1 , s2 ) ← − Sηl × Sηk t = As1 + s2 4: return (pk = (A, t), sk = (A, t, s1 , s2 )) 5: end procedure 6: procedure Sign(µ, sk) 7: repeat $ 8: y← − Sγl 1 −1 9: w = HighBits(Ay, 2γ2 ) 10: c ∈ C = H(µ, w) 11: z = y + cs1 12: until (∥z∥∞ < γ1 − β) ∧ (∥LowBits(Ay − cs2 , 2γ2 )∥∞ < γ2 − β) 13: return σ = (z, c) 14: end procedure 15: procedure Verify(µ, pk, σ) 16: w′ = HighBits(Az − ct, 2γ2 ) 17: if ∥z∥∞ < γ1 − β and c = H(µ, w′ ) then return 1 18: end if 19: end procedure 2: 3:

Algorithm 15 KeyGen(pp) 1: parse A from pp $ 2: (s1 , s2 ) ← − Sηl × Sηk 3: t = As1 + s2 4: (ek, dk) ← KGene (1κ ) 5: return pk = (A, t, ek), sk = (pk, s1 , s2 , dk)

Algorithm 16 WSignpub (µ, sks , π) 1: π = (pks , pkv ) 2: repeat ▷ simulate verifier branch from the accepted distribution $ $ 3: cv ← − C; zv ← − Sγl 1 −β−1 ; wv = HighBits(Azv − cv tv , 2γ2 ) 4: until ∥LowBits(Azv − cv tv , 2γ2 )∥∞ < γ2 − β 5: repeat $ 6: y← − Sγl 1 −1 ; ws = HighBits(Ay, 2γ2 )
7: g = HM (µ, ws , wv , π); cs = ι (g − ι−1 (cv )) mod M 8: zs = y + cs s′1 9: until (∥zs ∥∞ < γ1 − β) ∧ (∥LowBits(Ay − cs s′2 , 2γ2 )∥∞ < γ2 − β) 10: return σ = (cs , cv , zs , zv )

Ramses Fernandez

17

∥LowBits(Azv − cv tv , 2γ2 )∥∞ < γ2 − β hold simultaneously, revealing nothing about the origin. Algorithm 17 WSVerifypub (µ, π, σ) 1: σ = (cs , cv , zs , zv ) 2: ws′ = HighBits(Azs − cs ts , 2γ2 ); wv′ = HighBits(Azv − cv tv , 2γ2 ) 3: g = HM (µ, ws′ , wv′ , π) 4: if (ι−1 (cs ) + ι−1 (cv ) ≡ g (mod M )) ∧ (∥zs ∥∞ < γ1 − β) ∧ (∥zv ∥∞ < γ1 − β) then return 1 5: end if Algorithm 18 Confirmpub (µ, sks , π, σ) 1: return σ̃ ← Signsks (µ ∥ π ∥ σ)

▷ ordinary Dilithium signature, Alg. 14

Algorithm 19 CVerifypub (µ, π, σ, σ̃) 1: σ = (cs , cv , zs , zv ) pub 2: if WSVerify (µ, π, σ) = 1 ∧ Verifypks (µ ∥ π ∥ σ, σ̃) = 1 then return 1 3: end if Remark 7 (Correctness). For the real branch, the rejection condition ∥LowBits(Ay − cs s′2 , 2γ2 )∥∞ < γ2 − β yields HighBits(Azs − cs ts , 2γ2 ) = HighBits(Ay, 2γ2 ) = ws ; the simulated branch matches by construction; and ι−1 (cs ) + ι−1 (cv ) ≡ g by definition of cs . Hence WSVerify accepts honest signatures, and CVerify accepts by correctness of Sign. The quantity r of the original construction is no longer used, so the former r = r′ identity is unnecessary. Instantiation of εzk and α. Our scheme uses the no-hint identification scheme: verification recomputes w′ = HighBits(Az − ct, 2γ2 ) from the full t (no t0 /t1 split, no hint). For this scheme the simulator of Lemma 1 is perfect. Lemma 2 (Perfect naHVZK). Conditioned on the programmed HM -point being fresh, the simulator Sim(µ, π) of Lemma 1 produces a transcript identically distributed to a genuine WSign(µ, sks , π); that is, εzk = 0. Proof. Fix the challenge c (uniform in the real game as HM is a random oracle, and uniform in the simulation by programming a fresh point). In WSign, y is uniform over Sγl 1 −1 and z = y + cs′1 ; conditioned on ∥z∥∞ < γ1 − β, z is uniform over Sγl 1 −β−1 , because each target z in that box has a unique in-range preimage y = z − cs′1 (as ∥cs′1 ∥∞ ≤ β). The further test ∥LowBits(Ay − cs′2 , 2γ2 )∥∞ < γ2 − β equals ∥LowBits(Az − cts , 2γ2 )∥∞ < γ2 − β (since Az − cts = Ay − cs′2 ), a function of (c, z) and the public ts only; and the recomputed commitment is HighBits(Az − cts , 2γ2 ) = ws . The corrected simulator (Lemma 1) draws z uniformly over Sγl 1 −β−1 with the identical low-order test and sets ws = HighBits(Az − cts , 2γ2 ). Hence the conditional law of (c, z, ws ) is identical in both, and the verifier branch is produced by the same simulation on both sides. The transcripts therefore coincide. Corollary 1 (Concrete security). Instantiated with no-hint Dilithium, the scheme has εzk = 0 (Lemma 2) and α ≥ 1024 (Assumption 1). Hence, for any adversary making qW

18

Withdrawable FS

Table 1: Parameters (n = 256, q = 8380417) and the resulting commitment min-entropy lower bound α (bits). Challenge entropies log2 |Bτ | = 192.8, 225.3, 257.0. (k, l) Dilithium2 / ML-DSA-44 Dilithium3 / ML-DSA-65 Dilithium5 / ML-DSA-87

(4, 4) (6, 5) (8, 7)

η, τ, β 2, 39, 78 4, 49, 196 2, 60, 120

γ1 , γ2 17

2 , 95232 219 , 261888 219 , 261888

q−1 2γ2

α (≥)

44 16 16

1397 1024 1024

signing and qHM random-oracle queries, Theorems 2 and 3 give AdvEUF-CMA-ic (A) ≤ AdvEUF-CMA (B) + qW (qHM + qW ) 2−1024 , WS DS AdvWithdraw (A) ≤ 12 + (qW +1)(qHM +qW +1) 2−1024 . WS Unforgeability reduces to the EUF-CMA security of the underlying no-hint Dilithium-style signature (up to the 2−1024 programming term), whereas withdrawability follows statistically from perfect naHVZK (εzk = 0) and Assumption 1, up to the same 2−1024 programming term; it does not reduce to EUF-CMA. Remark 8 (Hint-optimised Dilithium). Production Dilithium publishes t1 (not t) plus a hint h, which trades the exact recovery HighBits(Az − ct) = ws for UseHint. That variant has a small, standard naHVZK defect in place of εzk = 0 and slightly smaller signatures; our no-hint choice keeps the proofs clean (perfect naHVZK) at a modest size cost. Either way the asymptotic and concrete security are governed by the same AdvEUF-CMA and 2−α DS terms.

3.3

Strong designated-verifier variant

The scheme of Sections 3.1 and 3.2 is publicly verifiable. To match the Liu–Baek–Susilo model [LBS23], where a withdrawable signature is verifiable only by the designated verifier, we upgrade it to a strong designated-verifier (SDVS) scheme: we hybrid-encrypt the publicly-verifiable signature to the verifier (and to the signer, so that Confirm stays stateless). Write (WSignpub , WSVerifypub , Confirmpub , CVerifypub ) for the scheme of Section 3.2 (Algorithms 16–19), where WSVerifypub (µ, π, ρ) is public; KeyGen is as amended (each party holds (ek, dk)). Let ρ denote a public ring signature and ∥ρ∥ its bit length. Algorithm 20 WSign(µ, sks , π) (strong DVS) 1: ρ ← WSign

pub

$

κ

(µ, sks , π)

2: K ← − {0, 1} 3: cts ← Enc(eks , K); ctv ← Enc(ekv , K) 4: C ← ρ ⊕ G(K) 5: return σ = (cts , ctv , C)

▷ public OR-proof ring signature

▷ G(K) truncated to ∥ρ∥ bits

Algorithm 21 WSVerify(µ, skv , pks , σ) (strong DVS; designated) 1: parse pkv from skv ; π = {pks , pkv }; parse σ = (cts , ctv , C) 2: K ← Dec(dkv , ctv ); ρ ← C ⊕ G(K) pub 3: return WSVerify (µ, π, ρ) Remark 9 (Scope of confirmed verification). CVerify certifies that the signer authenticated the outer object σ (via σ̄ = Signsks (µ∥π∥σ)) and that the revealed pad opens C to a public core ρ that passes WSVerifypub . It does not publicly certify ciphertext consistency, i.e. that

Ramses Fernandez

19

Algorithm 22 Confirm(µ, sks , π, σ) (strong DVS) 1: parse σ = (cts , ctv , C) 2: K ← Dec(dks , cts ); ρ ← C ⊕ G(K) 3: σ̄ ← Signsks (µ ∥ π ∥ σ) 4: return σ̃ = (σ̄, ρ, K)

▷ signer recovers ρ via its own dks

Algorithm 23 CVerify(µ, π, σ, σ̃) (strong DVS; public) 1: parse σ = (cts , ctv ,
C), σ̃ = (σ̄, ρ, K)

pub 2: if C = ρ ⊕ G(K) ∧ WSVerify (µ, π, ρ) = 1 ∧ Verifypks (µ ∥ π ∥ σ, σ̄) = 1 then return 1 3: end if cts and ctv encrypt the same K: for randomised PKE this cannot be checked without opening the encryption randomness. Confirmation is therefore a signer-authenticated opening of σ to a valid ambiguous core, which is all correctness (Definition 2) and unforgeability (Theorem 2) require; it does not retroactively attest that the designated verifier could decrypt σ prior to confirmation. For honestly generated σ the two ciphertexts do share K, so WSVerify = 1 ⇒ CVerify = 1 as stated. Proposition 1 (SDVS variant). Assume PKE has ciphertext pseudorandomness (advantage Advpr PKE ) and G is a secure PRG. Then Algorithms 20–23 form a correct withdrawable signature (Definitions 1–4) with designated verification, and: • (Designated verification / privacy.) Without dks or dkv , σ is pseudorandom; in particular third parties cannot publicly verify σ; recovering ρ (and hence verifying) requires a decryption key, so both the designated verifier (via dkv ) and the signer (via dks ) can verify. • (Withdrawability.) For any PPT third-party adversary making qW signing and qHM random-oracle queries, AdvWithdraw := Pr[ExpWithdraw = 1] ≤ 12 +(qW +1) 2 Advpr W S,A PKE +
prg pr AdvG , where AdvPKE is the ciphertext-pseudorandomness advantage of PKE. Against an adversary holding the full verifier secret key skv = (pkv , s′′1 , s′′2 , dkv ) the bound is 1 2 + (qW +1) εzk : by the perfect naHVZK of Lemma 2 the verifier branch is identically distributed whether produced for real or simulated, so the witness confers no distinguishing power. This equals exactly 21 for the no-hint Dilithium instantiation. • (Unforgeability under insider corruption.) Reduces to the EUF-CMA security of Sign exactly as in Theorem 2; the reduction chooses K and the ciphertexts itself, hence needs no secret key. Proof. The strong-DV algorithms (Algorithms 20–23) are built on the public core (WSignpub , WSVerifypub , Confirmpub , CVerifypub ) of Section 3.2, a public-key encryption scheme PKE = (KGene , Enc, Dec) with decryptionfailure probability δPKE and ciphertext-pseudorandomness advantage Advpr PKE (i.e. for any message m, Enc(ek, m) is indistinguishable from a uniform ciphertext given ek but not dk; this implies IND-CPA and key-privacy), and a PRG G with advantage Advprg G . Recall σ = (cts , ctv , C), cts = Enc(eks , K), ctv = Enc(ekv , K), C = ρ ⊕ G(K), ρ = WSignpub (µ, sks , π), $

K← − {0, 1}κ . The verifier recovers K = Dec(dkv , ctv ) and ρ = C ⊕ G(K), so WSVerify = WSVerifypub (µ, π, ρ) = 1

20

Withdrawable FS

by correctness of the core. Confirm recovers the same (ρ, K) via dks and outputs σ̃ = (σ̄, ρ, K), σ̄ = Signsks (µ∥π∥σ); then CVerify makes the following verifications: C = ρ⊕G(K) (true), WSVerifypub (µ, π, ρ) = 1, and Verifypks (µ∥π∥σ, σ̄) = 1, all of which hold. The error is at most 2δPKE plus the negligible correctness errors of the core and of Sign. We show σ is pseudorandom to any party lacking both dks , dkv . Hybrids: H0 = real σ; H1 replaces cts by a uniform string; H2 also replaces ctv by a uniform string; H3 also replaces G(K) by a uniform string R. Each PKE step costs ≤ Advpr PKE (the reduction picks K, embeds the challenge as cts resp. ctv , and computes the rest from the known K; no decryption key is used); the PRG step costs ≤ Advprg G (in H2 , K feeds only G). In H3 , C = prg ρ ⊕ R is uniform and independent of ρ, so σ is uniform. Hence ∆(σ, U) ≤ 2Advpr PKE + AdvG . Consequently no public procedure can decide validity of σ (it would distinguish H0 from H3 ); verification requires a decryption key, so the designated verifier (via dkv ) and the signer (via dks ) can verify, while third parties cannot. In Definition 4 the adversary A holds no secret keys and sees N := qW + 1 signatures (challenge and oracle replies) under the bit b. Applying the previous hybrid to each, every prg signature is within 2Advpr PKE + AdvG of uniform independently of b (a uniform σ reveals neither ρ nor which keys were used). Thus each of the two conditional views is within prg N (2Advpr PKE + AdvG ) of the same b-independent all-uniform view, whence prg
Pr[ExpWithdraw = 1] ≤ 12 + (qW +1) 2Advpr W S,A PKE + AdvG . If A holds the full verifier secret key skv = (pkv , s′′1 , s′′2 , dkv ) (in particular its dkv ), it decrypts and recovers ρ = WSignpub (µ, skb , π); the ciphertexts and C are then determined by (ρ, K) and carry no further information about b. Here we do not route through the simulator/programming hybrid of Theorem 3; instead we compare the two real public-core distributions WSignpub (·, sk0 , π) and WSignpub (·, sk1 , π) directly. In each, one branch is produced for real and the other is drawn from the accepted low-order distribution, and in both cases the challenge g = HM (µ, ws , wv , π) is read from the honest random oracle. By the per-branch naHVZK of Lemma 1, a real accepted branch and a simulated accepted branch are within statistical distance εzk as distributions, with no oracle reprogramming; hence the two real signing distributions are within 2εzk per signature, and no 2−α freshness term is incurred. Summing over the N = qW +1 signatures, Pr[ExpWithdraw = 1] ≤ 1 2 + (qW +1)εzk . For the no-hint Dilithium instantiation εzk = 0 (Lemma 2), so the two real distributions are identical and the excess advantage Pr[ExpWithdraw = 1] − 21 is exactly 0: even the designated verifier cannot tell whether it or the signer produced σ. The reduction is that of Theorem 2, with the reduction performing the encryption itself. B receives the Sign-challenge key pk ∗ , sets pks := pk ∗ , B receives the Signchallenge key pk ∗ (the signing component only). It generates a fresh encryption key pair (eks , dks ) ← KGene (1κ ) itself and sets pks := (pk ∗ , eks ), keeping dks private; it never uses dks (confirmation replies are served from stored (ρ, K), and signing queries encrypt under the public eks ). It generates all other keys honestly (so it holds skv and may give it to A). It answers: OWSign (µ) by simulating ρ with the witness-free simulator of Lemma 1 (programming HM ), drawing K, setting cts = Enc(eks , K), ctv = Enc(ekv , K), C = ρ ⊕ G(K), storing (σ, ρ, K) in W , and returning σ; and OConfirm (µ, σ), for σ ∈ W , by retrieving the stored (ρ, K) and returning (Signsk∗ (µ∥π∥σ), ρ, K) through the signing oracle. Thus B uses neither sks nor any decryption key. A confirmed forgery (µ∗ , σ ∗ , σ̃ ∗ = (σ̄ ∗ , ρ∗ , K ∗ )) with µ∗ never confirmed satisfies Verifypk∗ (µ∗ ∥π∥σ ∗ , σ̄ ∗ ) = 1 on the fresh message µ∗ ∥π∥σ ∗ , which B outputs. As in Theorem 2, AdvEUF-CMA-ic (A) ≤ AdvEUF-CMA (B) + qW εzk + qW (qHM + qW )/2α , WS DS with no contribution from PKE or G (which B evaluates honestly).

Ramses Fernandez

21

Table 2: Comparison of the Liu–Baek–Susilo withdrawable signature with the lattice construction of this work. Every difference follows from the absence of a free Diffie– Hellman-style shared secret in the lattice setting (Section 3.4). Aspect

Liu–Baek–Susilo [LBS23]

This work

Reason

Designation of σ

skv enters the verification exponent (Diffie–Hellman / pairing) algebraic symmetry of σ

encrypt σ to pkv via a PKE

no free shared secret no DH symmetry

re-derive shared randomness r; rebuild a linked σ̃ one key pair (signing = designation) DDH (Schnorr) / DBDH (BLS) CDH / DL

two-party FS-with-aborts ORproof (witness-indist.) ordinary signature Signsks (µ ∥ π ∥ σ) signing key pair + encryption key pair (ek, dk) decisional MLWE (PKE) + statistical WI MSIS / SelfTargetMSIS

monolithic designated-verifier object

public ambiguous core + encryption layer

composition forced

Signer/verifier ambiguity Confirmation Key material Withdrawability from Unforgeability from Overall structure

3.4

FS randomness not reusable signing key cannot designate lattice counterpart lattice counterpart

Comparison with Liu–Baek–Susilo

Our construction realises the same primitive and the same security model as Liu, Baek and Susilo [LBS23]: the syntax of Definition 1 and the security notions of Definitions 2, 3 and 4 are theirs, and we follow their two-stage “withdraw, then confirm” template. The differences are confined to the construction, and each of them follows from a single structural fact about lattices. Root cause: the group shared secret has no cheap lattice analogue. The designation mechanism of [LBS23] is, at its core, a Diffie–Hellman (or pairing) shared secret embedded in the signature. In their Schnorr-based scheme the withdrawable signature contains σ2 = pkvz−rt , which the designated verifier checks by raising to its secret key skv via (g a )b = (g b )a ; the BLS-based scheme uses e(·, g skv ) in the same way. A single algebraic object thereby delivers both properties required of a withdrawable signature at once: signer/verifier ambiguity — either party can compute σ from its own secret — and designation — verification requires skv — using nothing but the parties’ ordinary public keys, in effect a non-interactive key agreement (NIKE). This shared secret is essentially free in a group but has no cheap lattice counterpart: the noisy analogue of (g a )b ≈ (g b )a agrees only approximately, so a literal transcription that blinds the signature by a uniform matrix B ∈ Rqk×k leaves a residue Bs′′2 that the verifier cannot cancel (it is given BA, never B). Lattice NIKE is in fact possible: after a long line of negative evidence, including information-theoretic efficiency barriers for polynomial-modulus reconciliation [GKRS22], the recent SWOOSH scheme [GdKQ+ 24] gives the first practical M-LWE NIKE — but at a cost (public keys of hundreds of kilobytes, a super-polynomial modulus-to-noise ratio, and a NIZK for active security) well above what designation needs. Crucially, designation does not require a shared secret at all: it only needs to deliver a key to the designated verifier, which is public-key encryption — a weaker and far cheaper primitive. We therefore keep ambiguity and designation as separate mechanisms, an OR-proof for the former and encryption for the latter; this is the origin of every row of Table 2. Ambiguity and confirmation. For ambiguity we use a two-clause Fiat–Shamir-withaborts OR-proof (Algorithm 16): a proof of knowledge of a short witness for ts or for tv ,

22

Withdrawable FS

which either party can produce by executing its own branch and simulating the other. This is the natural lattice substitute for the group symmetry, and it agrees with the authors’ own description of withdrawable signatures as two-party ring signatures augmented with a transformation stage [LBS23]. For confirmation, where [LBS23] reconstructs the shared randomness r and rebuilds an algebraically linked σ̃, we let Confirm emit an ordinary signature Signsks (µ ∥ π ∥ σ) on the entire withdrawable object: the masking randomness of Fiat–Shamir with aborts is not reusable in the way a discrete-logarithm nonce is, and binding by a signature is both simpler and reducible to the unforgeability of the underlying scheme (Theorem 2). Designation by encryption: a PKE, not a KEM. Lacking the free shared secret, we transport the designation explicitly: the scheme of Section 3.3 encrypts the publicly verifiable, ambiguous signature ρ to the verifier, so that only a holder of dkv can recover and check it. This encryption must place the same chosen key K under two public keys: ekv , so that the verifier can decrypt and verify, and eks , so that the signer can decrypt and run Confirm statelessly (it is given only σ). A key-encapsulation mechanism returns a fresh random key for each encapsulation and recipient, so Encaps(ekv ) and Encaps(eks ) would produce two independent keys and the parties could never reconstruct the same ρ = C ⊕ G(K); delivering one shared chosen K to both recipients is exactly encryption of a chosen message, i.e. a public-key encryption scheme. We therefore instantiate PKE with the CPA-secure module-LWE encryption underlying ML-KEM (Kyber), and not with the KEM itself. This encryption is precisely what the group construction obtains for nothing: there the shared key is the Diffie–Hellman value that both parties derive from their public keys, so [LBS23] require no encryption at all, whereas we must transport it — and to both parties — which is why a public-key encryption scheme appears in our construction where theirs has none. Consequences. The two schemes rest on parallel hardness assumptions: decisional MLWE replaces DDH/DBDH for withdrawability, and MSIS/SelfTargetMSIS replace CDH/DL for unforgeability. The lattice route is less compact — an extra encryption key pair per party, and a withdrawable signature carrying two ciphertexts and a one-time pad rather than three group elements — but it gains two properties: the withdrawable signature is pseudorandom, concealing from outsiders even the existence of a signature, and non-transferability against the designated verifier is perfect (εzk = 0 for the no-hint instantiation) rather than computational. We regard these as necessary adaptations of the Liu–Baek–Susilo notion to the post-quantum setting rather than departures from it.

4

Conclusion and future research

This work uses the ideas in [LBS23] to extend the Fiat–Shamir with aborts paradigm [Lyu09] with withdrawability and defines a general construction for withdrawable latticebased digital signature schemes. We demonstrated our approach by creating a withdrawable version of Dilithium, though the same principles could be applied to other signature schemes like HAETAE [CCD+ 24]. Our construction maintains the security properties of the underlying signature scheme while adding the ability to withdraw signatures when needed by the signer. Several directions remain for future research, including optimizing our construction’s efficiency and exploring additional features such as blindness, multiparty capabilities, or enhancing this construction with extended withdrawability, where rather than limiting verification to a specific entity, we can ensure the universal verifiability of the withdrawable

Ramses Fernandez

23

signature by employing any signature scheme that can maintain signer ambiguity (this is work done in [LSB24]). Another potential line of research is given by practical applications, particularly how these constructions could enhance quantum resistance in blockchain systems. The ability to withdraw signatures could prove valuable in blockchain environments where transaction revocation is desirable but traditionally difficult to implement.

References [CCD+ 24]

Jung Hee Cheon, Hyeongmin Choe, Julien Devevey, Tim Güneysu, Dongyeon Hong, Markus Krausz, Georg Land, Marc Möller, Damien Stehlé, and MinJune Yi. Haetae: shorter lattice-based fiat-shamir signatures. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2024(3):25– 75, 2024. issn: 2569-2925. doi: 10.46586/tches.v2024.i3.25- 75. url: http://dx.doi.org/10.46586/tches.v2024.i3.25-75.

[DLL+ 18]

Léo Ducas, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehlé. Crystals–dilithium: digital signatures from module lattices. 2018.

[FS]

Amos Fiat and Adi Shamir. How to prove yourself: practical solutions to identification and signature problems. In Advances in Cryptology — CRYPTO’ 86. Springer Berlin Heidelberg, pages 186–194. isbn: 9783540180470. doi: 10.1007/3-540-47721-7_12. url: http://dx.doi.org/10.1007/3-54047721-7_12.

[GdKQ+ 24]

Phillip Gajland, Bor de Kock, Miguel Quaresma, Giulio Malavolta, and Peter Schwabe. SWOOSH: efficient Lattice-Based Non-Interactive key exchange. In 33rd USENIX Security Symposium (USENIX Security 24), pages 487–504, Philadelphia, PA. USENIX Association, 2024. isbn: 978-1-939133-44-1. url: https://www.usenix.org/conference/usenixsecurity24/presentatio n/gajland.

[GHHM21]

Alex B. Grilo, Kathrin Hövelmanns, Andreas Hülsing, and Christian Majenz. Tight adaptive reprogramming in the qrom. In Advances in Cryptology – ASIACRYPT 2021. Springer International Publishing, 2021, pages 637– 667. isbn: 9783030920623. doi: 10.1007/978- 3- 030- 92062- 3_22. url: http://dx.doi.org/10.1007/978-3-030-92062-3_22.

[GKRS22]

Siyao Guo, Pritish Kamath, Alon Rosen, and Katerina Sotiraki. Limits on the efficiency of (ring) lwe based non-interactive key exchange. Journal of Cryptology, 35(1), 2022.

[KLS18]

Eike Kiltz, Vadim Lyubashevsky, and Christian Schaffner. A concrete treatment of fiat-shamir signatures in the quantum random-oracle model. In Advances in Cryptology – EUROCRYPT 2018. Springer International Publishing, 2018, pages 552–586. isbn: 9783319783727. doi: 10.1007/978-3-31 9-78372-7_18. url: http://dx.doi.org/10.1007/978-3-319-78372-7 _18.

[LBS23]

Xin Liu, Joonsang Baek, and Willy Susilo. Withdrawable signature: how to call off a signature. In Information Security. Springer Nature Switzerland, 2023, pages 557–577. isbn: 9783031491870. doi: 10.1007/978-3-031-4918 7-0_28. url: http://dx.doi.org/10.1007/978-3-031-49187-0_28.

24

Withdrawable FS

[LSB24]

Xin Liu, Willy Susilo, and Joonsang Baek. Extended withdrawable signature. In Data Security and Privacy Protection. Springer Nature Singapore, October 2024, pages 119–140. isbn: 9789819785407. doi: 10.1007/978-981-97-854 0-7_8. url: http://dx.doi.org/10.1007/978-981-97-8540-7_8.

[Lyu09]

Vadim Lyubashevsky. Fiat-shamir with aborts: applications to lattice and factoring-based signatures. In Advances in Cryptology – ASIACRYPT 2009. Springer Berlin Heidelberg, 2009, pages 598–616. isbn: 9783642103667. doi: 10.1007/978-3-642-10366-7_35. url: http://dx.doi.org/10.1007/97 8-3-642-10366-7_35.