Cryptanalysis of two sparse polynomial based public key cryptosystems - BAO, Feng (Institutional Knowledge at Singapore Management University, 2001)
The application of sparse polynomials in cryptography has been studied recently. A public key encryption scheme EnRoot [4] and an identification scheme SPIFI [1] based on sparse polynomials were proposed. In this paper, we show that both of them are insecure. The designers of SPIFI proposed the modified SPIFI [2] after Schnorr pointed out some weakness in its initial version. Unfortunately, the modified SPIFI is still insecure. The same holds for the generalization of EnRoot proposed in [2].