Additive and linear structures of cryptographic functions.

*(English)*Zbl 0939.94508
Preneel, Bart (ed.), Fast software encryption. 2nd international workshop, Leuven, Belgium, December 14-16, 1994. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 1008, 75-85 (1995).

Summary: In the design and analysis of cryptographic algorithms, exploiting the structures of such algorithms is an important aspect. In this paper, additive and linear structures of functions from \(GF^{n} (q)\) to \(GF^{m} (q)\) will be considered. A function \(f\) is said to have an additive structure if there is a non-zero vector \(\mathbf{a}\), such that \(f(\mathbf{x} + \text\textbf{a}) - f(\text\textbf{x})\) remains invariant for all \(\mathbf{x}\). Such a vector \(\mathbf{a}\) is called an additive translator of the function \(f\). A function \(f\) is said to have a linear structure if \(f\) has an additive translator \(\mathbf{a}\) and if \(f(\mathbf{x} + c\text\textbf{a}) - f(\text\textbf{x}) = c(f(\text\textbf{a}) - f(\text\textbf{0}))\) for all \(c\) in \(GF(q)\). We call this \(\mathbf{a}\) a linear translator of \(f\). We show how to use such additive and linear structures to simplify the expression of the function \(f\).

It is shown that the function \(f\) has \(r\) linearly independent linear translators if and only if there is a non-singular linear transformation such that the composition of this linear transformation with the original function gives a function that is the sum of a linear function of \(r\) variables and some function of the other \(n - r\) variables. In particular, when \(q\) is a prime, then any additive translator is a linear translator, which implies that \(f\) becomes a sum of an \(r\)-variable linear function and an \(n - r\)-variable function if and only if \(f\) has \(r\) linearly independent additive translators. Moreover, for an invertible function \(f\), there is a one-to-one relationship between the linear translators of \(f\) and the linear translators of its inverse function.

For the entire collection see [Zbl 0829.68005].

It is shown that the function \(f\) has \(r\) linearly independent linear translators if and only if there is a non-singular linear transformation such that the composition of this linear transformation with the original function gives a function that is the sum of a linear function of \(r\) variables and some function of the other \(n - r\) variables. In particular, when \(q\) is a prime, then any additive translator is a linear translator, which implies that \(f\) becomes a sum of an \(r\)-variable linear function and an \(n - r\)-variable function if and only if \(f\) has \(r\) linearly independent additive translators. Moreover, for an invertible function \(f\), there is a one-to-one relationship between the linear translators of \(f\) and the linear translators of its inverse function.

For the entire collection see [Zbl 0829.68005].