1 Introduction↩︎

Digital signatures bind a signer’s identity to a message and provide authenticity, integrity and non-repudiation, underpinning secure communication and, increasingly, the settlement of transactions in decentralised systems such as blockchains. A defining feature of a conventional signature is its permanence. Once a signer legitimately produces a signature on a message, that signature remains verifiable under the signer’s public key indefinitely, and the signer cannot rescind it. Permanence is usually a feature, but it is a liability in the many settings where a commitment may legitimately need to be revoked: limited-time access grants, revocable electronic agreements, service-level commitments in outsourcing systems, decentralised escrow, and privacy-preserving voting. In all of these one would like a signer to be able to withdraw a signature without disclosing its secret key and without affecting the validity of its other signatures.

Liu, Baek and Susilo introduced withdrawable signatures [1] to capture exactly this capability. A withdrawable signature is revoked by default: after issuing it the signer may simply take no further action, in which case the signature is not verifiable under the signer’s public key. If the signer later wishes to stand behind the message, it, and only it, can confirm the withdrawable signature, turning it into a publicly verifiable one that remains deterministically traceable to the original object, so that the confirmed signature cannot be detached from the withdrawable one it came from. The first construction realised withdrawability through a designated-verifier signature (DVS) [2], [3]: the withdrawable signature is verifiable only by a single, signer-chosen verifier, and the ambiguity between the signer and that designated verifier is precisely what allows the signature to be withdrawn. The price is a significant limitation, verification is restricted to one designated party, so the scheme lacks universal verifiability.

1.0.0.1 From designated verifiers to extended withdrawability.

To lift this restriction, Liu, Susilo and Baek proposed extended withdrawable signatures [4]. Their starting observation is that a DVS is a two-party object whose ambiguity is exactly that of a \(1\)-out-of-\(2\) signature, and that the notion generalises to \(N\ge 2\) potential signers: a withdrawable signature can be made verifiable under any public key in a set of potential signers \(\pi\) while keeping the true signer ambiguous among them, until confirmation. This “extended withdrawability” can be obtained from any \(1\)-out-of-\(N\) signature that provides signer ambiguity, ring signatures [5] and designated-verifier signatures being two natural instances, and yields a publicly verifiable withdrawable signature: any party holding the signature and the public-key set can check it, yet no party can tell which member of \(\pi\) signed. Liu, Susilo and Baek give a generic construction of extended withdrawable signatures from discrete-logarithm primitives, with an instantiation based on the Schnorr signature [6], and prove it correct, unforgeable under insider corruption, and extended-withdrawable.

1.0.0.2 The post-quantum gap.

The discrete-logarithm foundation of [4], and of the Schnorr and BLS [7] building blocks it relies on, is broken by Shor’s quantum algorithm [8]. Because withdrawable signatures are meant to protect long-lived commitments in decentralised systems, a construction that fails against a quantum adversary is of limited durable value, and a post-quantum realisation is called for. The natural route is Lyubashevsky’s Fiat-Shamir with aborts paradigm [9], which turns lattice-based identification into signatures through a controlled rejection-sampling (“abort”) step and underlies the standardised signature Dilithium (ML-DSA) [10] as well as HAETAE [11]. A first step in this direction handled the designated-verifier (two-party) withdrawable signature over the Fiat-Shamir with aborts paradigm [12]; the present work addresses the extended, publicly verifiable, \(N\)-signer notion.

1.0.0.3 Why a literal lattice transcription fails.

Porting [4] to lattices is not just a matter of replacing Schnorr by a lattice signature. The discrete-logarithm construction re-randomises each ring member’s public key by a multiplicative shift and publishes those shifts, so that the confirmed signature can later be linked back to the withdrawable one. Over a prime-order group this is safe, because the published shifts \(\{g^{s_j}\}\) are independent of the signer’s secret key and uniformly distributed, and therefore leak nothing about who signed. A literal lattice transcription, however, replaces each shift \(g^{s_j}\) by a term of the form \(A\mathbf{s}_1 s_j\) that carries the signer’s own secret \(\mathbf{s}_1\) as a common factor. Since the signer’s public key satisfies \(t_i=A\mathbf{s}_1+\mathbf{s}_2\) with \(\mathbf{s}_2\) short, the value \(A\mathbf{s}_1\) is within short distance of \(t_i\) but of no other public key; hence publishing \(\{A\mathbf{s}_1 s_j\}\) exposes \(A\mathbf{s}_1\approx t_i\) and breaks the very signer ambiguity the scheme exists to provide. This is the same structural obstruction, the lack of a free re-randomisation of a shared value in the lattice setting, encountered for the designated-verifier case [12], and it means the transformation must be redesigned rather than transcribed.

1.0.0.4 Our approach.

We keep the two objectives of an extended withdrawable signature separate and realise each by a primitive with an established security analysis, so that no signer-derived value is ever published in the clear. Ambiguity is provided by an anonymous \(1\)-out-of-\(N\) (ring) signature, used as a black box and instantiated by an established lattice one-out-of-many proof [13], [14]. Confirmation is the signer’s claim: a binding signature on the withdrawable object, together with the opening of a hiding commitment to the signer’s index that is bound into the transcript at signing time. Before confirmation the commitment hides the signer and the ring signature is anonymous; at confirmation the signer opens the commitment, and the binding signature ties the claim to the exact withdrawable object. This is precisely a claimable ring signature in the sense of Park and Sealfon [15], a primitive that Liu, Susilo and Baek themselves single out as an instantiation of withdrawable signatures [4], [16]. The resulting scheme is publicly verifiable, ambiguous until claimed, and provably secure from decisional MLWE, MSIS, and the unforgeability of the base signature.

1.1 Related work↩︎

1.1.0.1 Withdrawable signatures.

Withdrawable signatures were introduced in [1] with a designated-verifier construction, and extended to the publicly verifiable, \(N\)-signer setting in [4]. A lattice-based designated-verifier variant over the Fiat-Shamir with aborts paradigm was given in [12]; the present paper is its extended, publicly verifiable counterpart.

1.1.0.2 Designated-verifier and universal designated-verifier signatures.

Designated-verifier signatures were introduced independently by Jakobsson, Sako and Impagliazzo [2] and by Chaum [3], and studied extensively thereafter [17], [18]. Universal designated-verifier signatures (UDVS), in which any holder of a signature can designate a verifier, were initiated by Steinfeld et al. [19] and extended to Schnorr and RSA signatures in [20]; a lattice-based UDVS appears in [21].

1.1.0.3 Ring signatures and one-out-of-many proofs.

Ring signatures, introduced by Rivest, Shamir and Tauman [5], let a signer produce a signature on behalf of a self-chosen set of public keys while hiding which member signed; constructions exist from RSA, discrete-logarithm [22], pairing [23] and lattice [14] assumptions. A generic route is the one-out-of-many zero-knowledge proof of Groth and Kohlweiss [13], with a short lattice instantiation by Esgin et al. [14]. Our \(1\)-out-of-\(N\) building block is any such scheme with anonymity under full key exposure.

1.1.0.4 Claimable ring and designated-verifier signatures.

Park and Sealfon [15] introduced claimable ring signatures, which let an anonymous signer later prove authorship, and Yamashita et al. [16] the analogous claimable designated-verifier signatures. As Liu, Susilo and Baek observe [4], both are instantiations of withdrawable signatures: the “claim” is exactly the confirmation step. Our construction makes this correspondence its design principle.

1.1.0.5 Lattice signatures from Fiat-Shamir with aborts.

The Fiat-Shamir heuristic [24] and its lattice adaptation with aborts [9] underlie Dilithium [10] and HAETAE [11], whose security rests on module lattice problems and, in the quantum random-oracle model, on the analyses of Kiltz, Lyubashevsky and Schaffner [25] and the adaptive-reprogramming lemma of Grilo, Hövelmanns, Hülsing and Majenz [26]. Our commitment layer uses an Ajtai-style commitment [27].

1.2 Contributions↩︎

Concretely, this paper makes the following contributions.

