Inverting HFE systems is quasi-polynomial for all fields

Jintai Ding; Timothy J. Hodges

doi:10.1007/978-3-642-22792-9_41

Inverting HFE systems is quasi-polynomial for all fields

Jintai Ding^*, Timothy J. Hodges

^*Corresponding author for this work

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

48 Citations (Scopus)

Abstract

In this paper, we present and prove the first closed formula bounding the degree of regularity of an HFE system over an arbitrary finite field. Though these bounds are not necessarily optimal, they can be used to deduce 1. if D, the degree of the corresponding HFE polynomial, and q, the size of the corresponding finite field, are fixed, inverting HFE system is polynomial for all fields; 2. if D is of the scale O(n^α) where n is the number of variables in an HFE system, and q is fixed, inverting HFE systems is quasi-polynomial for all fields. We generalize and prove rigorously similar results by Granboulan, Joux and Stern in the case when q = 2 that were communicated at Crypto 2006.

Original language	English
Title of host publication	Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Proceedings
Publisher	Springer Verlag
Pages	724-742
Number of pages	19
ISBN (Print)	9783642227912
DOIs	https://doi.org/10.1007/978-3-642-22792-9_41
Publication status	Published - 2011
Externally published	Yes
Event	31st Annual International Cryptology Conference, CRYPTO 2011 - Santa Barbara, United States Duration: 14 Aug 2011 → 18 Aug 2011

Publication series

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

Conference

Conference	31st Annual International Cryptology Conference, CRYPTO 2011
Country/Territory	United States
City	Santa Barbara
Period	14/08/11 → 18/08/11

Access to Document

10.1007/978-3-642-22792-9_41

Cite this

Ding, J., & Hodges, T. J. (2011). Inverting HFE systems is quasi-polynomial for all fields. In Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Proceedings (pp. 724-742). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6841 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-642-22792-9_41

@inproceedings{e1aafe75964a419b90c15a8caf84fca0,

title = "Inverting HFE systems is quasi-polynomial for all fields",

abstract = "In this paper, we present and prove the first closed formula bounding the degree of regularity of an HFE system over an arbitrary finite field. Though these bounds are not necessarily optimal, they can be used to deduce 1. if D, the degree of the corresponding HFE polynomial, and q, the size of the corresponding finite field, are fixed, inverting HFE system is polynomial for all fields; 2. if D is of the scale O(nα) where n is the number of variables in an HFE system, and q is fixed, inverting HFE systems is quasi-polynomial for all fields. We generalize and prove rigorously similar results by Granboulan, Joux and Stern in the case when q = 2 that were communicated at Crypto 2006.",

author = "Jintai Ding and Hodges, {Timothy J.}",

year = "2011",

doi = "10.1007/978-3-642-22792-9_41",

language = "English",

isbn = "9783642227912",

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

publisher = "Springer Verlag",

pages = "724--742",

booktitle = "Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Proceedings",

note = "31st Annual International Cryptology Conference, CRYPTO 2011 ; Conference date: 14-08-2011 Through 18-08-2011",

}

Ding, J & Hodges, TJ 2011, Inverting HFE systems is quasi-polynomial for all fields. in Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6841 LNCS, Springer Verlag, pp. 724-742, 31st Annual International Cryptology Conference, CRYPTO 2011, Santa Barbara, United States, 14/08/11. https://doi.org/10.1007/978-3-642-22792-9_41

Inverting HFE systems is quasi-polynomial for all fields. / Ding, Jintai; Hodges, Timothy J.
Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Proceedings. Springer Verlag, 2011. p. 724-742 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6841 LNCS).

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

TY - GEN

T1 - Inverting HFE systems is quasi-polynomial for all fields

AU - Ding, Jintai

AU - Hodges, Timothy J.

PY - 2011

Y1 - 2011

N2 - In this paper, we present and prove the first closed formula bounding the degree of regularity of an HFE system over an arbitrary finite field. Though these bounds are not necessarily optimal, they can be used to deduce 1. if D, the degree of the corresponding HFE polynomial, and q, the size of the corresponding finite field, are fixed, inverting HFE system is polynomial for all fields; 2. if D is of the scale O(nα) where n is the number of variables in an HFE system, and q is fixed, inverting HFE systems is quasi-polynomial for all fields. We generalize and prove rigorously similar results by Granboulan, Joux and Stern in the case when q = 2 that were communicated at Crypto 2006.

AB - In this paper, we present and prove the first closed formula bounding the degree of regularity of an HFE system over an arbitrary finite field. Though these bounds are not necessarily optimal, they can be used to deduce 1. if D, the degree of the corresponding HFE polynomial, and q, the size of the corresponding finite field, are fixed, inverting HFE system is polynomial for all fields; 2. if D is of the scale O(nα) where n is the number of variables in an HFE system, and q is fixed, inverting HFE systems is quasi-polynomial for all fields. We generalize and prove rigorously similar results by Granboulan, Joux and Stern in the case when q = 2 that were communicated at Crypto 2006.

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

U2 - 10.1007/978-3-642-22792-9_41

DO - 10.1007/978-3-642-22792-9_41

M3 - Conference Proceeding

AN - SCOPUS:80051965157

SN - 9783642227912

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

SP - 724

EP - 742

BT - Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Proceedings

PB - Springer Verlag

T2 - 31st Annual International Cryptology Conference, CRYPTO 2011

Y2 - 14 August 2011 through 18 August 2011

ER -

Ding J, Hodges TJ. Inverting HFE systems is quasi-polynomial for all fields. In Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Proceedings. Springer Verlag. 2011. p. 724-742. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-22792-9_41

Inverting HFE systems is quasi-polynomial for all fields

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this