×

A systematic construction of a \(Q_{2^k}\)-module in TTM. (English) Zbl 1019.94010

Let \(F=F_{2^{8}}\) be the finite field with \(2^{8}\) elements, \(F^{n}\) a linear space over \(F\), and \( \varphi: F^{n} \leftarrow F^{n}\) a tame automorphism of \(F^{n}\) given by an invertible linear transformation of the form \[ \varphi: y_{i}=x_{i}+f_{i}(x_{1}, \dots ,x_{i-1}), \qquad 1 \leq i \leq n, \] where \(f_{1}=0\) and the \(f_{i}\)’s are polynomials for \(i=2,3, \dots ,n\). Making use of such automorphisms, T. Moh [ibid. 27, 2207-2222 (1999; Zbl 0933.94022)] developed the tame transformation method (TTM) to construct the corresponding tame transformation cryptosystem (TTC). The enciphering map in TTC is the composition \( \pi= \varphi_{4} \varphi_{3} \varphi_{2} \varphi_{1}\) of some suitable tame automorphisms \( \varphi_{1}, \varphi_{2}, \varphi_{3}\) and \( \varphi_{4}\), where \[ \varphi_{2}: y_{i}=x_{i}+f_{i}(x_{1}, \dots ,x_{i-1}), \quad f_{1}=0, \quad 2 \leq i \leq r=100, \] and \[ \varphi_{3}: \left\{\begin{align*}{z_{1}&=y_{1}+Q_{2^3}(y_{i_{1}}, \dots ,y_{i_{s}})\cr z_{2}&=y_{2}+Q_{2^3}(y_{k_{1}}, \dots ,y_{k_{s}})\cr z_{i}&=y_{i}, \quad 3 \leq i \leq r=100\cr}\end{align*}\right., \] with \(Q_{2^3}\) a special polynomial of degree \(2^3\) in \(y_{i_{1}}, \dots , y_{i_{s}}\) or \(y_{k_{1}}, \dots ,y_{k_{s}}\), \(1 \leq s < r\), which has degree \(2\) being considered as a polynomial in \(x_{1}, \dots ,x_{r}\). The security of this cryptosystem relies on the fact that it is hard to compute \( \pi^{-1}\) or to compose \( \pi\) into \( \varphi\)’s. The above property of the polynomial \(Q_{2^3}\) provides an easy realization of the enciphering map \(\pi\).
The authors extend Moh’s construction as follows. Let \(F\) be an arbitrary finite field of characteristic \(2\), and \(k \geq 3\) an integer. The authors find \(s=3k+6\) polynomials \[ f_{1}(x_{1}, \dots ,x_{r}), \dots ,f_{s}(x_{1}, \dots ,x_{r}) \] of degree \(2\) in \(r=3k+4\) variables \(x_{1}, \dots,x_{r}\), and construct a polynomial \[ Q_{2^k}(f_{1}, \dots ,f_{s}) \] of degree \(2^k\) in \(f_{1}, \dots ,f_{s}\) which has degree \(2\) as a polynomial in \(x_{1}, \dots ,x_{r}\). The use of the polynomials \(f_{1}, \dots ,f_{s}\) and \(Q_{2^k}\) for different \(k \geq 3\) gives a possibility to produce new TTC’s. This not only enhances the complexity and the security of TTC, but also makes the TTC more accessible. In the last section the authors extend the result to the case of arbitrary positive characteristic.

MSC:

94A60 Cryptography
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
11T55 Arithmetic theory of polynomial rings over finite fields
68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)

Citations:

Zbl 0933.94022
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1080/00927879908826559 · Zbl 0933.94022 · doi:10.1080/00927879908826559
[2] Moh T., The Proc. CrypTEC’99
[3] Patarin J., Asymmetric Cryptography with S-Boxes (1997) · Zbl 0903.94032
[4] Patarin J., Improved Algorithms for Isomorphisms of Polynomials (1998) · Zbl 0919.94030 · doi:10.1007/BFb0054126
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.