# zbMATH — the first resource for mathematics

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].

##### MSC:
 94A60 Cryptography 11T71 Algebraic coding theory; cryptography (number-theoretic aspects)