Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleAlgebraic decoder of multidimensional convolutional code: Constructive algorithms for determining syndrome decoder and decoder matrix based on Gr\"obner basis.
Author(s) Chalie Charoenlarpnopparut, P. Jangisarakul
TypeArticle in Journal
AbstractWe investigate the security of a generalization of HFE (multivariate and odd-characteristic variants). First, we propose an improved version of the basic Kipnis-Shamir key recovery attack against HFE. Second, we generalize the Kipnis-Shamir attack to Multi-HFE. The attack reduces to solve a MinRank problem directly on the public key. This leads to an improvement of a factor corresponding to the square of the degree of the extension field. We used recent results on MinRank to show that our attack is polynomial in the degree of the extension field. It appears that multi-HFE is less secure than original HFE for equal-sized keys. Finally, adaptations of our attack overcome several variants (i.e. minus modifier and embedding). As a proof of concept, we have practically broken the most conservative parameters given by Chen, Chen, Ding, Werner and Yang in 9 days for 256 bits security. All in all, our results give a more precise picture on the (in)security of several variants of HFE proposed these last years.
KeywordsHidden Field Equations, MinRank, Gröbner bases
ISSN0923-6082; 1573-0824/e
URL http://link.springer.com/chapter/10.1007%2F978-3-642-19379-8_27
JournalMultidimensional Syst. Signal Process.
PublisherSpringer US, New York, NY
Translation No
Refereed No