## Cryptology ePrint Archive: Report 2020/1365

Evaluation Methods for Chebyshev Polynomials

Zhengjun Cao and Lihua Liu and Leming Hong

Abstract: The security of cryptosystems based on Chebyshev recursive relation, T_n(x)=2xT_{n-1}(x)-T_{n-2}(x), relies on the difficulty of finding the large degree of Chebyshev polynomials from given parameters. The relation cannot be used to evaluate T_n(x) if n is very large. We will investigate other three methods: matrix-multiplication-based evaluation, halve-and-square evaluation, and root-extraction-based evaluation. Though they have the same theoretical complexity O(\log n\log^2p), we find in some cases the root-extraction-based method is more efficient than the others, which is as fast as the general modular exponentiation. The result indicates that the hardness of some cryptosystems based on modular Chebyshev polynomials is almost equivalent to that of solving general discrete logarithm.

Category / Keywords: foundations / Chebyshev polynomials; matrix-multiplication-based evaluation; halve-and-square evaluation; root-extraction-based evaluation.