  We study the last fall degrees of {\em semi-local} 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
semi-local 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
semi-local. Such systems have received considerable attention due to their
application in cryptography. Our main results bound the last fall degree of a
semi-local 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 semi-local systems imply an
improvement on a previously known polynomial-time attack on the HFE (Hidden
Field Equations) cryptosystems. The attacks implied in our results extend to
public key encryption functions which are based on semi-local 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 semi-local systems over a finite field of large prime characteristic
with exponential number of closed point solutions. Such a method is presented
in the paper, followed by further cryptanalysis involving the isomorphism of
polynomials (IP) problem, as well as a concrete public key encryption scheme
which is secure against all the attacks discussed in this paper.