1. Security model: We adopt the syntax and the three security goals, correctness, unforgeability under insider corruption, and extended withdrawability, of Liu, Susilo and Baek [4], and we sharpen their formalisation of extended withdrawability. Their definition asserts only that a withdrawable signature can be re-attributed to another member and still verify (a completeness statement), delegating the hiding guarantee to the signer ambiguity of the underlying \(1\)-out-of-\(N\) scheme. We fold both into a single anonymity-until-claim indistinguishability game (Definition 14), state unforgeability under insider corruption as an explicit experiment (Definition 15), and add a claimability soundness notion (Definition 16) that makes precise the requirement that only the true author can confirm.

2. Generic construction: We give a generic construction of extended withdrawable signatures over the Fiat-Shamir with aborts paradigm (Section 5) from three modular ingredients: any base signature, any anonymous \(1\)-out-of-\(N\) signature, and any hiding-and-binding commitment. Crucially, and in contrast with a literal transcription of the discrete-logarithm scheme, the construction publishes no signer-derived value: ambiguity comes from the ring signature and traceability from a committed index, avoiding the signer-identifying leak described above.

3. Complete security proofs: We prove, with fully explicit game-based reductions in the (quantum) random-oracle model (Section 6): correctness; extended withdrawability, reducing to decisional MLWE (commitment hiding) and the anonymity of the \(1\)-out-of-\(N\) scheme; unforgeability under insider corruption, reducing to the EUF-CMA security of the base signature (with no rewinding and no multiplicative random-oracle loss); and claimability soundness, reducing to MSIS (commitment binding).

4. Instantiation: We instantiate the base signature with a no-hint, full-\(t\) Dilithium-style scheme and the ambiguity layer with a lattice one-out-of-many proof (Section 7), correcting the parameter choices (the low-order bound \(\gamma_2\), the challenge set \(B_\tau\), and the high/low-order decomposition) and explaining why a naive Dilithium challenge-split is not a sound anonymous ring signature. HAETAE is discussed as an alternative base.

5. Comparison with Liu-Susilo-Baek: We give a precise comparison (Section 8) that traces every divergence from [4] to a single structural fact, the absence of a free re-randomisation of a shared value in the lattice setting, and shows that our claimable-ring-signature design is faithful to their primitive, their security goals, and their own stated intuition.

2 Preliminaries↩︎

2.1 Notation, rings and norms↩︎

We write \(\kappa\) for the security parameter. A function \(\mathsf{negl}:\mathbb{N}\to\mathbb{R}_{\ge 0}\) is negligible if it decays faster than any inverse polynomial; PPT abbreviates probabilistic polynomial-time. For a positive integer \(a\) we write \([a]=\{1,\dots,a\}\); in particular \([N]\) indexes the \(N\) potential signers of a ring, while \(n\) (never bracketed) always denotes the ring degree of \(\mathcal{R}_q\). Sets of public keys carry a fixed canonical total order (say, lexicographic on the encoding \(\langle \mathbf{t} \rangle\)); the index of a key in a ring \(\pi\) always means its position under this order, and when keys are generated in an experiment we relabel them so that \(pk_1<\cdots<pk_N\), making global labels coincide with positions in the full pool. We write \(a\mathrel{\overset{\$}{\leftarrow}}S\) for a uniform draw of \(a\) from a finite set \(S\). All logarithms are base \(2\), and \(\langle \cdot \rangle\) denotes a fixed injective encoding of tuples of bit strings and ring elements into \(\{0,1\}^\ast\).

Let \(n\) be a power of \(2\) and \(q\) an odd prime (with \(q\equiv 1\bmod 2n\) in the Dilithium instantiation, so that \(x^n+1\) splits completely). We work in the rings \(\mathcal{R}=\mathbb{Z}[x]/(x^n+1)\) and \(\mathcal{R}_q=\mathbb{Z}_q[x]/(x^n+1)\). Elements of \(\mathcal{R},\mathcal{R}_q\) are written in regular font; vectors are bold lower-case and are column vectors unless stated otherwise; matrices are bold upper-case; \(\mathbf{I}\) is the identity.

For an even positive integer \(\alpha\) we write \(r\bmod^{\pm}\alpha\) for the unique representative of \(r\bmod\alpha\) in \((-\tfrac{\alpha}{2},\tfrac{\alpha}{2}]\), and for odd \(\alpha\) in \([-\tfrac{\alpha-1}{2},\tfrac{\alpha-1}{2}]\) (centred reduction); \(r\bmod^{+}\alpha\) is the representative in \([0,\alpha)\). For \(w\in\mathbb{Z}_q\) set \(\lVert w\rVert_\infty=\lvert w\bmod^{\pm}q\rvert\). For \(w=\sum_{i=0}^{n-1}w_i x^i\in\mathcal{R}\) set \(\lVert w\rVert_\infty=\max_i\lVert w_i\rVert_\infty\) and \(\lVert w\rVert=(\sum_i\lVert w_i\rVert_\infty^2)^{1/2}\), and for \(\mathbf{w}=(w_1,\dots,w_k)\in\mathcal{R}^k\), \(\lVert\mathbf{w}\rVert_\infty=\max_i\lVert w_i\rVert_\infty\) and \(\lVert\mathbf{w}\rVert=(\sum_i\lVert w_i\rVert^2)^{1/2}\). For \(\eta\in\mathbb{N}\) let \(S_\eta=\{w\in\mathcal{R}:\lVert w\rVert_\infty\le\eta\}\); when the exact bound is dictated by the underlying scheme we write simply \(S\). The challenge set \(B_\tau\subset\mathcal{R}\) is the set of elements with exactly \(\tau\) coefficients in \(\{-1,1\}\) and the rest \(0\); then \(\lvert B_\tau\rvert=2^{\tau}\binom{n}{\tau}\) and every \(c\in B_\tau\) has \(\lVert c\rVert_\infty=1\) and \(\lVert c\mathbf{s}\rVert_\infty\le\tau\lVert\mathbf{s}\rVert_\infty\).

2.2 The (quantum) random-oracle model↩︎

A hash function \(H\) used inside a Fiat-Shamir transform is modelled as a random oracle: a function drawn uniformly from all functions of the given domain and range, accessible to all parties only as an oracle. In the classical random-oracle model (ROM) queries are classical; in the quantum random-oracle model (QROM) an adversary may query \(H\) on superpositions of inputs. Security reductions may program the oracle, answering a chosen input with a chosen (consistently distributed) value; in the QROM this is governed by the adaptive-reprogramming lemma of [26]. Unless noted, all results are stated in the classical ROM and lifted to the QROM in Remark 6.

2.3 High-order and low-order bits↩︎

Following Dilithium [10], for an even \(\alpha\mid(q-1)\) the decomposition of \(w\in\mathbb{Z}_q\) writes \(w=\mathop{\mathrm{\mathsf{HighBits}}}(w,\alpha)\cdot\alpha+\mathop{\mathrm{\mathsf{LowBits}}}(w,\alpha)\) with \(\mathop{\mathrm{\mathsf{LowBits}}}(w,\alpha)=w\bmod^{\pm}\alpha\) (and a boundary correction ensuring \(\mathop{\mathrm{\mathsf{HighBits}}}\in\{0,\dots,(q-1)/\alpha\}\)); the maps extend coordinatewise to \(\mathcal{R}\) and to vectors. Intuitively \(\mathop{\mathrm{\mathsf{HighBits}}}\) keeps the top part of \(w\) and \(\mathop{\mathrm{\mathsf{LowBits}}}\) the signed remainder of magnitude \(\le\alpha/2\). We use the following standard stability property, which is the basis of correctness of every Fiat-Shamir with aborts scheme.

2.4 Digital signatures and EUF-CMA↩︎

2.5 Fiat-Shamir with aborts signatures↩︎

