Paper 2020/307

Handling vectorial functions by means of their graph indicators

Claude Carlet

Abstract

We characterize the ANF and the univariate representation of any vectorial function as parts of the ANF and bivariate representation of the Boolean function equal to its graph indicator. We show how this provides, when $F$ is bijective, the expression of $F^{-1}$ and/or allows deriving properties of $F^{-1}$. We illustrate this with examples and with a tight upper bound on the algebraic degree of $F^{-1}$ by means of that of $F$. We characterize by the Fourier-Hadamard transform, by the ANF, and by the bivariate representation, that a given Boolean function is the graph indicator of a vectorial function. We also give characterizations of those Boolean functions that are affine equivalent to graph indicators. We express the graph indicators of the sum, product, composition and concatenation of vectorial functions by means of the graph indicators of the functions. We deduce from these results a characterization of the bijectivity of a generic $(n,n)$-function by the fact that some Boolean function, which appears as a part of the ANF (resp. the bivariate representation) of its graph indicator, is equal to constant function 1. We also address the injectivity of $(n,m)$-functions. Finally, we study the characterization of the almost perfect nonlinearity of vectorial functions by means of their graph indicators.

Note: To appear in IEEE Transactions on Information Theory.