Security of Public-Key Cryptosystems Based on Commutative Polynomials Over ℤ22k
Daisaburo Yoshioka · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · 2025
The commutative property has been an essential characteristic in the development of public-key cryptosystems. There are essentially only two kinds of commutative polynomials: monomials and Chebyshev polynomials. By leveraging the commutative property of them, efficiently implementable public-key cryptosystems over the residue class ring ℤ2k have been introduced; unfortunately, however, they can be broken. Although commutative polynomials with two variables could be potential candidates for a public-key cryptosystem over the ring, the characteristics of these polynomials should be rigorously investigated. In this study, we analyzed several properties of commutative polynomials with two variables over ℤ22k. More precisely, the degree period and the condition for permutation polynomials are discussed theoretically and verified experimentally. Based on the derived properties, a security analysis of a key exchange protocol using the commutative polynomials is also discussed.