Our base signatures follow Lyubashevsky’s Fiat-Shamir with aborts paradigm [9]. Keys are \(pk=\mathbf{t}=A\mathbf{s}_1+\mathbf{s}_2\) with short \((\mathbf{s}_1,\mathbf{s}_2)\) and a public matrix \(A\) (Section 2.8); signing draws a masking vector \(\mathbf{y}\mathrel{\overset{\$}{\leftarrow}}S^l_{\gamma_1-1}\), forms the commitment \(\mathbf{w}=\mathop{\mathrm{\mathsf{HighBits}}}(A\mathbf{y},2\gamma_2)\), derives a challenge \(c=H(\mu,\mathbf{w})\in B_\tau\), sets the response \(\mathbf{z}=\mathbf{y}+c\mathbf{s}_1\), and rejects (restarting) unless \(\mathbf{z}\) and \(\mathop{\mathrm{\mathsf{LowBits}}}(A\mathbf{y}-c\mathbf{s}_2,2\gamma_2)\) lie within scheme-dependent bounds; verifying recomputes \(\mathop{\mathrm{\mathsf{HighBits}}}(A\mathbf{z}-c\mathbf{t},2\gamma_2)\) and checks it hashes to \(c\). The rejection step makes the output distribution independent of the secret key: the accepted transcript admits an efficient, witness-free simulator (non-abort honest-verifier zero-knowledge, naHVZK), a property we invoke for the ambiguity layer. Dilithium [10] and HAETAE [11] are concrete instances; we use such a scheme as the black-box base \(\mathop{\mathrm{\mathsf{DS}}}\) of Definition 1.

2.6 Hardness assumptions↩︎

Security rests on three module-lattice assumptions. Informally, MLWE guards secret keys against key recovery, SelfTargetMSIS is the assumption behind new-message unforgeability of Fiat-Shamir with aborts signatures, and MSIS underlies strong unforgeability (resistance to malleability of existing signatures).

All three are assumed hard for the parameter sets of Section 7.

2.7 Commitment schemes↩︎

2.8 Public parameters↩︎

Throughout, \(pp\gets\mathop{\mathrm{\mathsf{Setup}}}(1^\kappa)\) fixes a common matrix \(A\in\mathcal{R}_q^{k\times l}\) and a commitment key \(ck\); every user key is generated relative to the same \(A\). This shared \(A\) is essential: the one-out-of-\(N\) proof is a membership proof for the relation \(\{\,\mathbf{t}:\exists\,(\mathbf{s}_1,\mathbf{s}_2)\;\text{short},\;\mathbf{t}=A\mathbf{s}_1+\mathbf{s}_2\,\}\), which is a single well-formed relation across the ring only when every \(\mathbf{t}_j\) is generated against the same \(A\).

3 Building block: an anonymous one-out-of-\(N\) signature↩︎

A one-out-of-\(N\) signature lets a signer produce, for a self-chosen set \(\pi=\{\mathbf{t}_1,\dots,\mathbf{t}_N\}\) of public keys containing its own, a signature that verifies under \(\pi\) yet hides which member signed [4]. It is the engine that supplies ambiguity to an extended withdrawable signature.

3.1 Role and design decision↩︎

Extended withdrawability is delivered by an anonymous one-out-of-\(N\) signature: the withdrawable signature is such a signature over the set of potential signers, and being withdrawable is exactly being signer-ambiguous. This is the design of Liu, Susilo and Baek [4], who realise the one-out-of-\(N\) signature by a concrete construction from discrete-logarithm primitives (Algorithm 1) and prove its signer ambiguity directly. We depart from their treatment in one respect: we specify the one-out-of-\(N\) signature abstractly, through the two security properties we actually use (Definitions 9–11), and instantiate it with an established lattice one-out-of-many proof. There are two reasons, one methodological and one forced by the setting.

• Modularity: Fixing the exact interface separates the security of the withdrawable layer from that of the ambiguity engine: the reductions of Section 6 then rest on a single, clearly stated assumption, signer ambiguity under full key exposure, rather than on the internals of one particular ring signature. Any scheme meeting the interface may be plugged in.

• Necessity: The specific discrete-logarithm construction of [4] has no secure literal lattice analogue (Proposition 1 below). A faithful post-quantum port therefore cannot transcribe it; it must use a genuinely lattice-based ring-signature technique, which is most naturally invoked as a black box. Treating \(\mathop{\mathrm{\mathsf{Ambi}}}\) abstractly is thus not only cleaner but unavoidable.

3.2 The discrete-logarithm one-out-of-\(N\) signature of Liu-Susilo-Baek↩︎

For reference we recall the construction of [4]. Let \(G\) be a group of prime order \(p\) with generator \(g\), \(H:\{0,1\}^\ast\to\mathbb{Z}_p\), and \(pk_j=g^{sk_j}\).

