Abstract
Let K be the field GF(3). We calculate the growth of the ideal Aλ where A is the algebra of functions from Kn → Kn and λ is a quadratic function. Specifically we calculate dim A kλ where Ak is the space of polynomials of degree less than or equal to k. This question arises in the analysis of the complexity of Gröbner basis attacks on multivariate quadratic cryptosystems such as the Hidden Field Equation systems. We also prove analogous results over the associated graded ring B = K[X1, ⋯, Xn]/(X 13, ⋯, Xn3) and state conjectures for the case of a general finite field of odd order.
| Original language | English |
|---|---|
| Article number | 1250219 |
| Journal | Journal of Algebra and its Applications |
| Volume | 12 |
| Issue number | 5 |
| DOIs | |
| Publication status | Published - Aug 2013 |
| Externally published | Yes |
Keywords
- Cohomology
- XL algorithm
- finite-dimensional algebras
- functions over finite fields
- growth of ideals
Fingerprint
Dive into the research topics of 'Growth of the ideal generated by a quadratic multivariate function over GF(3)'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver