| Abstract: |
| The graphs ${\cal G}_F=\{(x,F(x));\, x\in {\Bbb F}_2^n\}$ of vectorial functions $F: {\Bbb F}_2^n\mapsto {\Bbb F}_2^m$ play an important role in coding theory, since all linear codes and the most important nonlinear codes are systematic. They also play a significant role in symmetric cryptography, in the diffusion layers and substitution boxes of block ciphers. The Walsh transform of a vectorial function $F$, which allows determining its nonlinearity, equals by definition the Fourier-Hadamard transform of the indicator of its graph (that we call the graph indicator of the function), and the CCZ equivalence of vectorial functions is also defined by means of their graphs. The important notion of almost perfect nonlinearity is more naturally defined by means of the graphs of functions. And graph indicators play roles in recent advances of cryptography, like counter-measures against side channel attacks, the leakage squeezing method and the related codes, called complementary information set (CIS) codes). Moreover, looking at these graphs helps simplifying some studies on vectorial functions. For instance, the graph of a permutation and the graph of its compositional inverse are equal, up to variable swap.
We shall express the ANF, the numerical normal form (NNF) and the bivariate (polynomial) representation of the indicator $1_{{\cal G}_F}$ of the graph of any vectorial function $F$ by means of the corresponding representations of the function. When the function is bijective, we shall characterize the ANF and the univariate representation of the compositional inverse as parts of the corresponding representations of the graph indicator; this allows to obtain the expression of $F^{-1}$ in some cases where the equation $F(x)=y$ cannot be solved, and to show results on $F^{-1}$ in some other cases that we shall describe. We shall characterize by the Fourier-Hadamard transform, by the ANF and by the bivariate representation, the fact that a given $(n+m)$-variable Boolean function is the graph indicator of an $(n,m)$-function. We shall address the main operations (addition, multiplication, composition, concatenation) in terms of graph indicators and obtain a rather simple characterization of bijectivity by the fact that some Boolean function which appears in a part of its graph indicator equals the constant function 1. We shall also characterize injectivity in three different ways, and almost perfect nonlinearity in two different ways. |
|