Correctness is immediate: \(U'=g^z\prod_j pk_j^{t_j}=g^{e-sk_i t_i}\prod_j g^{sk_j t_j}=g^e\prod_{j\ne i}pk_j^{t_j}=U\), and \(\sum_j t_j=t\). Signer ambiguity holds because the challenge space is a field: a witness-free simulator draws \(t_1,\dots,t_N,z\mathrel{\overset{\$}{\leftarrow}}\mathbb{Z}_p\), sets \(U'=g^z\prod_j pk_j^{t_j}\), and programs \(H(m,\gamma,U'):=\sum_j t_j\); its output is distributed exactly as a real signature and is independent of the signer index. Two features make this work, and both are lost over lattices: the recombined challenge \(t_i=t-\sum_{j\ne i}t_j\) may take any value in \(\mathbb{Z}_p\), and the response \(z=e-sk_i t_i\) is a uniform field element (as \(e\) is uniform), so no rejection is needed.

3.3 Why a literal lattice transcription fails↩︎

The Fiat-Shamir with aborts setting keeps challenges in the sparse set \(B_\tau\) and responses short (this is what makes the response leak no information and the proof sound). These requirements are incompatible with the additive challenge-splitting of Algorithm 1.

3.4 Abstract syntax and security↩︎

We now record the interface used in the sequel.

Ambiguity under full key exposure, the adversary knows every witness, is precisely what a one-out-of-many zero-knowledge proof provides, since the accepted transcript is (statistically or computationally) independent of the witness used. It is exactly the strength we need: in the withdrawability and unforgeability games of Section 6 the adversary may hold ring members’ secret keys. The two-key left-or-right game above is equivalent, up to a factor equal to the ring size, to the “guess the signer” formulation of [4], whose signer-ambiguity advantage is bounded by \((\text{ring size})^{-1}+\mathsf{negl}\).

3.5 Instantiation↩︎

We instantiate \(\mathop{\mathrm{\mathsf{Ambi}}}\) by an established lattice one-out-of-many proof [13], [14]: a zero-knowledge proof that one of the public keys in \(\pi\) opens to a short witness, made non-interactive by Fiat-Shamir. Its signer ambiguity (Definition 10) is the honest-verifier zero-knowledge of the underlying \(\Sigma\)-protocol, which holds under full key exposure, as it uses no witness, and its unforgeability (Definition 11) is the knowledge soundness of the proof, reducing to MSIS. Such proofs achieve size logarithmic in the ring, and by Proposition 1 they, rather than a naive challenge-split, are the correct lattice realisation. Only signer ambiguity is invoked in the proofs of the main construction (Section 6); Definition 11 is recorded for completeness and matches the treatment of [4].

In particular, the one-out-of-many proofs of [13], [14] are anonymous under full key exposure via the special honest-verifier zero-knowledge of their \(\Sigma\)-protocol, so Definition 10 is met concretely rather than merely assumed.

4 Extended withdrawable signatures: syntax and security↩︎

Our security model is that of Liu, Susilo and Baek [4]: the same seven-algorithm syntax and the same three goals, correctness, unforgeability under insider corruption, and extended withdrawability. We refine it in two respects, both stated and justified in Section 4.1: we replace their completeness-style definition of extended withdrawability by an indistinguishability game (Definition 14), and we add an explicit claimability-soundness notion (Definition 16). Section 4.1 then compares every definition, assumption and security statement with its counterpart in [4], and justifies each discrepancy. Throughout, \(N\ge 2\) is the number of potential signers and \(i\) the index of the true signer.

4.1 Relation to the Liu-Susilo-Baek model↩︎

We now compare each notion above with its counterpart in [4] and justify every discrepancy. The definitional comparison is summarised, alongside the construction-level differences, in the consolidated comparison of Section 8 (Table 1); here we take each notion in turn.

4.1.0.1 Syntax (Definition 12).

Both models use the same seven algorithms (Definition 12) with the same roles: \(\mathop{\mathrm{\mathsf{Shuffle}}}\) publishes \(aux=\pi\setminus\{pk\}\), \(\mathop{\mathrm{\mathsf{WSVerify}}}\) is public, and \(\mathop{\mathrm{\mathsf{Check}}}\) ties a confirmed signature to its withdrawable object. The only differences are in the argument lists of \(\mathop{\mathrm{\mathsf{Confirm}}}\) and \(\mathop{\mathrm{\mathsf{CVerify}}}\): [4] write \(\mathop{\mathrm{\mathsf{Confirm}}}(m,sk,\sigma)\) and \(\mathop{\mathrm{\mathsf{CVerify}}}(m,pk,\tilde{\sigma})\) in their syntax (while silently passing \(aux\) and \(\sigma\) in the construction), whereas we make the dependence explicit, \(\mathop{\mathrm{\mathsf{Confirm}}}(\mu,sk,pk,aux,\sigma)\) and \(\mathop{\mathrm{\mathsf{CVerify}}}(\mu,pk,\sigma,\delta)\). Justification: in our construction the confirmed signature is an ordinary signature on the whole withdrawable object \(\langle \mu,\pi,\sigma \rangle\), so both \(\mathop{\mathrm{\mathsf{Confirm}}}\) and \(\mathop{\mathrm{\mathsf{CVerify}}}\) must read \(\sigma\) (and \(\pi\), reconstructed from \(pk\) and \(aux\)); making this explicit keeps traceability intrinsic to the confirmed signature rather than deferring it entirely to \(\mathop{\mathrm{\mathsf{Check}}}\).

4.1.0.2 Correctness (Definition 13).

This is identical to [4]: an honestly produced withdrawable signature passes \(\mathop{\mathrm{\mathsf{WSVerify}}}\), its confirmation passes \(\mathop{\mathrm{\mathsf{CVerify}}}\), and the pair passes \(\mathop{\mathrm{\mathsf{Check}}}\), all with overwhelming probability. No discrepancy.

4.1.0.3 Unforgeability under insider corruption (Definition 15).

This matches [4] in substance: the adversary has a corruption oracle, a withdrawable signing oracle and a confirmation oracle, may hold every ring member’s key except the target’s, and wins by confirming a fresh message under the target key with all three verifications passing. Two refinements. (i) Fixed target. [4] generate a pool of keys and let the adversary forge for whichever uncorrupted index it chooses; we fix the target index \(i\) in advance. This is without loss of generality up to a factor \(N\) (a reduction guesses \(i\); see Theorem 4) and makes the reduction cleaner. (ii) Bookkeeping. We record signed tuples in \(W\) and let \(\mathcal{O}\mathsf{Confirm}\) act only on \(\sigma\in W\); [4] do the same (“if \(\sigma\in W\)”). A point of rigour rather than definition: [4] claims a reduction loss \(L=q_H\) (the number of hash queries), whereas our reduction (Theorem 4) incurs no multiplicative \(q_H\) factor, it neither rewinds the adversary nor guesses a hash index, the only losses being the factor \(N\) above and a \(q_W\mathsf{Adv}^{\mathsf{anon}}_{\mathop{\mathrm{\mathsf{Ambi}}}}\) term from simulating the signing oracle. We view the tighter reduction as a benefit of the modular treatment.

4.1.0.4 Extended withdrawability (Definition 14): the main discrepancy.

Here we depart from [4] deliberately. Their Definition 3 declares the experiment successful when the adversary outputs \((pk',aux')\) with \(aux'=\gamma\setminus\{pk'\}\) and \(\mathop{\mathrm{\mathsf{WSVerify}}}(m^\ast,pk',\sigma^\ast)=1\), and requires \(\Pr[\mathsf{Exp}^{\mathsf{Withdraw}}=1]=1\). This is a completeness statement, it asserts that a withdrawable signature can always be re-attributed to another ring member and still verify, and it contains no hidden bit, hence no hiding guarantee. Read literally, it is met by any scheme whose \(\mathop{\mathrm{\mathsf{WSVerify}}}\) accepts, including one that plainly reveals the signer. [4] obtain the actual hiding elsewhere, from the signer ambiguity of the underlying one-out-of-\(N\) signature (their Definition 4) together with the “\(1/n\)-guess” step in the proof of their Theorem 3. We instead fold both into a single anonymity-until-claim game (Definition 14): a hidden bit \(b\) selects which of two signer identities produces the challenge, the advantage \(\lvert\Pr[b'=b]-\tfrac12\rvert\) must be negligible, and the “until claim” clause is enforced by withholding the challenge randomness \(\rho^\ast\), so that the commitment \(C^\ast\) cannot be opened and \(\sigma^\ast\) cannot be confirmed. Justification: (a) a completeness statement is not a security definition, so the hiding must be phrased as indistinguishability; (b) our game captures exactly the guarantee [4] intend, ambiguity among the potential signers until confirmation, now as one self-contained notion that the construction provably meets (Theorem 3), rather than a property split across a completeness claim and a building-block assumption; and (c) nothing is lost, since the re-attribution completeness that Definition 3 does capture is, in our treatment, an immediate consequence of correctness of ring verification (\(\mathop{\mathrm{\mathsf{WSVerify}}}\) accepts for every \(pk'\in\pi\)). This is the most consequential definitional change and the reason our withdrawability theorem is a reduction to commitment hiding and ring anonymity rather than a probability-one assertion.

4.1.0.5 Signer ambiguity of the building block (Definition 10).

The hiding that [4] place in their Definition 4 (signer ambiguity of the one-out-of-\(N\) signature, advantage \(\le\tfrac1N+\mathsf{negl}\)) survives verbatim as our Definition 10, stated as a two-key left-or-right game under full key exposure and equivalent to theirs up to the factor \(N\). In our model it lives with the building block (Section 3) and is invoked by the withdrawability theorem, rather than standing beside the withdrawability definition; this is the structural counterpart of folding Definition 3 and Definition 4 into one notion.

4.1.0.6 Claimability soundness (Definition 16): a new notion.

[4] have no explicit counterpart. Their \(\mathop{\mathrm{\mathsf{Check}}}\) links \(\tilde{\sigma}\) to \(\sigma\) (through the embedded group element \(g^r\)), and their unforgeability prevents a non-signer from confirming, but they never isolate the property that a confirmed signature binds to a unique signer index, that no adversary can present two valid confirmations of one \(\sigma\) attributing it to different members. In our construction the signer’s index is an explicit committed value, so this property is both meaningful and necessary for “claim” to be sound; we state it as Definition 16 and prove it (Proposition 5) from the binding of the commitment. Justification: this is exactly the claimability of a claimable ring signature [15], the abstraction [4] themselves point to; making it explicit closes a gap in the original model.

4.1.0.7 Assumptions.

The model of [4] is realised under the discrete-logarithm assumption (via the EUF-CMA security of the discrete-log signature and the ambiguity of the discrete-log one-out-of-\(N\) signature). We replace these by their post-quantum, module-lattice analogues (Section 2.6): decisional MLWE, MSIS and SelfTargetMSIS, together with the base signature’s EUF-CMA and the ring signature’s anonymity. Our claimable-ring design additionally uses a commitment, hence the extra hiding (MLWE) and binding (MSIS) assumptions of Section 2.7; [4] need no commitment because their confirmation links through the group element \(g^r\), a re-randomisation that is free in a prime-order group but has no cheap lattice analogue (Section 8).

4.1.0.8 Security statements and their proofs.

Beyond the definitions, our results correspond to the three theorems of [4], and our proofs close gaps in theirs.

• Unforgeability: [4] reduces to the EUF-CMA security of the discrete-log signature but asserts a reduction loss \(L=q_H\) with no rewinding or hash-guessing argument, and in extracting the forgery it identifies the confirmed component with the underlying signature. Our Theorem 4 gives an explicit reduction with no \(q_H\) loss and a clean extraction: the confirmed signature \(\delta_s\) on the fresh string \(\langle \mu^\ast,\pi^\ast,\sigma^\ast \rangle\) is the base forgery.

• Signer ambiguity: [4] simulates the challenge by a uniform tuple \((t_1,\dots,t_N,z)\) and concludes advantage \(1/2\) “since \(b,sk_b\) are unused”; the step that makes the simulated tuple verify, programming \(H\) at the induced commitment, is left implicit. Over a field this is harmless (a uniform tuple can always be made to verify), but the same omission is fatal over lattices, where a uniform tuple neither lies in the sparse set \(B_\tau\) nor passes the rejection test (Proposition 1). We therefore take ambiguity to be the zero-knowledge of a one-out-of-\(N\) proof (Definition 10), made rigorous with the programming step explicit.

• Extended withdrawability: [4] argues that, ambiguity holding, the adversary guesses the signer with probability \(1/N\) and that \(\mathop{\mathrm{\mathsf{WSVerify}}}\) still accepts, a mixture of an informal \(1/N\) bound and the completeness of re-attribution. Our Theorem 3 is a game-based reduction to commitment hiding and ring anonymity, and we additionally prove claimability soundness (Proposition 5), for which [4] state no result.

• A new statement: Proposition 1 (no secure literal lattice transcription) has no counterpart in [4]: it is a lattice-specific impossibility that justifies treating the one-out-of-\(N\) signature as a black box rather than transcribing their concrete scheme.

4.1.0.9 Relation to the earlier lattice transcription.

A direct lattice transcription of [4] adopts their definitions verbatim, including the completeness-style Definition 3 and the informal ambiguity argument, and so inherits the gaps above, compounded by two lattice-specific defects: it publishes a signer-derived shift \(\{A\mathbf{s}_1 s_j\}\) that breaks ambiguity (Section 8), and its one-out-of-\(N\) layer is the unsound challenge-split of Proposition 1. The refinements of this section, the hiding game (Definition 14), the explicit claimability notion (Definition 16), and the black-box ambiguity assumption (Definition 10), correct issues present in both [4] and that transcription, and are exactly what the construction of Section 5 is designed to satisfy.

5 The construction↩︎

5.1 Ingredients and random oracles↩︎

The construction combines the three primitives fixed in Sections 2.4–2.7.

1. A Fiat-Shamir with aborts base signature \(\mathop{\mathrm{\mathsf{DS}}}=(\mathop{\mathrm{\mathsf{KeyGen}}},\mathop{\mathrm{\mathsf{Sign}}},\mathop{\mathrm{\mathsf{Verify}}})\) over the common matrix \(A\) (Section 2.5), whose signing algorithm evaluates a challenge random oracle \(H_{\mathop{\mathrm{\mathsf{DS}}}}:\{0,1\}^\ast\to B_\tau\).

2. An anonymous one-out-of-\(N\) signature \(\mathop{\mathrm{\mathsf{Ambi}}}=(\mathop{\mathrm{\mathsf{AKeyGen}}},\mathop{\mathrm{\mathsf{ASign}}},\mathop{\mathrm{\mathsf{AVerify}}})\) (Section 3), whose non-interactive proof evaluates its own challenge oracle \(H_{\mathop{\mathrm{\mathsf{Ambi}}}}:\{0,1\}^\ast\to\mathcal{X}\), where \(\mathcal{X}\) is the challenge space of the underlying \(\Sigma\)-protocol (a bounded subset of \(\mathcal{R}_q\) for a one-out-of-many proof; any finite set for the abstract interface). We take \(\mathop{\mathrm{\mathsf{AKeyGen}}}=\mathop{\mathrm{\mathsf{KeyGen}}}\), so ring members and signers share the key format \(pk=\mathbf{t}=A\mathbf{s}_1+\mathbf{s}_2\), \(sk=(\mathbf{s}_1,\mathbf{s}_2)\).

3. A commitment \(\mathop{\mathrm{\mathsf{Com}}}_{ck}:\mathcal{M}\times S^m\to\mathcal{R}_q^{k'}\) with key \(ck=\bar A\in\mathcal{R}_q^{k'\times m}\) (Section 2.7), together with an injective index encoding \(\mathop{\mathrm{\mathsf{Encode}}}:[N]\to\mathcal{M}\); we write \(\mathop{\mathrm{\mathsf{Com}}}_{ck}(i;\rho)\) for \(\mathop{\mathrm{\mathsf{Com}}}_{ck}(\mathop{\mathrm{\mathsf{Encode}}}(i);\rho)\), where \(i\) is the signer’s position in \(\pi\) under the canonical order of Section 2.1, so that “the committed index” names a unique ring member.

Here \(\langle \cdot \rangle:(\{0,1\}^\ast)^\ast\to\{0,1\}^\ast\) is the fixed injective tuple encoding of Section 2.1. The two random oracles \(H_{\mathop{\mathrm{\mathsf{DS}}}}\) and \(H_{\mathop{\mathrm{\mathsf{Ambi}}}}\) are domain-separated (say, by a distinct one-bit prefix), so a query to one is never a query to the other; the extended withdrawable signature introduces no further oracle of its own, invoking \(H_{\mathop{\mathrm{\mathsf{DS}}}},H_{\mathop{\mathrm{\mathsf{Ambi}}}}\) only through \(\mathop{\mathrm{\mathsf{Sign}}}/\mathop{\mathrm{\mathsf{Verify}}}\) and \(\mathop{\mathrm{\mathsf{ASign}}}/\mathop{\mathrm{\mathsf{AVerify}}}\). Correctness and security are stated in the (quantum) random-oracle model (Section 2.2).

5.2 Setup and key generation↩︎

\(\mathop{\mathrm{\mathsf{Setup}}}\) fixes the parameters shared by all users: a uniform module matrix \(A\mathrel{\overset{\$}{\leftarrow}}\mathcal{R}_q^{k\times l}\) and a commitment key \(\bar A\mathrel{\overset{\$}{\leftarrow}}\mathcal{R}_q^{k'\times m}\). A single common \(A\) is essential (Section 2.8): each public key is the module-LWE sample \(\mathbf{t}=A\mathbf{s}_1+\mathbf{s}_2\in\mathcal{R}_q^k\) taken against the same \(A\), so that the membership relation “\(\exists\) short \((\mathbf{s}_1,\mathbf{s}_2):\mathbf{t}_j=A\mathbf{s}_1+\mathbf{s}_2\)” proved by the one-out-of-\(N\) layer is identical for every ring member, which is what makes “one of the \(\mathbf{t}_j\) opens to a short witness” a well-formed statement across \(\pi\). The secret key is the short pair \((\mathbf{s}_1,\mathbf{s}_2)\in S^l_\eta\times S^k_\eta\); its shortness is what the base signature’s rejection sampling exploits and what decisional MLWE (Definition 3) protects against key recovery. Finally, \(\mathop{\mathrm{\mathsf{Setup}}}\) is a public-coin common reference string: \(A\) and \(\bar A\) are uniformly sampled and no party holds, or needs, a trapdoor, since binding (MSIS) and hiding (MLWE) hold for uniformly generated \(\bar A\).

The contrast with the group-based \(\mathop{\mathrm{\mathsf{KeyGen}}}\) of [4] is discussed in Section 8.3.

5.3 Withdrawable signing and public verification↩︎

\(\mathop{\mathrm{\mathsf{WSign}}}\) proceeds in two steps. First it commits to its own index: it samples short randomness \(\rho\mathrel{\overset{\$}{\leftarrow}}S^m\) and sets \(C=\mathop{\mathrm{\mathsf{Com}}}_{ck}(i;\rho)\in\mathcal{R}_q^{k'}\), a commitment that hides \(i\) under decisional MLWE (Definition 7) and to which the signer will later be bound (Definition 8). Second, it produces a one-out-of-\(N\) signature on the message \(\langle \mu,C \rangle\) over the ring \(\pi=aux\cup\{pk_i\}\) using its own witness, \(\sigma_r\gets\mathop{\mathrm{\mathsf{ASign}}}(\langle \mu,C \rangle,sk_i,\pi)\). Folding \(C\) into the signed message binds the commitment to the transcript through \(H_{\mathop{\mathrm{\mathsf{Ambi}}}}\), so \(C\) cannot be stripped or replaced without invalidating \(\sigma_r\); this is what makes the later claim sound (Remark 4). The withdrawable signature is \(\sigma=(\sigma_r,C,aux)\). Verification is public: \(\mathop{\mathrm{\mathsf{WSVerify}}}\) reconstructs \(\pi=aux\cup\{pk\}\) and returns \(\mathop{\mathrm{\mathsf{AVerify}}}(\langle \mu,C \rangle,\pi,\sigma_r)\), reading only public keys.

Two properties are immediate from the algorithm. Ambiguity: \(\sigma_r\) hides the signer index by the anonymity of \(\mathop{\mathrm{\mathsf{Ambi}}}\) (Definition 10) and \(C\) hides it by commitment hiding, so \(\sigma\) leaks nothing about which member of \(\pi\) signed. Extended withdrawability (re-attribution): for any \(pk'\in\pi\) the repackaged signature \(\sigma'=(\sigma_r,C,\pi\setminus\{pk'\})\) verifies, \(\mathop{\mathrm{\mathsf{WSVerify}}}(\mu,pk',\sigma')=1\), since \((\pi\setminus\{pk'\})\cup\{pk'\}=\pi\); one withdrawable signature verifies under every potential signer. This is exactly the completeness that Definition 3 of [4] isolates, and which our hiding game (Definition 14) subsumes. The corresponding change to \(\mathop{\mathrm{\mathsf{WSign}}}\), a committed index in place of published shifts, is compared in Section 8.3.

5.4 Confirmation, confirmed verification and checking↩︎

\(\mathop{\mathrm{\mathsf{Confirm}}}\) is the signer’s claim, and it is stateful in one respect: per signature, the signer retains the opening randomness \(\rho\) drawn inside \(\mathop{\mathrm{\mathsf{WSign}}}\) together with its position \(i\) in \(\pi\); the experiments of Section 4 model exactly this by storing \(\rho\) in \(W\). Holding \(sk_i\) and \((i,\rho)\), the signer produces an ordinary base signature on the entire withdrawable object, \(\delta_s\gets\mathop{\mathrm{\mathsf{Sign}}}_{sk_i}(\langle \mu,\pi,\sigma \rangle)\), and reveals the opening \((i,\rho)\) of the index commitment \(C\); the confirmed signature is \(\delta=(\delta_s,i,\rho)\). Signing \(\langle \mu,\pi,\sigma \rangle\) rather than \(\mu\) alone makes \(\delta_s\) inseparable from this particular \(\sigma\), and revealing \((i,\rho)\) lifts the ambiguity by naming the signer. \(\mathop{\mathrm{\mathsf{CVerify}}}\) is public: it returns \(\mathop{\mathrm{\mathsf{Verify}}}_{pk_i}(\langle \mu,\pi,\sigma \rangle,\delta_s)\), so a confirmed signature is checkable under the signer’s public key by anyone. \(\mathop{\mathrm{\mathsf{Check}}}\) certifies traceability on top of \(\mathop{\mathrm{\mathsf{CVerify}}}\): it recomputes \(C=\mathop{\mathrm{\mathsf{Com}}}_{ck}(i;\rho)\) (the revealed index is the one committed inside \(\sigma\)) and requires \(\mathop{\mathrm{\mathsf{WSVerify}}}(\mu,pk_i,\sigma)=1\) as well; hence \(\mathop{\mathrm{\mathsf{Check}}}\) accepts only when \(\delta\) confirms this \(\sigma\) and attributes it to the unique committed signer.

Our \(\mathop{\mathrm{\mathsf{Confirm}}}\) replaces their two signatures and embedded group element by one base signature and one commitment opening; see Section 8.3.

6 Security analysis↩︎

We establish, in the (quantum) random-oracle model, the four properties of Section 4: correctness (Theorem 2), extended withdrawability (Theorem 3), unforgeability under insider corruption (Theorem 4) and claimability soundness (Proposition 5). Each result reduces the security of the composed scheme to a single, previously stated guarantee of an ingredient: correctness to the correctness of \(\mathop{\mathrm{\mathsf{DS}}},\mathop{\mathrm{\mathsf{Ambi}}},\mathop{\mathrm{\mathsf{Com}}}\); extended withdrawability to commitment hiding (hence decisional MLWE) and the anonymity of \(\mathop{\mathrm{\mathsf{Ambi}}}\); unforgeability to the EUF-CMA security of the base signature \(\mathop{\mathrm{\mathsf{DS}}}\); and claimability soundness to commitment binding (hence MSIS). All reductions are tight up to the stated additive terms and the factor \(N\) from guessing the target signer, and none rewinds the adversary. Throughout we write \(\sigma=(\sigma_r,C,aux)\), \(\delta=(\delta_s,i,\rho)\) and \(\pi=aux\cup\{pk_i\}\) as in Section 5.

Correctness requires that an honestly generated withdrawable signature and its confirmation pass all three verification algorithms. Because the construction is modular, this follows from the correctness of the three ingredients; the lattice rounding that makes it hold at the concrete level is confined to \(\mathop{\mathrm{\mathsf{DS}}}\) and \(\mathop{\mathrm{\mathsf{Ambi}}}\) and rests on the rounding-stability Lemma 1.

Extended withdrawability is the hiding guarantee: until the signer confirms, no efficient adversary, even one holding every secret key in the ring, can tell which of two nominated members produced a withdrawable signature. Exactly two components of \(\sigma\) could betray the signer: the index commitment \(C\) and the ring signature \(\sigma_r\). The proof neutralises them in turn by a three-game sequence, first replacing \(C\) by a commitment to a fixed dummy index (commitment hiding), then re-signing \(\sigma_r\) with a fixed witness (ring anonymity), after which the challenge is manifestly independent of the hidden bit \(b\). Crucially, since \(\mathcal{A}\) holds all keys it answers its own \(\mathop{\mathrm{\mathsf{WSign}}}\) and \(\mathop{\mathrm{\mathsf{Confirm}}}\) queries, so the reduction alters only the challenge \(\sigma^\ast\); and \(\mathcal{A}\) cannot confirm \(\sigma^\ast\), because the challenge randomness \(\rho^\ast\) (which would open \(C^\ast\)) is withheld, this is the “until claim” clause.

Unforgeability under insider corruption guarantees that only the genuine signer can confirm: no adversary, even one holding every ring member’s key except the target’s, can output a confirmed signature on a message the target never confirmed. Note the withdrawable signature \(\sigma_r\) is itself a ring signature that the adversary could forge with a corrupted witness, so the unforgeable core is the confirmation, where \(\delta_s\) is a base signature under the target key \(pk_i\) on the whole object \(\langle \mu,\pi,\sigma \rangle\). Accordingly the reduction plants the EUF-CMA challenge at \(pk_i\): it answers withdrawable-signing queries without \(sk_i\) by ring-signing with a corrupted witness (indistinguishable by anonymity, Step 1) and confirmation queries through its own signing oracle, so that a confirmed forgery on a fresh message is exactly a base-scheme forgery (Step 2). The reduction never rewinds and incurs no multiplicative \(q_H\) factor, the point of rigour on which it improves [4].

Claimability soundness makes the confirmation unambiguous: a confirmed signature must bind to a single signer, so that an adversary cannot present one withdrawable signature \(\sigma\) with two valid confirmations attributing it to different ring members. This is the property that gives the committed index its meaning, without it, “confirming” would not pin down who signed, and it reduces directly to the binding of the commitment, hence to MSIS.

7 Instantiation↩︎

Take \(\mathop{\mathrm{\mathsf{DS}}}\) to be a no-hint, full-\(t\) Dilithium-style signature: challenge set \(B_\tau\) with \(\tau\in\{39,49,60\}\), \(\gamma_2=(q-1)/88\) (level 2) or \((q-1)/32\) (levels 3,5), not \(\gamma_1/2\), and rejection \(\lVert\mathbf{z}\rVert_\infty<\gamma_1-\beta\), \(\lVert\mathop{\mathrm{\mathsf{LowBits}}}(A\mathbf{z}-c\mathbf{t},2\gamma_2)\rVert_\infty<\gamma_2-\beta\); its EUF-CMA security follows from SelfTargetMSIS and MSIS. Take \(\mathop{\mathrm{\mathsf{Ambi}}}\) to be a lattice one-out-of-many proof [13], [14] over the same \(A\), whose anonymity under full key exposure is its zero-knowledge; and \(\mathop{\mathrm{\mathsf{Com}}}\) the Ajtai commitment of Section 2.7.

HAETAE may replace Dilithium as the base \(\mathop{\mathrm{\mathsf{DS}}}\) once its bimodal-Gaussian rejection is shown to meet the same EUF-CMA interface; it plays no role in the ambiguity or commitment layers.

Quantitatively, the binding solution extracted in Proposition 5 has norm \(\gamma=\lVert\mathbf{y}\rVert_\infty\le\max(2B_{\mathop{\mathrm{\mathsf{Encode}}}},\,2\lVert S\rVert_\infty)\), with \(B_{\mathop{\mathrm{\mathsf{Encode}}}}\) bounding the encoded indices (Remark 1) and \(\lVert S\rVert_\infty\) the commitment randomness; the claimability bound is meaningful only when this \(\gamma\) lies below the \(\mathsf{MSIS}_{k',m,\gamma}\) hardness threshold (indexing as in Definition 4) for the chosen \((q,n,k',m)\). A concrete parameter set simultaneously meeting \(\mathop{\mathrm{\mathsf{DS}}}\) EUF-CMA, \(\mathop{\mathrm{\mathsf{Ambi}}}\) zero-knowledge, MLWE-hiding and MSIS-binding at this \(\gamma\) is left to the full version.

8 Comparison with Liu-Susilo-Baek↩︎

This section collects, in one place, every comparison with the discrete-logarithm construction of Liu, Susilo and Baek [4]: the structural reason a literal port fails (Section 8.1), the definition- and theorem-level correspondence with our security model (Section 8.2, Table 1), and the algorithm-by-algorithm differences of the construction (Section 8.3). The definitional refinements themselves are stated where the definitions are introduced (Section 4.1); here we assemble the full picture and justify each divergence against a single structural fact, the absence, over lattices, of a free re-randomisation of a shared value.

8.1 The structural obstruction↩︎

Liu, Susilo and Baek realise extended withdrawability from a discrete-logarithm one-out-of-\(N\) signature in which re-randomising the signer’s contribution across the ring is essentially free: one group element serves ambiguity and confirmation. The lattice setting has no such free re-randomisation. Transporting a signer-derived shift in the clear (as an earlier draft did, publishing \(\{A\mathbf{s}_1 s_j\}_j\)) exposes \(A\mathbf{s}_1\approx\mathbf{t}_{\mathsf{signer}}\), since \(\mathbf{t}_i-A\mathbf{s}_1=\mathbf{s}_2\) is short only for the true signer, and breaks ambiguity, the same structural obstruction met in the designated-verifier setting. We therefore separate the two roles: ambiguity is a genuine lattice one-out-of-\(N\) proof, and confirmation is a claim, a binding signature plus the opening of a hiding index commitment bound into the transcript. This is exactly a claimable ring signature [15], [16], a primitive the related-work literature already identifies with withdrawable signatures. The cost is one commitment and its opening per signature; the gain is that no signer-identifying value is ever published, so ambiguity reduces cleanly to MLWE (hiding) plus the zero-knowledge of the one-out-of-\(N\) proof, and confirmation soundness to MSIS-binding plus the base scheme’s EUF-CMA.

8.2 Correspondence with the Liu-Susilo-Baek security model↩︎

Table 1 sets each notion of our model against its counterpart in [4]; the per-notion justifications are given in Section 4.1, where each definition is introduced. The two rows that carry genuine security content, rather than a change of algebraic setting, are extended withdrawability (a hiding game in place of a completeness statement) and claimability soundness (a new notion with no counterpart in [4]); the unforgeability row records a strictly tighter reduction (no multiplicative \(q_H\) loss).

8.3 Construction, algorithm by algorithm↩︎

We now compare the seven algorithms of Section 5 with their discrete-logarithm originals. The first three items contrast the signing-side algorithms directly; the last collects the same three contrasts against a literal lattice transcription of [4], making explicit which defect each of our design choices repairs.

8.3.0.1 Key generation vs.their \(g^{sk}\).

Their key generation draws \(sk\mathrel{\overset{\$}{\leftarrow}}\mathbb{Z}_p\) and sets \(pk=g^{sk}\); ours is the module-lattice analogue, with \(sk=(\mathbf{s}_1,\mathbf{s}_2)\) short and \(pk=A\mathbf{s}_1+\mathbf{s}_2\). They require no \(\mathop{\mathrm{\mathsf{Setup}}}\) because the group \(G\) and generator \(g\) are global objects; the lattice setting has no canonical counterpart, so the common \(A\) must be produced by \(\mathop{\mathrm{\mathsf{Setup}}}\) and shared, precisely the amendment missing from a literal transcription (Section 8).

8.3.0.2 Withdrawable signing vs.their published shifts.

Their \(\mathop{\mathrm{\mathsf{WSign}}}\) re-randomises every ring key by a shift, forming \(\gamma'=\{pk_j g^{s_j}\}_j\), signs \(\gamma'\) with a shifted witness \(\widetilde{sk}=sk_i+r\), and publishes the shifts \(\sigma_2=\{g^{s_j}\}_j\) so the verifier can rebuild \(\gamma'\); the shift exists solely to enable the linked confirmation. We keep the ring \(\pi\) and the witness \(sk_i\) unchanged and introduce a committed index instead. The reason is structural: over a prime-order group the published shifts \(\{g^{s_j}\}\) are uniform and independent of the secret, hence harmless, whereas their literal lattice analogue \(\{A\mathbf{s}_1 s_j\}\) shares the common factor \(A\mathbf{s}_1\approx\mathbf{t}_i\) and thereby reveals the signer (Section 8). Replacing the shift by a hiding commitment removes the leak while preserving the one function the shift served, carrying, into \(\sigma\), a signer-chosen value that confirmation can later open.

8.3.0.3 Confirmation vs.their ephemeral-key claim.

Their confirmation re-derives the shared randomness \(r=H(\gamma,g^{sk_i\sum_j s_j})\) and outputs \(\delta_1=\mathop{\mathrm{\mathsf{Sign}}}(\{m,\sigma\},r)\) (a signature under the ephemeral key \(g^r\)), \(\delta_2=\mathop{\mathrm{\mathsf{Sign}}}(m,sk_i)\) (under the real key), and \(\delta_3=g^r\); their \(\mathop{\mathrm{\mathsf{Check}}}\) then verifies \(g^r=g^{s_i}\) against the value embedded in \(\sigma_2\) and \(\delta_1\) under \(g^r\). Our single signature \(\delta_s\) on \(\langle \mu,\pi,\sigma \rangle\) plays the role of both their \(\delta_2\) (it binds the real key \(pk_i\)) and their \(\delta_1\) (it binds the object \(\sigma\)), while the commitment \(C\) plays the role of the embedded \(g^r\): the signer-chosen value fixed inside \(\sigma\) at signing time that \(\mathop{\mathrm{\mathsf{Check}}}\) re-derives and matches at confirmation. The commitment is the lattice analogue of \(g^r\), with one strict improvement, it hides the index on its own, whereas \(g^{s_i}\) hides only in combination with the ambiguity of \(\sigma_1\). This is why our \(\mathop{\mathrm{\mathsf{Confirm}}}\) needs one base signature plus one opening, in place of two signatures and an embedded group element.

8.4 Algorithm-level relation to a direct lattice transcription↩︎

The construction above is most sharply understood as the correction of a direct lattice transcription of [4], which realises the seven algorithms over \(\mathcal{R}_q\) but ports the discrete-logarithm operations symbol for symbol. Each of that transcription’s signing-side algorithms is thereby defective, and our algorithms differ in exactly the places that repair them.

• Key generation: The transcription’s \(\mathop{\mathrm{\mathsf{KeyGen}}}\) samples a fresh \(A\mathrel{\overset{\$}{\leftarrow}}\mathcal{R}_q^{k\times l}\) inside each invocation, so distinct users hold distinct matrices and the ring identity \(A\mathbf{z}-\sum_j c_j\mathbf{t}_j\) is not defined across \(\pi\). Our \(\mathop{\mathrm{\mathsf{Setup}}}\) (Algorithm 2) fixes one common \(A\in\mathcal{R}_q^{k\times l}\) shared by all \(N\) users, making the ring statement well formed, the omission a group-based transcription cannot see, since \(g\in G\) is global by fiat.

• Withdrawable signing: The transcription’s \(\mathop{\mathrm{\mathsf{WSign}}}\) shifts each ring key by \(A\mathbf{s}_1 s_j\), publishes the shifts \(\sigma_2=\{A\mathbf{s}_1 s_j\}_j\) so the verifier can rebuild the shifted ring, and signs that ring with the shifted witness \(\widetilde{sk}=((1+r)\mathbf{s}_1,\mathbf{s}_2)\), where \(r=s_i\in B_\tau\). Both steps are unsound over lattices. First, the published shifts share the common factor \(A\mathbf{s}_1=\mathbf{t}_i-\mathbf{s}_2\approx\mathbf{t}_i\), which is short-distance from the signer’s key \(\mathbf{t}_i\) but from no other \(\mathbf{t}_j\); publishing them therefore identifies the signer and destroys ambiguity. Second, \((1+r)\mathbf{s}_1\) is no longer short: for \(r\in B_\tau\) one has \(\lVert(1+r)\mathbf{s}_1\rVert_\infty\le(1+\tau)\lVert\mathbf{s}_1\rVert_\infty\), so the shifted witness violates the norm bound that \(\mathop{\mathrm{\mathsf{ASign}}}\)’s rejection sampling presumes (and on which its zero-knowledge rests). Our \(\mathop{\mathrm{\mathsf{WSign}}}\) (Algorithm 3) publishes no shift, leaves the witness \(sk_i\) and the ring \(\pi\) unchanged, and carries the signer-chosen value in the hiding commitment \(C\) instead.

• Confirmation: The transcription’s \(\mathop{\mathrm{\mathsf{Confirm}}}\) sets \(\aleph=\sigma_2\setminus\{A\mathbf{s}_1 s_i\}\) and re-derives \(r=H\bigl(\pi,\mathop{\mathrm{\mathsf{HighBits}}}(\sum_{j\ne i}A\mathbf{s}_1 s_j+\mathbf{s}_2,2\gamma_2)\bigr)\); but recovering \(A\mathbf{s}_1 s_i\) presupposes \(s_i=r\), whose derivation needs \(\aleph\), a circular dependency, well defined only if \(\sigma_2\) is index-ordered or the per-signature randomness is stored. It then uses \(\delta_3=A(1+r)\mathbf{s}_1+\mathbf{s}_2\) as an on-the-fly public key against which one of the confirmed components is verified. Our \(\mathop{\mathrm{\mathsf{Confirm}}}\) (Algorithm 4) is stateless and non-circular: the signer signs \(\langle \mu,\pi,\sigma \rangle\) under its real key \(sk_i\) and opens the commitment it stored at signing, with no shift to recover and no ephemeral key to synthesise.

In one sentence: the transcription fails because it treats the group re-randomisation \(g^{s_j}\) as though it had a free lattice analogue; the present construction removes the re-randomisation altogether and recovers traceability from a committed index. The single structural cause behind all three defects, the absence of a cheap lattice shared secret, is analysed in Section 8.

9 Conclusion↩︎

We have given a lattice realisation of extended withdrawable signatures over the Fiat-Shamir with aborts paradigm. The central move is a change of viewpoint: rather than porting the discrete-logarithm construction of Liu, Susilo and Baek [4] operation by operation, which, as we prove, cannot be done securely (Proposition 1), we recognise the extended withdrawable signature as a claimable ring signature in the sense of Park and Sealfon [15], the very abstraction that [4] single out as an instantiation of their primitive. This reframing separates the two responsibilities of the object and assigns each to a component with an established analysis: signer ambiguity is carried by an anonymous one-out-of-\(N\) proof used as a black box, and confirmation is a signer’s claim, a binding base signature on the whole withdrawable object together with the opening of a hiding index commitment bound into the transcript. No signer-derived value is ever published in the clear, which is precisely what a literal transcription fails to achieve.

9.0.0.1 What we proved.

Within a security model that sharpens [4] in two respects, extended withdrawability is recast from a completeness statement into an anonymity-until-claim indistinguishability game (Definition 14), and claimability soundness is added as an explicit notion (Definition 16), we gave complete, fully explicit game-based reductions for all four properties in the (quantum) random-oracle model. Correctness (Theorem 2) follows modularly from the correctness of the ingredients. Extended withdrawability (Theorem 3) reduces, through a three-game sequence, to commitment hiding (hence decisional MLWE) and the anonymity of the one-out-of-\(N\) layer. Unforgeability under insider corruption (Theorem 4) reduces to the plain EUF-CMA security of the base signature, with a clean forgery extraction and, unlike [4], no rewinding and no multiplicative \(q_H\) loss, the only overheads being the factor \(N\) from guessing the target and an additive \(q_W\mathsf{Adv}^{\mathsf{anon}}_{\mathop{\mathrm{\mathsf{Ambi}}}}\) term. Claimability soundness (Proposition 5) reduces directly to commitment binding (hence MSIS). Along the way, Proposition 1 isolates a lattice-specific impossibility with no counterpart in the discrete-logarithm setting: the additive challenge-split that makes their one-out-of-\(N\) signature work is complete only with negligible probability once challenges are confined to the sparse set \(B_\tau\), and anonymity fails even if completeness is forced.

9.0.0.2 Significance.

The construction is publicly verifiable, ambiguous until claimed, and post-quantum: its security rests entirely on module-lattice assumptions (MLWE, MSIS, SelfTargetMSIS) and the unforgeability of a standardised-style base signature, so it retains its guarantees against a quantum adversary, exactly the durability that long-lived commitments in decentralised systems require, and that the discrete-logarithm foundation of [4] lacks. Because ambiguity, binding and the base signature are invoked only through their stated interfaces, the result is also modular: any anonymous one-out-of-\(N\) proof, any hiding-and-binding commitment, and any EUF-CMA base signature meeting the interfaces of Section 5 may be substituted without reopening the proofs. Instantiated with a no-hint, full-\(t\) Dilithium-style base and an established logarithmic-size lattice one-out-of-many proof (Section 7), the scheme is concretely realisable, and the design is faithful to the primitive, the security goals, and the stated intuition of [4].

9.0.0.3 Future work.

Several directions remain. First, a fully concrete instantiation: pinning down a logarithmic-size one-out-of-\(N\) proof [13], [14] with explicit parameters and giving a single parameter set that simultaneously meets base-signature EUF-CMA, one-out-of-\(N\) zero-knowledge, MLWE-hiding and MSIS-binding at the extracted norm \(\gamma\) of Proposition 5, the quantitative gap flagged in Section 7. Second, a rigorous HAETAE [11] base: verifying that its bimodal-Gaussian rejection meets the same EUF-CMA interface would yield shorter signatures at no cost to the surrounding analysis. Third, tightening the reductions: both the factor \(N\) from target-guessing in Theorem 4 and the factor \(2\) relating the guessing and distinguishing forms of the anonymity advantage (Definition 10) are artefacts of the current arguments, and it is natural to ask whether either can be removed. Fourth, functionality extensions that the modular structure should accommodate cleanly: blind withdrawable signing, threshold or multi-signer confirmation, and revocation or time-bounded confirmation windows. Finally, a treatment of concurrent confirmation and an analysis in the plain model (without random oracles) for the ambiguity layer would further strengthen the guarantees.

References↩︎