## 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 | IEEE Transactions on Industry Applications |

Volume | 27 |

Issue number | 1 pt 1 |

State | Published - Jan 1 1991 |

Event | 1989 Industry Applications Society Annual Meeting - San Diego, CA, USA Duration: Oct 1 1989 → Oct 5 1989 |