Cryptanalysis of two sparse polynomial based public key cryptosystems

• Main Authors: BAO, Feng, DENG, Robert H., Geiselmann, Willi, Schnorr, Claus, Steinwandt, Rainer, WU, Hongjun
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2001
• Subjects: Information Security
• Online Access: https://ink.library.smu.edu.sg/sis_research/1108; https://ink.library.smu.edu.sg/context/sis_research/article/2107/viewcontent/Bao2001_CryptanalysisOfTwoSparsePolynomial_pv.pdf
• Institution: Singapore Management University

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].