Cryptanalysis of a rank-based signature with short public keys (Q2306903)

The {\em threat} of quantum computation has caused the search of new primitive for public-key encryption and cryptographic protocols. Recently \textit{Y. Song} et al. (SHMW) [Cryptology ePrint Archive, Report 2019/053, (2019)] proposed a digital signature scheme, with small keys, based on error-correcting codes (rank metric codes, in fact). Now the present paper gives a cryptanalysis of that scheme allowing to recover the secret key ``in about the same amount of time as required for signing.'' The SHMW scheme can be considered an adaptation to coding theory of the classical Schnorr signature [\textit{C. P. Schnorr}, Lect. Notes Comput. Sci. 435, 239--252 (1990; Zbl 0722.68050)]. The secret key is a couple of codewords \((x,y)\)\, and the public key a random codeword \(h\)\, and \(s=x+hy\). The rank of the signature must be small. But the present paper takes advantage of this condition to transform the signature into an efficiently solvable decoding problem and recover the secret key. Section 2 gathers the necessary concepts and tools of rank metric and codes with that metric. Section 3 recalls the Schnorr signature scheme and describes the SHMW scheme. Algorithms 1, 2 and 3 describes the key generation, the signature of a message and the signature verification. Table 1 gives the suggested parameters for 128, 192 and 256 security levels. Section 4 describes how to recover the support of the secret key \((x,y)\)\ (Algorithm 4) and finally the vectors \(x\)\, and \(y\). Table 2 gives the time comparison, for an implementation, of the SHMW signature and the proposed cryptanalysis.