Efficient Signature Schemes Based on Birational Permutations

Many public key cryptographic schemes (such as cubic RSA) are based on low degree polynomials whose inverses are high degree polynomials. These functions are very easy to compute but time consuming to invert even by their legitimate users. To overcome this problem, it is natural to consider the class of birational permutations ƒ over k-tuples of numbers, in which both ƒ and ƒ−1 are low degree rational functions. In this paper we develop two new families of birational permutations, and discuss their cryptographic applications.