Efficiently inverting bijections given by straight line programs

Research output: Contribution to journalConference articlepeer-review

1 Scopus citations


Let K be any field, and let F: Kn → Kn 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 Kn → Kn bijection, there always exists an automorphism defining that bijection. This is not generally true for an arbitrary finite field.

Original languageEnglish (US)
Pages (from-to)327-334
Number of pages8
JournalProceedings [1990] 31st Annual Symposium on Foundations of Computer Science
Issue number1 pt 1
StatePublished - 1990
Externally publishedYes
EventProceedings of the 31st Annual Symposium on Foundations of Computer Science - St. Louis, MO, USA
Duration: Oct 22 1990Oct 24 1990


Dive into the research topics of 'Efficiently inverting bijections given by straight line programs'. Together they form a unique fingerprint.

Cite this