Breaking public key cryptosystem based on systems of nonlinear equations over finite field

Tsujii et al. (see ibid., vol.23, no.11, p.558-60, 1987) proposed a public key cryptosystem which requires only O(m/sup 2/) bit operations for encryption/decryption and which also realised digital signatures; m here is the block length. The speed advantage over better known systems such as the RSA system (which takes O(m/sup 3/) operations) could have been immensely significant. Unfortunately it is possible to deduce the private key of the Tsujii system from the public key in polynomial time except possibly in a tiny minority of randomly chosen cases.<>