Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / Vectorial function, code, cryptography

Original Publication (with minor differences): IEEE Transactions on Information Theory

Date: received 9 Mar 2020, last revised 24 Apr 2020

Contact author: claude carlet at gmail com

Available format(s): PDF | BibTeX Citation

Note: To appear in IEEE Transactions on Information Theory.

Version: 20200424:080028 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]