Paper 2020/1365 Original: eprint.iacr.org/2020/1365 ↗
Evaluation Methods for Chebyshev Polynomials
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.
- History
- 2020-11-02: last updated
- 2020-11-02: published
- Short URL
- https://ia.cr/2020/1365
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2020/1365}
}