[Resource Topic] 2007/203: Kipnis-Shamir's Attack on HFE Revisited

Welcome to the resource topic for 2007/203

Kipnis-Shamir’s Attack on HFE Revisited

Authors: Xin Jiang, Jintai Ding, Lei Hu


In this paper, we show that the claims in the original Kipnis-Shamir’s attack on the HFE cryptosystems and the improved attack by Courtois that the complexity of the attacks is polynomial in terms of the number of variables are invalid. We present computer experiments and a theoretical argument using basic algebraic geometry to explain why it is so. Furthermore we show that even with the help of the powerful new Gröbner basis algorithm like F_4, the Kipnis-Shamir’s attack still should be exponential not polynomial. This again is supported by our theoretical argument.

ePrint: https://eprint.iacr.org/2007/203

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .