Paper 2025/397

Blind Signatures from Cryptographic Group Actions

Abstract

We provide a generic construction of blind signatures from cryptographic group actions following the framework of the blind signature CSIOtter introduced by Katsumata et al. (CRYPTO'23) in the context of isogeny (commutative group action). We adapt and modify that framework to make it work even for non-commutative group actions. As a result, we obtain a blind signature from abstract group actions which are proven to be secure in the random oracle model. We also propose an instantiation based on a variant of linear code equivalence, interpreted as a symmetric group action.

Note: Update 2: On 2025-03-05, Lucjan Hanzlik (https://eprint.iacr.org/2025/425) provided an attack against the blindness of our scheme. We have fixed it to thwart Hanzlik's attack. We thank Lucjan Hanzlik for fruitful discussions. Update 1: On 2025-02-21, Kuchta, LeGrow and Persichetti ([KLP25]) proposed a construction of blind signatures from matrix code equivalence ( https://eprint.iacr.org/2025/274). The framework also follows that in CSI-Otter, with a focus on matrix code equivalence. To resolve issues caused by non-commutativity, the authors make use of the actions of both $A$ and its inverse transpose $A^{-T}$ for an invertible matrix $A$, and require $A$ to be (anti)symmetric. The security of the scheme relies on the hardness assumption of the Modified Inverse Matrix Code Equivalence Problem (MIMCE), a computational version of Inverse Matrix Code Equivalence Problem (IMCE). IMCE was recently attacked by Budroni et al. ([BCDSK24]) (Asiacrypt'24, https://eprint.iacr.org/2024/244), and this attack was not discussed in [KLP25]. In contrast, our framework is applicable for general (non-commutative) group actions. One requirement for instantiating our scheme is the reuse of secret keys, which leads us to propose the use of symmetric group action to equivalence classes of linear codes under the action of general linear group and diagonal group. This viewpoint helps to thwart the attack of reusing keys as in [BCDSK24].