Coppersmith, D.Stern, J.Vaudenay, S.2007-01-182007-01-182007-01-18199710.1007/s001459900028https://infoscience.epfl.ch/handle/20.500.14299/239674In 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 (H. Ong et al., 1984), which has been broken by J.M. Pollard and C.P. Schnorr (1987). A. Shamir (1994) proposed a family of cryptographic signature schemes based on a new method. His design made subtle use of birational permutations over the set of k tuples of integers module a large number N of unknown factorization. However, the schemes presented in Shamir's paper are weak. We describe several attacks which can be applied to schemes in this general familycombinatorial mathematicscryptographybirational permutation signature scheme securityRSA signature schemecomputational requirementspolynomial equationshidden trap doorOng-Schnorr-Shamir signature schemecryptographic signature schemesbirational permutationsk tuplesunknown factorizationtext::journal::journal article::research article