The security of the birational permutation signature schemes

Abstract

In recent years, researchers have invested a lot of effort in trying to design suitable alternatives to the RSA signature scheme, with lower computational requirements. The idea of using polynomial equations of low degree in several unknowns, with some hidden trap-door, has been particularly attractive. One of the most noticeable attempts to push this idea forward is the Ong-Schnorr-Shamir signature scheme, which has been broken by Pollard and Schnorr. At Crypto '93, Shamir proposed a family of cryptographic signature schemes based on a new method. His design made subtle use of birational permutations over the set of it-tuples of integers modulo a large number N of unknown factorization. However, the schemes presented in Shamir's paper are weak. In the present paper, we describe several attacks which can be applied to schemes in this general family. © 1997 International Association for Cryplologic Research.