A Note on the Insecurity of Cryptosystems Based on Chebyshev Polynomials.

The security of cryptosystems based on Chebyshev recursive relation, T n (x) = 2 x T n − 1 (x) − T n − 2 (x) , relies on the difficulty to find the large degree n of Chebyshev polynomial for given parameters. But this relation cannot be used to evaluate T n (x) , if n is very large. We investigate three other methods: matrix-multiplication-based evaluation, halve-and-square evaluation, and root-extraction-based evaluation. We find they have the same complexity O (log n log 2 p) over finite field p . The result shows that the hardness of some cryptosystems based on modular Chebyshev polynomials is almost equivalent to the general discrete logarithm. This partially answers the question why such chaos-based cryptosystems have rarely been put into practice. [ABSTRACT FROM AUTHOR]