Lattice-based extended withdrawability

Technical Summary: Lattice-based Extended Withdrawability

Problem Statement
Digital signatures traditionally provide permanence: once signed, a message remains verifiable under the signer's public key indefinitely. However, many decentralized applications (e.g., limited-time access, revocable agreements, decentralized escrow) require the ability to withdraw a signature without revealing the secret key or invalidating other signatures. Liu, Susilo, and Baek introduced extended withdrawable signatures (EWS) to address this, allowing a signature to be ambiguous among a set of potential signers until the true signer "confirms" it. Their construction relies on discrete-logarithm primitives (Schnorr signatures and 1-out-of-N signatures).

This paper addresses the "post-quantum gap": Shor's algorithm breaks the discrete-logarithm foundation of existing EWS schemes. While lattice-based signatures (e.g., Dilithium) exist, a direct "literal transcription" of the Liu-Susilo-Baek (LSB) construction to lattices fails due to structural obstructions. Specifically, the LSB scheme relies on publishing multiplicative shifts of public keys to re-randomize the signer's contribution. In the lattice setting (Fiat-Shamir with aborts), such shifts take the form $As_1 s_j$, which share a common factor $As_1$ with the signer's public key $t_i = As_1 + s_2$. Publishing these shifts leaks the signer's identity, breaking the required ambiguity.

Methodology
The authors propose a new construction for lattice-based EWS that departs from the LSB approach by treating the scheme as a claimable ring signature (Park and Sealfon). Instead of attempting to re-randomize public keys in the clear, the construction separates the two core functions of EWS:

1. Ambiguity: Provided by an anonymous 1-out-of-N (ring) signature, used as a black box.
2. Confirmation: Provided by the signer's claim, consisting of a binding signature on the withdrawable object and the opening of a hiding commitment to the signer's index.

The construction operates over the Fiat-Shamir with aborts paradigm and relies on three modular ingredients:

• A base signature scheme (e.g., a no-hint, full-$t$ Dilithium-style scheme).
• An anonymous 1-out-of-N signature (instantiated via a lattice one-out-of-many proof).
• A hiding-and-binding commitment scheme (Ajtai-style).

The withdrawable signature $\sigma$ consists of a ring signature $\sigma_r$ on the message and a commitment $C$ to the signer's index, along with the set of public keys. To confirm, the signer reveals the opening $(i, \rho)$ of $C$ and signs the entire withdrawable object $\langle \mu, \pi, \sigma \rangle$ with their base secret key.

Key Contributions

1. Security Model Refinement: The authors refine the security model of LSB.

   • They replace the LSB "completeness" definition of extended withdrawability with an anonymity-until-claim indistinguishability game (Definition 14), explicitly capturing the hiding guarantee.
   • They introduce claimability soundness (Definition 16), ensuring that a confirmed signature binds to a unique signer index, preventing an adversary from attributing the same signature to different ring members.
   • They formalize unforgeability under insider corruption with a fixed target index, avoiding the multiplicative $q_H$ (hash query) reduction loss present in the LSB proof.

2. Generic Construction: A generic construction of EWS over the Fiat-Shamir with aborts paradigm is presented. Crucially, it publishes no signer-derived value in the clear. Ambiguity is derived solely from the ring signature's zero-knowledge properties, and traceability is derived from the binding property of the commitment.

3. Impossibility Result: The paper proves (Proposition 2) that a literal lattice transcription of the LSB 1-out-of-N signature (using additive challenge splitting) is insecure. In the lattice setting with sparse challenges, the probability of an honest signer producing a valid challenge split is negligible ($2^{-\Omega(n)}$), and even if completeness were patched, anonymity would fail because the simulated transcript would not be indistinguishable from a real one.

4. Complete Security Proofs: The authors provide explicit game-based reductions in the (Quantum) Random Oracle Model (QROM) for:

   • Correctness: Reducing to the correctness of the underlying primitives.
   • Extended Withdrawability: Reducing to the hiding of the commitment (Decisional MLWE) and the anonymity of the 1-out-of-N scheme.
   • Unforgeability: Reducing to the EUF-CMA security of the base signature (with no rewinding and no $q_H$ loss).
   • Claimability Soundness: Reducing to the binding of the commitment (MSIS).

5. Instantiation: The scheme is instantiated using a no-hint, full-$t$ Dilithium-style base signature and an established lattice one-out-of-many proof. The paper discusses parameter choices and notes that HAETAE could serve as an alternative base.

Results
The paper establishes that the proposed construction is:

• Correct: Honest signatures verify with overwhelming probability.
• Extended Withdrawable: An adversary holding all secret keys cannot distinguish which member of a ring produced a withdrawable signature until the signer confirms it.
• Unforgeable: Even with access to signing oracles and the secret keys of all ring members except the target, an adversary cannot forge a confirmed signature for a fresh message.
• Sound: A confirmed signature cannot be attributed to two different signers.

The security relies on standard module-lattice assumptions: Decisional MLWE, MSIS, and SelfTargetMSIS, alongside the zero-knowledge property of the 1-out-of-N proof.

Significance
The paper claims significance by providing the first secure, post-quantum realization of extended withdrawable signatures. It demonstrates that the discrete-logarithm construction of LSB cannot be directly ported to lattices due to the lack of "free re-randomization" of shared values. By reframing the problem as a claimable ring signature and utilizing a commitment-based confirmation mechanism, the authors achieve a scheme that is:

• Post-Quantum Secure: Resistant to quantum adversaries via lattice assumptions.
• Publicly Verifiable: Unlike designated-verifier variants, any party can verify the withdrawable signature.
• Modular: The security proofs rely only on the interfaces of the underlying primitives, allowing for substitution of different lattice-based components (e.g., different base signatures or ring proofs) without re-proving the entire system.
• Faithful to Original Goals: The design preserves the functional goals and intuition of the original LSB scheme while correcting its structural flaws in the lattice setting.