Paper 2020/1365

Evaluation Methods for Chebyshev Polynomials

Zhengjun Cao, 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Chebyshev polynomialsmatrix-multiplication-based evaluationhalve-and-square evaluationroot-extraction-based evaluation.
Contact author(s)
caozhj @ shu edu cn
History
2020-11-02: received
Short URL
https://ia.cr/2020/1365
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1365,
      author = {Zhengjun Cao and Lihua Liu and Leming Hong},
      title = {Evaluation Methods for Chebyshev Polynomials},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1365},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1365}},
      url = {https://eprint.iacr.org/2020/1365}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.