Cryptanalysis of the SHMW signature scheme

Area of Science:

• Cryptography
• Information Security
• Computer Science

Background:

• Durandal and SHMW are signature schemes based on rank metrics.
• SHMW was proposed as an enhancement to Durandal with smaller keys and signatures.
• Both schemes aim to conceal secret keys by manipulating vector subspaces and rely on hard-to-solve problems for security.

Purpose of the Study:

• To cryptanalyze the SHMW signature scheme and assess its security claims.
• To demonstrate the superiority of the original Durandal scheme over the SHMW enhancement.
• To introduce a novel method for identifying weak keys in rank-based signature schemes.

Main Methods:

• Exploiting extra information within signatures to compute an intersection space containing the secret key.
• Developing an algorithm to recover an extended support that includes the secret key.
• Applying the developed cryptanalytic approach to the SHMW signature scheme.

Main Results:

• The proposed method successfully recovers the secret key of the SHMW scheme with 97-bit computational complexity.
• This complexity is significantly lower than the claimed 128-bit security level.
• The security of the SHMW scheme was found to be inferior to the original Durandal scheme.

Conclusions:

• The SHMW signature scheme's security parameters are insufficient to meet the claimed 128-bit security level.
• The proposed cryptanalytic technique effectively undermines the security assumptions of the SHMW scheme.
• The original Durandal scheme offers a more robust security level compared to its SHMW enhancement.