Kipnis-Shamir attack on HFE revisited

Xin Jiang; Jintai Ding; Lei Hu

doi:10.1007/978-3-540-79499-8_31

Kipnis-Shamir attack on HFE revisited

Xin Jiang^*, Jintai Ding, Lei Hu

^*Corresponding author for this work

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

14 Citations (Scopus)

Abstract

In this paper, we show the claims in the original Kipnis-Shamir 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 ₄, the Kipnis-Shamir attack still should be exponential but not polynomial. This again is supported by our theoretical argument.

Original language	English
Title of host publication	Information Security and Cryptology - Third SKLOIS Conference, Inscrypt 2007, Revised Selected Papers
Pages	399-411
Number of pages	13
DOIs	https://doi.org/10.1007/978-3-540-79499-8_31
Publication status	Published - 2008
Externally published	Yes
Event	3rd SKLOIS Conference on Information Security and Cryptology, Inscrypt 2007 - Xining, China Duration: 31 Aug 2007 → 5 Sept 2007

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4990 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	3rd SKLOIS Conference on Information Security and Cryptology, Inscrypt 2007
Country/Territory	China
City	Xining
Period	31/08/07 → 5/09/07

Keywords

Gröbner basis
HFE
MinRank
Multivariate public key cryptosystem
Relinearization
XL algorithm

Access to Document

10.1007/978-3-540-79499-8_31

Cite this

Jiang, X., Ding, J., & Hu, L. (2008). Kipnis-Shamir attack on HFE revisited. In Information Security and Cryptology - Third SKLOIS Conference, Inscrypt 2007, Revised Selected Papers (pp. 399-411). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4990 LNCS). https://doi.org/10.1007/978-3-540-79499-8_31

@inproceedings{849a9219c42047278d16a72e53d562b7,

title = "Kipnis-Shamir attack on HFE revisited",

abstract = "In this paper, we show the claims in the original Kipnis-Shamir 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{\"o}bner basis algorithm like F 4, the Kipnis-Shamir attack still should be exponential but not polynomial. This again is supported by our theoretical argument.",

keywords = "Gr{\"o}bner basis, HFE, MinRank, Multivariate public key cryptosystem, Relinearization, XL algorithm",

author = "Xin Jiang and Jintai Ding and Lei Hu",

year = "2008",

doi = "10.1007/978-3-540-79499-8_31",

language = "English",

isbn = "3540794980",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "399--411",

booktitle = "Information Security and Cryptology - Third SKLOIS Conference, Inscrypt 2007, Revised Selected Papers",

note = "3rd SKLOIS Conference on Information Security and Cryptology, Inscrypt 2007 ; Conference date: 31-08-2007 Through 05-09-2007",

}

Jiang, X, Ding, J & Hu, L 2008, Kipnis-Shamir attack on HFE revisited. in Information Security and Cryptology - Third SKLOIS Conference, Inscrypt 2007, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4990 LNCS, pp. 399-411, 3rd SKLOIS Conference on Information Security and Cryptology, Inscrypt 2007, Xining, China, 31/08/07. https://doi.org/10.1007/978-3-540-79499-8_31

Kipnis-Shamir attack on HFE revisited. / Jiang, Xin; Ding, Jintai; Hu, Lei.
Information Security and Cryptology - Third SKLOIS Conference, Inscrypt 2007, Revised Selected Papers. 2008. p. 399-411 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4990 LNCS).

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

TY - GEN

T1 - Kipnis-Shamir attack on HFE revisited

AU - Jiang, Xin

AU - Ding, Jintai

AU - Hu, Lei

PY - 2008

Y1 - 2008

N2 - In this paper, we show the claims in the original Kipnis-Shamir 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 attack still should be exponential but not polynomial. This again is supported by our theoretical argument.

AB - In this paper, we show the claims in the original Kipnis-Shamir 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 attack still should be exponential but not polynomial. This again is supported by our theoretical argument.

KW - Gröbner basis

KW - HFE

KW - MinRank

KW - Multivariate public key cryptosystem

KW - Relinearization

KW - XL algorithm

UR - http://www.scopus.com/inward/record.url?scp=54249088990&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-79499-8_31

DO - 10.1007/978-3-540-79499-8_31

M3 - Conference Proceeding

AN - SCOPUS:54249088990

SN - 3540794980

SN - 9783540794981

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 399

EP - 411

BT - Information Security and Cryptology - Third SKLOIS Conference, Inscrypt 2007, Revised Selected Papers

T2 - 3rd SKLOIS Conference on Information Security and Cryptology, Inscrypt 2007

Y2 - 31 August 2007 through 5 September 2007

ER -

Kipnis-Shamir attack on HFE revisited

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this