Breaking the Ong-Schnorr-Shamir Signature Scheme for Quadratic Number Fields

Recently Ong, Schnorr, and Shamir [OSS1, OSS2] have presented new public key signature schemes based on quadratic equations. We will refer to these as the OSS schemes. The security of the schemes rest in part on the difficulty of finding solutions to (1)$$ X^2 - KY^2 \equiv M(mod{\mathbf{ }}n), $$ where n is the product of two large rational primes. In the original OSS scheme [OSS1], K, M, X, and Y were to be rational integers. However, when this version succumbed to an attack by Pollard [PS,S1], a new version was introduced [OSS2], where M, X, and Y were to be quadratic integers, i. e. elements of the ring $$ Z[\sqrt d ] $$. In this paper we will show that the OSS system in $$ Z[\sqrt d ] $$ is also breakable The method by which we do this is to reduce the problem of solving the congruence over the ring $$ Z[\sqrt d ] $$ to the problem of solving the congruence over the integers, for which we can use Pollard’s algorithm.