Last Fall Degree of Semilocal Polynomial Systems

Abstract. We study the last fall degrees of semilocal polynomial systems and the computational complexity of solving such systems for closed-point and rational-point solutions, where the systems are defined over a finite field. A semilocal polynomial system specifies an algebraic set which is the image of a global linear transformation of a direct product of local affine algebraic sets. As a special but interesting case, polynomial systems that arise from Weil restriction of algebraic sets in an affine space of low dimension are semilocal. Such systems have received considerable attention due to their application in cryptography. Our main results bound the last fall degree of a semilocal polynomial system in terms of the number of closed point solutions and yield an efficient algorithm for finding all rational-point solutions when the prime characteristic of the finite field and the number of rational solutions are small. Our results on solving semilocal systems imply an improvement on a previously known polynomial-time attack on the hidden field equations cryptosystems. The attacks implied in our results extend to public key encryption functions which are based on semilocal systems where either the number of closed point solutions is small or the characteristic of the field is small. It remains plausible to construct public key cryptosystems based on semilocal systems over a finite field of large prime characteristic with an exponential number of closed point solutions. Such a method is presented in the paper, followed by further cryptanalysis involving the isomorphism of polynomials problem, as well as a concrete public key encryption scheme which is secure against all the attacks discussed in this paper.