The security of the birational permutation signature schemes (Q1364903)

The paper describes several attacks which can be applied to the family of signature schemes proposed by \textit{A. Shamir} [Advances in Cryptology -- CRYPTO'93, Santa Barbara, CA, Lect. Notes Comput. Sci. 773, 1-12 (1994; Zbl 0877.94041)]. Shamir's schemes were put forward as a possible alternative to the RSA signature scheme, employing polynomials of low degree and of several variables taking values in the ring \({\mathbb Z}_N\) with \(N\) large (e.g. one of the schemes under consideration is based on quadratic forms) and consequently having lower computational requirements, and they also improved on an earlier scheme [\textit{H. Ong, C. P. Schnorr} and \textit{A. Shamir}, A fast signature scheme based on quadratic equations, Proc. 16th ACM Symp. Theory of Computing, 208-216 (1984); see also Zbl 0571.94015)], which was broken in [\textit{J. M. Pollard} and \textit{C. P. Schnorr}, An efficient solution of the congruence \(x^2+ky^2=m\pmod n\), IEEE Trans. Inf. Theory IT-33, No. 5, 702-709 (1987; Zbl 0636.94008)]. The conclusion of the authors is that Shamir's schemes are vulnerable to the proposed attacks. Many proofs in the paper are based on the following `rule of the thumb,' supported by some mathematical arguments but still largely heuristic: if \(N\) is a large composite integer whose prime factorization is unknown, then in many situations one is free to treat the ring \({\mathbb Z}_N={\mathbb Z}/N{\mathbb Z}\) as a field, at least in the algorithmic aspects, through pretending that one is working in some \({\mathbb Z}_p\). Discovering the exact nature of the phenomenon behind this principle is a challenging problem for an interested model theorist.