We review a fundamental weak point of the OSS digital signature scheme against cryptanalysis by Pollard et al., and propose a new scheme of digital signature which overcomes this defect. More specifically, instead of the ring of the rational integer, we use the ring of integral quaternions, which is a non-commutative Euclidean ring. Known attacks to OSS signature do not work our scheme due to the non-commutativity. On the other hand, this scheme causes little increase in the burden of generation and verification of digital signature for the legitimate users, with respect to the original OSS scheme.