×

Three theorems on odd degree Chebyshev polynomials and more generalized permutation polynomials over a ring of module \(2^w\). (English) Zbl 1430.94075

Summary: Odd degree Chebyshev polynomials over a ring of modulo \(2^w\) have two kinds of period. One is an “orbital period”. Odd degree Chebyshev polynomials are bijection over the ring. Therefore, when an odd degree Chebyshev polynomial iterates affecting a factor of the ring, we can observe an orbit over the ring. The “ orbital period ” is a period of the orbit. The other is a “degree period”. It is observed when changing the degree of Chebyshev polynomials with a fixed argument of polynomials. Both kinds of period have not been completely studied. In this paper, we clarify completely both of them. The knowledge about them enables us to efficiently solve degree decision problem of Chebyshev polynomial over the ring, and so a key-exchange protocol with Chebyshev polynomial over the ring is not secure. In addition, we generalize the discussion and show that a key-exchange protocol with more generalized permutation polynomials which belong to a certain class is not secure.

MSC:

94A60 Cryptography
33D45 Basic orthogonal polynomials and functions (Askey-Wilson polynomials, etc.)
42C05 Orthogonal functions and polynomials, general theory of nontrigonometric harmonic analysis
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Rivest, R.L.: Permutation polynomials modulo \[2^w2\] w. Finite Fields Appl. 7, 287-292 (2001) · Zbl 0997.11111 · doi:10.1006/ffta.2000.0282
[2] Rivest, R.L., Robshaw, M.J.B., Sidney, R., Yin, Y.L.: The RC6 Block Ciphe .https://people.csail.mit.edu/rivest/pubs/RRSY98.pdf. Accessed 9 Oct 2017
[3] Umeno, K., Kim, S., Hasegawa, A.: 128bit VSC specification. http://www.chaosware.com/vsc128.pdf. Accessed 9 Oct 2017 (In Japanese)
[4] Iwasaki, A., Umeno, K.: Improving security of vector stream cipher. Nonlinear Theory Appl. IEICE E7-N, 30-37 (2016) · doi:10.1587/nolta.7.30
[5] Umeno, K.: Key exchange by Chebyshev polynomials modulo \[2^w2\] w. In: Proc. of INA-CISC, pp. 95-97 (2005)
[6] Kocarev, L., Tasev, Z.: Public-key encription based on Chebyshev maps. In: Proc. IEEE Symp. Circuits and Systems (ISCAS’03) vol. 3, pp. 28-31 (2003)
[7] Bergamo, P., D’Arco, P., Santis, A.S., Kocarev, L.: Security of public-key cryptosystems based on Chebyshev polynomials. IEEE Circuits Syst. I Regul. Pap. 52(7), 1382-1393 (2005) · Zbl 1374.94775 · doi:10.1109/TCSI.2005.851701
[8] Ishii, M., Yoshimoto, A.: Applications for cryptography of the structure of the group of reduced residue classes of residue ring of \[\mathbb{Z}/2^w{\mathbb{Z}}\] Z/2wZ. Trans. JSIAM 19(2), 57-71 (2009). (In Japanese)
[9] Ishii, M.: Periodicity of Chebyshev polynomials over the residue ring of \[\mathbb{Z}/2^r{\mathbb{Z}}\] Z/2rZ and an electronic signature. Trans. JSIA 18(2), 257-265 (2008). (In Japanese)
[10] Yoshioka, D., Dainobu, Y.: On some properties of Chebyshev polynomial sequences modulo \[2^k2\] k. Nonlinear Theory Appl. IEICE 6(3), 443-452 (2015) · doi:10.1587/nolta.6.443
[11] Iwasaki, A., Umeno, K.: Periodical property of Chebyshev polynomials on the residue class rings of modulo \[2^w2\] w. IEICE Technical Report, CAS2014-67, NLP2014-61, pp. 81-86 (2014) (In Japanese)
[12] Iwasaki, A., Umeno, K.: Period of orbit and degree of Chebyshev polynomial on a ring of modulo \[2^w2\] w ”. IEICE Technical Report, NLP2015-61, pp. 129-134 (2015) (In Japanese)
[13] Kawano, K., Yoshioka, D.: A solution on the degree determination problem of Chebyshev polynomials over the residue ring \[\mathbb{Z}/2^k\mathbb{Z}\] Z/2kZ. IEICE Technical Report, NLP2015-77, pp. 53-56 (2015) (In Japanese)
[14] Yoshioka, D., Kawano, K.: Periodic properties of Chebyshev polynomial sequences over the residue ring \[\mathbb{Z}/2^k\mathbb{Z}\] Z/2kZ. IEEE Trans. Circuits Syst. II 63, 778-782 (2016) · doi:10.1109/TCSII.2016.2531058
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.