Deciding multiaffinity of polynomials over a finite field

Abstract We consider polynomials f ( x 1 , …, x n ) over a finite filed that satisfy the following condition: the set of solutions of the equation f ( x 1 , …, x n ) = b , where b is some element of the field, coincides with the set of solutions of some system of linear equations over this field. Such polynomials are said to be multiaffine with the right-hand side b (or with respect to b ). We describe a number of properties of multiaffine polynomials. Then on the basis of these properties we propose a polynomial algorithm that takes a polynomial over a finite field and an element of the field as an input and decides whether the polynomial is multiaffine with respect to this element. In case of the positive answer the algorithm also outputs a system of linear equations that corresponds to this polynomial. The complexity of the proposed algorithm is the smallest in comparison with other known algorithms that solve this problem.