A Note on the Insecurity of Cryptosystems Based on Chebyshev Polynomials
Zhengjun Cao, Lihua Liu · International Journal of Bifurcation and Chaos · 2022
The security of cryptosystems based on Chebyshev recursive relation, [Formula: see text], relies on the difficulty to find the large degree [Formula: see text] of Chebyshev polynomial for given parameters. But this relation cannot be used to evaluate [Formula: see text], if [Formula: see text] 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 [Formula: see text] over finite field [Formula: see text]. 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.