## Abstract

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

Original language | English (US) |
---|---|

Pages (from-to) | 327-334 |

Number of pages | 8 |

Journal | Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science |

Volume | 27 |

Issue number | 1 pt 1 |

DOIs | |

State | Published - 1990 |

Externally published | Yes |

Event | Proceedings of the 31st Annual Symposium on Foundations of Computer Science - St. Louis, MO, USA Duration: Oct 22 1990 → Oct 24 1990 |