On the (In)security of optimized Stern-like signature schemes

Stern's signature scheme is a historically important code-based signature scheme. A crucial optimization of this scheme is to generate pseudo-random vectors and a permutation instead of random ones, and most proposals that are based on Stern's signature use this optimization. However, its security has not been properly analyzed, especially when we use deterministic commitments. In this article, we study the security of this optimization. We first show that for some parameters, there is an attack that exploits this optimization and breaks the scheme in time $O(2^{\fracλ{2}})$ while the claimed security is $λ$ bits. This impacts in particular the recent Quasy-cyclic Stern signature scheme [BGMS22]. Our second result shows that there is an efficient fix to this attack. By adding a string $salt \in \{0,1\}^{2λ}$ to the scheme, and changing slightly how the pseudo-random strings are generated, we prove not only that our attack doesn't work but that for any attack, the scheme preserves $λ$ bits of security, and this fix increases the total signature size by only $2λ$ bits. We apply this construction to other optimizations on Stern's signature scheme, such as the use of Lee's metric or the use of hash trees, and we show how these optimizations improve the signature length of Stern's signature scheme.