Paper 2025/1883

On the security of two blind signatures from code equivalence problems

Abstract

The Linear Code Equivalence (LCE) problem and the Matrix Code Equivalence (MCE) problem are two examples of code-based hard problems that have gained attention as candidates for use in post-quantum cryptography. They are straightforward to implement, can be viewed as group actions, and offer a good trade-off between compactness and performance in the realm of post-quantum group actions. With the community gaining confidence in the security of these problems, new variants of these problems have been introduced to achieve particular functionalities in advanced protocols or efficiency improvements. A natural question is then whether the problem variants are as secure as the original ones. In this work, we consider three problem variants of LCE or MCE. We first consider a variant based on LCE, and reduce it to the original LCE assumption. This problem was presented in a prior version of the blind signature scheme, proposed by Duong, Khuc, Qiao, Susilo and Zhang. Second, we analyse an MCE variant, MIMCE, proposed in the context of another blind signature scheme, by Kutcha, Legrow and Persichetti, and show that the parameters proposed are not sufficient to reach the claimed bit security. Finally, we consider a multi-sample version of MIMCE which we solve in polynomial time.

Note: We updated the "Our contributions" paragraph to explain the change of problem in eprint 2025/397 and give comparison between our work and that of eprint 2025/1909. We also updated the publication information, the proof of Lemma 1, and made a few small editorial changes.