Cryptanalysis of multivariate and odd-characteristic HFE variants

摘要: We investigate the security of a generalization HFE (multivariate and odd-characteristic variants). First, we propose an improved version basic Kipnis-Shamir key recovery attack against HFE. Second, generalize to Multi-HFE. The reduces solve MinRank problem directly on public key. This leads improvement factor corresponding square degree extension field. used recent results show that our is polynomial in It appears multi-HFE less secure than original for equal-sized keys. Finally, adaptations overcome several variants (i.e. minus modifier embedding). As proof concept, have practically broken most conservative parameters given by Chen, Ding, Werner Yang 9 days 256 bits security. All all, give more precise picture (in)security proposed these last years.