Nonlinearity

Background and Definition

Vectorial Boolean Functions play an essential role in the design of cryptographic algorithms, and as such should be resistant to various types of cryptanalytic attacks. The notion of nonlinearity is introduced by Nyberg in order to measure the resistance of vectorial Boolean functions to Matsui's linear attack . This attack attempts to approximate the function used in an encryption algorithm by a linear function (which, in turn, is easy to analyze), and is, therefore, applicable when the actual functions used in the encryption algorithm is "close" to linear in some sense. A natural measure of distance between two functions, $F$ and Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle G} , is the Hamming distance, i.e. the metric

$d_{H}(F,G)=|\{x:F(x)\neq G(x)\}|.$

Formally, the nonlinearity Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle nl(F)} of an Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (n,m)} -function $F$ is the minimum distance between any component function of $F$ and any affine Boolean function. In other words,

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle nl(F)=\min\{d_{H}(u\cdot F,f_{a}):0\neq u\in \mathbb {F} _{2}^{m},f_{a}:\mathbb {F} _{2}^{n}\rightarrow \mathbb {F} {\text{ affine }}\}.}

Properties

Nonlinearity remains invariant under CCZ-equivalence (and, therefore, under extended affine and affine equivalence as well). If $F$ is Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (n,n)} -permutation, then $F$ and Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle F^{-1}</mah>havethesamenonlinearity.Thenonlinearityofan<math>(n,m)} -function $F$ can be expressed in terms of its Walsh transform via the identity

$nl(F)=2^{n-1}-{\frac {1}{2}}\max\{|W_{F}(u,v)|:u\in \mathbb {F} _{2}^{n},0\neq v\in \mathbb {F} _{2}^{m}\}.$

There is a relation between the maximal possible nonlinearity of vectorial Boolean functions and the possible parameters of certain linear codes. If Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle C} is a linear Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle [2^{n},K,D]} containing the Reed-Muller code Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle RM(1,n)} as a subcode, let Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (b_{1},b_{2},\ldots ,b_{K})} be a basis of $C$ completing a basis Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (b_{1},b_{2},\ldots ,B_{n+1})} of Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle RM(1,n)} . Then the $n$-variable Boolean functions corresponding to the vectors Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle b_{n+2},\ldots ,b_{K}} are the coordinate functions of an Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (n,K-n-1)} functions with nonlinearity Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle D} . Conversely, given an Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (n,m)} function $F$ of nonlinearity Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle D>0} , the linear code obtained as the union of all cosets $\{v\cdot F+RM(1,n):v\in \mathbb {F} _{2}^{m}\}$ has parameters Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle [2^{n},n+m+1,D]} .

Bounds on the Nonlinearity of Vectorial Boolean Functions

The covering radius bound for Boolean functions can naturally be extended to vectorial Boolean functions, stating

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle nl(F)\leq 2^{n-1}-2^{n/2-1}}

for any Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (n,m)} -function $F$.