Welcome to the resource topic for 2020/1365
Title:
Evaluation Methods for Chebyshev Polynomials
Authors: Zhengjun Cao, Lihua Liu, 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.
ePrint: https://eprint.iacr.org/2020/1365
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .