TY - JOUR
T1 - Growth of the ideal generated by a quadratic multivariate function over GF(3)
AU - Ding, Jintai
AU - Hodges, Timothy J.
AU - Kruglov, Victoria
AU - Schmidt, Dieter
AU - Tohneanu, Stefan
PY - 2013/8
Y1 - 2013/8
N2 - 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.
AB - 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.
KW - Cohomology
KW - finite-dimensional algebras
KW - functions over finite fields
KW - growth of ideals
KW - XL algorithm
UR - http://www.scopus.com/inward/record.url?scp=84874801520&partnerID=8YFLogxK
U2 - 10.1142/S0219498812502192
DO - 10.1142/S0219498812502192
M3 - Article
AN - SCOPUS:84874801520
SN - 0219-4988
VL - 12
JO - Journal of Algebra and its Applications
JF - Journal of Algebra and its Applications
IS - 5
M1 - 1250219
ER -