Efficient key recovery attack breaks Miranda signature scheme parameters
How to break the Miranda signature scheme over matrix Gabidulin codes
Cryptography and Security
Summary
The Miranda signature scheme is meant to keep digital signatures secure by hiding a special structure in a type of code. The authors show a way to uncover this hidden structure using a mathematical technique called MinRank, which lets them crack the secret keys much faster than expected. This means the security level claimed by Miranda for certain parameters is much weaker in practice. Their method reduces the difficulty from very high to much lower, making it easier to break.
What this means in practice
- •For cryptography engineers: Identify insecure parameter sets in matrix Gabidulin code-based signature schemes before deployment.
- •For security auditors: Assess the vulnerability of deployed Miranda signature-based systems to key recovery attacks efficiently.
Authors
Adrien Vinçotte
Abstract
The Miranda signature scheme relies on masking a matrix code which disposes of a masked underlying structure, and the knowledge of which allows for efficient error decoding. We consider a Gabidulin code which is expanded into a matrix code, that is only \Fq-linear. An additional masking is then applied to it. The attack proposed here shares similarities with that of [Le26, https://arxiv.org/abs/2608.03328] on the EGMC encryption scheme, which also follows the paradigm described above. It consists in recovering the Fqm-linear structure of a masked matrix Gabidulin code by reducing to a MinRank instance to be solved over the extension field Fqm, but where the matrices have coefficients in Fq. Such an instance can be efficiently solved. However, unlike the previous attack, it is possible to reduce in polynomial time to such a MinRank instance in the case of the Miranda signature scheme. This results in a particularly efficient key recovery attack against the parameters proposed for Miranda. For example, for the proposed parameter set with m=79, the complexity drops from 146 bits to 46 bits in this attack.