Efficiently inverting bijections given by straight line programs

Let K be any field, and let F: Kⁿ → Kⁿ be a bijection with the property that both F and F^-1 are computable using only arithmetic operations from K. Motivated by cryptographic considerations, the authors concern themselves with the relationship between the arithmetic complexity of F and the arithmetic complexity of F^-1. They give strong relations between the complexity of F and F^-1 when F is an automorphism in the sense of algebraic geometry (i.e., a formal bijection defined by n polynomials in n variables with a formal inverse of the same form). These constitute all such bijections in the case in which K is infinite. The authors show that at polynomially bounded degree, if an automorphism F has a polynomial-size arithmetic circuit, then F^-1 has a polynomial-size arithmetic circuit. Furthermore, this result is uniform in the sense that there is an efficient algorithm for finding such a circuit for F^-1, given such a circuit for F. This algorithm can also be used to check whether a circuit defines an automorphism F. If K is the Boolean field GF(2), then a circuit defining a bijection does not necessarily define an automorphism. However, it is shown in this case that, given any Kⁿ → Kⁿ bijection, there always exists an automorphism defining that bijection. This is not generally true for an arbitrary finite field.