Security of Public-Key Cryptosystems Based on Chebyshev Polynomials over the Residue Ring Z/pkZ

摘要

Recently, a public-key cryptosystem using Chebyshev polynomials defined on a finite set has been proposed. The security of the cryptosystem depends on the difficulty of finding the degree of Chebyshev polynomials from given parameters. In this paper, we propose an algorithm to find the degree of Chebyshev polynomials modulo a prime power. The result shows that the cryptosystem based on Chebyshev polynomials modulo a prime power is insecure unless a huge prime is used.