Paper 2020/372

Graph indicators of vectorial functions and bounds on the algebraic degree of composite functions

Claude Carlet

Abstract

Given a vectorial function $F:\mathbb{F}_2^n \mapsto \mathbb{F}_2^m$, the indicator $1_{{\cal G}_F}$ of its graph ${\cal G}_F=\{(x,F(x)); x\in \mathbb{F}_2^n\}$ allows to express the algebraic degree of $F$ in a simple way. Exploiting the formula, obtained in a previous paper, for the graph indicator of a composite function $G\circ F$, that involves only a sum of products of $1_{{\cal G}_F}$ and $1_{{\cal G}_G}$, we deduce bounds on the algebraic degree of $G\circ F$, whose efficiency comes from the fact that the algebraic degree of the product of two Boolean functions is bounded above by the sum of their algebraic degrees, while for a composition, it is bounded above by their product. One of these bounds, that depends on the algebraic degrees of $G$ and $1_{{\cal G}_F}$, is tight, general, simple, and most often efficient (for the case where it is not efficient, we give an improved bound, that is a little more complex). As far as we know, it is the first efficient upper bound ever found, that works without any condition on the vectorial functions. It provides a new criterion for the choice of S-boxes in block ciphers. It implies as a corollary a known bound assuming the divisibility of the Walsh transform values by a power of 2. It gives a better view why this latter bound works. Our results generalize to more than two functions. \\ When $F$ is a permutation, our expression of the algebraic degree of $G\circ F$ simplifies into a formula involving the algebraic degrees of the products of a coordinate function of $G$ and coordinate functions of $F^{-1}$. This implies another known bound showing that the algebraic degree of $F^{-1}$ has more impact on that of $G\circ F$ than that of $F$ itself. Our approach by graph indicators gives one more explanation to this interesting fact. Our results include all the known efficient bounds as particular cases, and clarify the reasons why they work. We also deduce the exact expression of the algebraic degree of the composition of any number of functions, leading to a bound that is much more efficient than what we obtain by applying the known bound several times. We also obtain two bounds on the algebraic degree of $G \circ F$, where $F$ is a permutation, given the divisibility by powers of 2 of some Walsh transform values of component functions of $F$ and their sums with a coordinate function of $G$. We study the generalizations of all (known and new) bounds of this kind to the composition of more than two functions.