Paper 2026/928

Wombat: Post-Quantum Blind Signature from Standard Group Action Assumptions and More

Abstract

A recent work by Hanzlik et al.~(Asiacrypt'25) introduced Tanuki, a family of blind-signature frameworks based on non-commutative cryptographic group actions. Tanuki develops new techniques to obtain concurrently secure blind signatures, and admits compact instantiations in two distinct regimes: (i) an isogeny-based instantiation from the CSI-FiSh group action with signatures of about 4.5 KB, and (ii) a code-based instantiation from LESS and the code-equivalence group action with signatures around 64 KB. To the best of our knowledge, these are the first efficient blind-signature constructions in the isogeny- and code-based settings that support concurrent executions. Despite this advance, the Tanuki frameworks rely on a non-standard and interactive assumption, namely the so-called ``one more'' vectorization assumption. Given several structural attacks and vulnerabilities discovered in various group action instantiations, relying on non-standard assumptions can raise concerns. In this work we present a new framework building upon Tanuki's techniques that achieves concurrent security while achieving better performance, and relying only on the standard group action hardness assumption, the vectorization problem (also known as the group action inversion problem). For the LESS instantiation, we apply dedicated code-based techniques to reduce signature sizes by a factor of 14.5. These improvements come with rigorous reductions to the standard problem, do not weaken the security claims, and are directly applicable to the LESS instantiations of Tanuki. As a result, our isogeny-based and code-based instantiations yield signature sizes of 8.89 and 8.84 KB, respectively, and retain concurrent security under the standard group-action inversion assumption.