Inverting square systems algebraically is exponential

Jintai Ding; Crystal Clough; Roberto Araujo

doi:10.1016/j.ffa.2013.10.004

Inverting square systems algebraically is exponential

Jintai Ding^*, Crystal Clough, Roberto Araujo

^*Corresponding author for this work

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

6 Citations (Scopus)

Abstract

In this paper, we prove that the degree of regularity of square systems, a subfamily of the HFE systems, over a prime finite field of odd characteristic q is exactly q and, therefore, prove that inverting square systems algebraically using Gröbner basis algorithm is exponential, when q=Ω(n), where n is the number of variables of the system.

Original language	English
Pages (from-to)	32-48
Number of pages	17
Journal	Finite Fields and their Applications
Volume	26
DOIs	https://doi.org/10.1016/j.ffa.2013.10.004
Publication status	Published - 2014
Externally published	Yes

Keywords

Degree of regularity
HFE
Square

Access to Document

10.1016/j.ffa.2013.10.004

Cite this

@article{639fbb3b4f46459ca087c1f18db2ef81,

title = "Inverting square systems algebraically is exponential",

abstract = "In this paper, we prove that the degree of regularity of square systems, a subfamily of the HFE systems, over a prime finite field of odd characteristic q is exactly q and, therefore, prove that inverting square systems algebraically using Gr{\"o}bner basis algorithm is exponential, when q=Ω(n), where n is the number of variables of the system.",

keywords = "Degree of regularity, HFE, Square",

author = "Jintai Ding and Crystal Clough and Roberto Araujo",

year = "2014",

doi = "10.1016/j.ffa.2013.10.004",

language = "English",

volume = "26",

pages = "32--48",

journal = "Finite Fields and their Applications",

issn = "1071-5797",

}

TY - JOUR

T1 - Inverting square systems algebraically is exponential

AU - Ding, Jintai

AU - Clough, Crystal

AU - Araujo, Roberto

PY - 2014

Y1 - 2014

N2 - In this paper, we prove that the degree of regularity of square systems, a subfamily of the HFE systems, over a prime finite field of odd characteristic q is exactly q and, therefore, prove that inverting square systems algebraically using Gröbner basis algorithm is exponential, when q=Ω(n), where n is the number of variables of the system.

AB - In this paper, we prove that the degree of regularity of square systems, a subfamily of the HFE systems, over a prime finite field of odd characteristic q is exactly q and, therefore, prove that inverting square systems algebraically using Gröbner basis algorithm is exponential, when q=Ω(n), where n is the number of variables of the system.

KW - Degree of regularity

KW - HFE

KW - Square

UR - https://www.scopus.com/pages/publications/84888194273

U2 - 10.1016/j.ffa.2013.10.004

DO - 10.1016/j.ffa.2013.10.004

M3 - Article

AN - SCOPUS:84888194273

SN - 1071-5797

VL - 26

SP - 32

EP - 48

JO - Finite Fields and their Applications

JF - Finite Fields and their Applications

ER -

Inverting square systems algebraically is exponential

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this