Stronger bounds on the cost of computing Gröbner bases for HFE systems

Elisa Gorla; Daniela Mueller; Christophe Petit

doi:10.1016/j.jsc.2020.07.011

Stronger bounds on the cost of computing Gröbner bases for HFE systems

Elisa Gorla, Daniela Mueller, Christophe Petit

Computer Science

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

29 Downloads (Pure)

Abstract

We give upper bounds for the solving degree and the last fall degree of the polynomial system associated to the HFE (Hidden Field Equations) cryptosystem. Our bounds improve the known bounds for this type of systems. We also present new results on the connection between the solving degree and the last fall degree and prove that, in some cases, the solving degree is independent of coordinate changes.

Original language	English
Journal	Journal of Symbolic Computation
Early online date	8 Jul 2020
DOIs	https://doi.org/10.1016/j.jsc.2020.07.011
Publication status	E-pub ahead of print - 8 Jul 2020

Keywords

(Fake) Weil descent
Gröbner bases
HFE
Last fall degree
Multivariate cryptography
Solving degree

Access to Document

10.1016/j.jsc.2020.07.011Licence: None: All rights reserved

GorlaE2020StrongerAccepted author manuscript, 260 KBLicence: Creative Commons: Attribution-NonCommercial-NoDerivs (CC BY-NC-ND)

https://linkinghub.elsevier.com/retrieve/pii/S0747717120300663Licence: None: All rights reserved

Cite this

@article{8ac0d507bfd94db5a35a067fd9dce551,

title = "Stronger bounds on the cost of computing Gr{\"o}bner bases for HFE systems",

abstract = "We give upper bounds for the solving degree and the last fall degree of the polynomial system associated to the HFE (Hidden Field Equations) cryptosystem. Our bounds improve the known bounds for this type of systems. We also present new results on the connection between the solving degree and the last fall degree and prove that, in some cases, the solving degree is independent of coordinate changes.",

keywords = "(Fake) Weil descent, Gr{\"o}bner bases, HFE, Last fall degree, Multivariate cryptography, Solving degree",

author = "Elisa Gorla and Daniela Mueller and Christophe Petit",

year = "2020",

month = jul,

day = "8",

doi = "10.1016/j.jsc.2020.07.011",

language = "English",

journal = "Journal of Symbolic Computation",

issn = "0747-7171",

publisher = "Elsevier",

}

TY - JOUR

T1 - Stronger bounds on the cost of computing Gröbner bases for HFE systems

AU - Gorla, Elisa

AU - Mueller, Daniela

AU - Petit, Christophe

PY - 2020/7/8

Y1 - 2020/7/8

N2 - We give upper bounds for the solving degree and the last fall degree of the polynomial system associated to the HFE (Hidden Field Equations) cryptosystem. Our bounds improve the known bounds for this type of systems. We also present new results on the connection between the solving degree and the last fall degree and prove that, in some cases, the solving degree is independent of coordinate changes.

AB - We give upper bounds for the solving degree and the last fall degree of the polynomial system associated to the HFE (Hidden Field Equations) cryptosystem. Our bounds improve the known bounds for this type of systems. We also present new results on the connection between the solving degree and the last fall degree and prove that, in some cases, the solving degree is independent of coordinate changes.

KW - (Fake) Weil descent

KW - Gröbner bases

KW - HFE

KW - Last fall degree

KW - Multivariate cryptography

KW - Solving degree

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

U2 - 10.1016/j.jsc.2020.07.011

DO - 10.1016/j.jsc.2020.07.011

M3 - Article

SN - 0747-7171

JO - Journal of Symbolic Computation

JF - Journal of Symbolic Computation

ER -

Stronger bounds on the cost of computing Gröbner bases for HFE systems

Abstract

Keywords

Access to Document

Fingerprint

Cite this