×

A note on the insecurity of cryptosystems based on Chebyshev polynomials. (English) Zbl 1485.94067

The Chebyshev polynomials are defined by \(T_n(x) = \cos(n \arccos x)\), where \(x \in [-1, 1]\) and \(n\in\mathbb{N}\), and they can be also defined by the following recursive relation: \(T_0(x)=1\), \(T_1(x)=x\) and \(T_n(x)=2x\cdot T_{n-1}(x)-T_{n-2}(x)\), for \(n\geq 2\). There are many encryption schemes based on the Chebyshev recursive relation and their security relies on the hardness to find a large degree \(n\) of Chebyshev polynomials for given parameters.
In this paper, the authors focus on the problem to evaluate modular Chebyshev polynomials. After describing two public key encryption schemes based on the Chebyshev recursive relation, one defined over the real number field [L. Kocarev et al., Circuits Syst. Signal Process. 24, No. 5, 497–517 (2005; Zbl 1103.94018)] and the other one defined on finite fields [J. Li et al., “Verifiable Chebyshev maps-based chaotic encryption schemes with outsourcing computations in the cloud/fog scenarios”, Concurr. Comput. Pract. Exp. 31, No. 22, Article ID e4523, 10 p. (2019; doi:10.1002/cpe.4523)], they investigate three methods for evaluating Chebyshev polynomials.
First, the authors explain that the expression \(T_n(x) = \cos(n \arccos x)\) can be used for the evaluating, but this method is only suitable for small \(n\), in particular for \(n\leq 2^{20}\). Then they describe three other methods, i.e. Matrix-multiplication-based evaluation, Halve-and-square evaluation and Root-extraction-based evaluation, and they prove that all these techniques, if executed over a finite field \(\mathbb{F}_p\), where \(p\) is a prime, have computational complexity \(O(\log n \log^2 p)\).
Finally, the authors conclude that there is no significant performance difference between these methods for moderate degrees. However, in theory, the root-extraction-based method could be more efficient. If one directly picks \(a\in\mathbb{F}_p\) and considers the explicit expression \(T_n(\frac{a+a^{-1}}{2} \bmod p)\), this method runs almost as fast as the general modular exponentiation.

MSC:

94A60 Cryptography
33C45 Orthogonal polynomials and functions of hypergeometric type (Jacobi, Laguerre, Hermite, Askey scheme, etc.)

Citations:

Zbl 1103.94018
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adleman, L., Manders, K. & Miller, G. [1977] “ On taking roots in finite fields,” Proc. 18th Ann. Symp. Foundations of Computer Science (IEEE Computer Society), pp. 175-178.
[2] Bergamo, P., D’Arco, P., Santis, A. & Kocarev, L. [2005] “Security of public-key cryptosystems based on Chebyshev polynomials,” IEEE Trans. Circuits Syst.-I: Regul. Pap.52-I, 1382-1393. · Zbl 1374.94775
[3] Biham, E. [1991] “ Cryptanalysis of the chaotic-map cryptosystem suggested at EUROCRYPT’91,” Proc. Advances in Cryptology — EUROCRYPT’91, Workshop on the Theory and Application of Cryptographic Techniques, Brighton, UK, April 8-11, 1991 (Springer), pp. 532-534. · Zbl 0825.94182
[4] Cao, Z., Sha, Q. & Fan, X. [2011] “ Adleman-Manders-Miller root extraction method revisited,” Proc. Inform. Secur. Cryptol. — 7th Int. Conf. (Springer), pp. 77-85. · Zbl 1292.94044
[5] Chen, F., Liao, X., Xiang, T. & Zheng, H. [2011] “ Security analysis of the public key algorithm based on Chebyshev polynomials over the integer ring \(\Bbb Z_n\),” Inf. Sci.181, 5110-5118. · Zbl 1272.94021
[6] Cheong, K. & Koshiba, T. [2007] “ More on security of public-key cryptosystems based on Chebyshev polynomials,” IEEE Trans. Circuits Syst.-II: Express Briefs54-II, 795-799.
[7] Geisel, T. & Fairen, V. [1984] “ Statistical properties of chaos in Chebyshev maps,” Phys. Lett.105A, 263-266.
[8] Habutsu, T., Nishio, Y., Sasase, I. & Mori, S. [1991] “ A secret key cryptosystem by iterating a chaotic map,” Proc. Advances in Cryptology — EUROCRYPT’91, Workshop on the Theory and Application of Cryptographic Techniques, Brighton, UK, , April 8-11, 1991, pp. 127-140. · Zbl 0766.94011
[9] Hunziker, M., Machiavelo, A. & Park, J. [2004] “ Chebyshev polynomials over finite fields and reversibility of automata on square grids,” Theor. Comput. Sci.320, 465-483. · Zbl 1068.68089
[10] Kocarev, L. & Tasev, Z. [2003] “ Public-key encryption based on Chebyshev maps,” Proc. 2003 Int. Symp. Circuits and Systems, ISCAS 2003, Bangkok, Thailand, , May 25-28, 2003 (IEEE), pp. 28-31.
[11] Kotulski, Z., Szczepanski, J., Gorski, K., Paszkiewicz, A. & Zugaj, A. [1999] “ Application of discrete chaotic dynamical systems in cryptography — DCC method,” Int. J. Bifurcation and Chaos9, 1121-1135. · Zbl 1089.94505
[12] Lawnik, M. & Kapczynski, A. [2019] “ The application of modified Chebyshev polynomials in asymmetric cryptography,” Comput. Sci.20, https://doi.org/10.7494/csci.2019.20.3.3307.
[13] Li, Z., Cui, Y., Jin, Y. & Xu, H. [2011] “ Parameter selection in public key cryptosystem based on Chebyshev polynomials over finite field,” J. Commun.6, 400-408.
[14] Li, J., Wang, L., Wang, L., Wang, X., Huang, Z. & Li, J. [2019] “ Verifiable Chebyshev maps-based chaotic encryption schemes with outsourcing computations in the cloud/fog scenarios,” Concurr. Comput. Pract. Exp.31, https://doi.org/10.1002/cpe.4523.
[15] Li, C., Tan, K., Feng, B. & Lu, J. [2022] “ The graph structure of the generalized discrete Arnold’s cat map,” IEEE Trans. Comput.71, 364-377. · Zbl 07497646
[16] Liao, X., Chen, F. & Wong, K. [2010] “ On the security of public-key algorithms based on Chebyshev polynomials over the finite field \(\Bbb Z_n\),” IEEE Trans. Comput.59, 1392-1401. · Zbl 1366.94511
[17] Lima, J., Souza, R. & Panario, D. [2008] “ Security of public-key cryptosystems based on Chebyshev polynomials over prime finite fields,” Proc. IEEE Int. Symp. Information Theory, ISIT 2008, Toronto, ON, Canada, , July 6-11, 2008 (IEEE), pp. 1843-1847.
[18] Lima, J., Panario, D. & Souza, R. [2010] “ Public-key encryption based on Chebyshev polynomials over GF(q),” Inf. Process. Lett.111, 51-56. · Zbl 1260.94068
[19] Mason, J. [1993] “ Chebyshev polynomials of the second, third and fourth kinds in approximation, indefinite integration, and integral transforms,” J. Comput. Appl. Math.49, 169-178. · Zbl 0793.33010
[20] Quan, C., Jung, J., Lee, H., Kang, D. & Won, D. [2018] “ Cryptanalysis of a chaotic Chebyshev polynomials based remote user authentication scheme,” Proc. Int. Conf. Information Networking, ICOIN 2018, Chiang Mai, Thailand, , January 10-12, 2018 (IEEE), pp. 438-441.
[21] Qureshi, C. & Panario, D. [2019] “ The graph structure of Chebyshev polynomials over finite fields and applications,” Des. Codes Cryptogr.87, 393-416. · Zbl 1428.12005
[22] Rajaram, G., Ramar, K. & Pillai, P. [2009] “ Public key cryptosystems based on chaotic-Chebyshev polynomials,” Proc. Int. Conf. Advances in Recent Technologies in Communication and Computing, Kottayam, Kerala, India, , 27-28 October 2009 (IEEE Computer Society), pp. 4-8.
[23] Shakiba, A., Hooshmandasl, M. & Meybodi, M. [2016] “ Cryptanalysis of multiplicative coupled cryptosystems based on the Chebyshev polynomials,” Int. J. Bifurcation and Chaos26, 1-11. · Zbl 1343.94081
[24] Tirrell, J. & Zhuang, Y. [2019] “ Hopping from Chebyshev polynomials to permutation statistics,” Electron. J. Comb.26, P3.27. · Zbl 1418.05012
[25] Truong, T., Tran, M. & Duong, A. [2019] “ Improved Chebyshev polynomials-based authentication scheme in client-server environment,” Secur. Commun. Networks2019, 4250743-1-11.
[26] Yan, S., Zhen, P. & Min, L. [2015] “ Provably secure public key cryptosystem based on Chebyshev polynomials,” J. Commun.10, 380-384.
[27] Yoshioka, D. [2020] “ Security of public-key cryptosystems based on Chebyshev polynomials over \(\Bbb Z/ p^k\Bbb Z\),” IEEE Trans. Circuits Syst.-II: Express Briefs67-II, 2204-2208.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.