Growth of the ideal generated by a quadratic multivariate function over GF(3)

摘要

Let K be the field GF(3). We calculate the growth of the ideal Aλ where A is the algebra of functions from K~n → K~n and λ is a quadratic function. Specifically we calculate dim A _kλ where A_k 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[X_1, ?, X_n]/(X _1 ~3, ?, X_n ~3) and state conjectures for the case of a general finite field of odd order.