| Luk Bettale |  |
 |
Date de l'exposé : 10 février 2012
Cryptanalysis of HFE, Multi-HFE and Variants for Odd and Even Characteristic
In this talk, we present a key recovery attack on a family of multivariate public key schemes, namely HFE and Multi-HFE, as well as several classical variants for odd and even characteristic. We recall the general principle of multivariate public key schemes. It uses the NP-hardness of the so-called Polynomial System Solving problem (PoSSo).Among multivariate public key schemes, Hidden Field Equations (HFE) is one of the most studied. We present in this talk an attack that improves and generalizes the key recovery attack of Kipnis and Shamir (KS) on HFE. To do so, we express this attack as matrix/vector operations. In one hand, this permits to improve the attack on HFE. In the other hand, this allows to generalize the attack on Multi-HFE. Due to its structure, we prove that a Multi-HFE scheme has much more equivalent keys than a basic HFE. This induces a structural weakness which can be exploited to adapt the KS attack against classical modifiers of multivariate schemes such as minus and embedding. Along the way, we discovered that the KS attack as initially described cannot be applied against HFE in characteristic 2. We revised our attack to make it working for any characteristic. In all cases, the cost of our attacks is related to the complexity of solving the MinRank problem. Thanks to recent complexity analysis on this problem, we prove that our attack is polynomial in the degree of the extension field for all practical settings used in HFE and Multi-HFE. This makes Multi-HFE less secure than basic HFE for equally sized keys. As a proof of concept, we have been able to practically break the most conservative parameters proposed for Multi-HFE in few days (256 bits security broken in 9 days).
This is a joint work with Jean-Charles Faugère and Ludovic Perret.
