Paper 2025/274

Post-Quantum Blind Signatures from Matrix Code Equivalence

Abstract

We construct a novel code-based blind signature scheme, us- ing the Matrix Equivalence Digital Signature (MEDS) group action. The scheme is built using similar ideas to the Schnorr blind signature scheme and CSI-Otter, but uses additional public key and commitment informa- tion to overcome the difficulties that the MEDS group action faces: lack of module structure (present in Schnorr), lack of a quadratic twist (present in CSI-Otter), and non-commutativity of the acting group. We address security concerns related to public key validation, and prove the security of our protocol in the random oracle model, using the security framework of Kastner, Loss, and Xu, under a variant of the Inverse Matrix Code Equivalence problem and a mild heuristic assumption.

Note: Duong et al. (https://eprint.iacr.org/2025/397) claim that our construction, which is based on MIMCE, may be vulnerable to an attack due to the prior cryptanalysis of the original IMCE problem by Budroni et al. [BCDDK24] (https://eprint.iacr.org/2024/244). However, Budroni et al. do not attack the IMCE problem; rather, their attack immediately breaks the (unrelated) ILCE problem, and a variant of IMCE in which many samples are required. We did not mention this attack because it does not affect our construction, since only one (M)IMCE sample is provided to the adversary in our protocol, meaning that our protocol is not susceptible to the attack and hence still secure.