Nonlinearity: Difference between revisions

From Boolean
No edit summary
mNo edit summary
Line 10: Line 10:
= Properties =
= Properties =


Nonlinearity remains invariant under CCZ-equivalence (and, therefore, under extended affine and affine equivalence as well). If <math>F</math> is <math>(n,n)</math>-permutation, then <math>F</math> and <math>F^{-1}</mah> have the same nonlinearity.
Nonlinearity remains invariant under CCZ-equivalence (and, therefore, under extended affine and affine equivalence as well). If <math>F</math> is <math>(n,n)</math>-permutation, then <math>F</math> and <math>F^{-1}</math> have the same nonlinearity.


The nonlinearity of an <math>(n,m)</math>-function <math>F</math> can be expressed in terms of its Walsh transform via the identity
The nonlinearity of an <math>(n,m)</math>-function <math>F</math> can be expressed in terms of its Walsh transform via the identity

Revision as of 13:48, 23 September 2019

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 [1] in order to measure the resistance of vectorial Boolean functions to Matsui's linear attack [2]. 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, and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} , is the Hamming distance, i.e. the metric

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d_H(F,G) = | \{ x : F(x) \ne G(x) \} |.}

Formally, the nonlinearity Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle nl(F)} of an Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n,m)} -function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} is the minimum distance between any component function of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} and any affine Boolean function. In other words,

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle nl(F) = \min \{ d_H(u \cdot F, f_a) : 0 \ne 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n,n)} -permutation, then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F^{-1}} have the same nonlinearity.

The nonlinearity of an Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n,m)} -function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} can be expressed in terms of its Walsh transform via the identity

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle nl(F) = 2^{n-1} - \frac{1}{2} \max \{ |W_F(u,v)| : u \in \mathbb{F}_2^n, 0 \ne v \in \mathbb{F}_2^m \}.}

There is a relation [3] between the maximal possible nonlinearity of vectorial Boolean functions and the possible parameters of certain linear codes. If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} is a linear Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [2^n,K,D]} containing the Reed-Muller code Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle RM(1,n)} as a subcode, let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (b_1, b_2, \ldots, b_K)} be a basis of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} completing a basis Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (b_1, b_2, \ldots, B_{n+1})} of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle RM(1,n)} . Then the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} -variable Boolean functions corresponding to the vectors Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_{n+2}, \ldots, b_K} are the coordinate functions of an Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n,K-n-1)} functions with nonlinearity Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} . Conversely, given an Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n,m)} function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} of nonlinearity Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D > 0} , the linear code obtained as the union of all cosets Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{ v \cdot F + RM(1,n) : v \in \mathbb{F}_2^m \}} has parameters Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle nl(F) \le 2^{n-1} - 2^{n/2 - 1}}

for any Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n,m)} -function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} . Bent Functions are defined as those meeting this bound with equality.

The Sidelnikov-Chabaud-Vaudenay (SCV) bound [4] [5] bounds the nonlinearity of any Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n,m)} -function, with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m \ge n-1} , by

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle nl(F) \le 2^{n-1} - \frac{1}{2} \sqrt{3 \cdot 2^n - 2 - 2 \frac{(2^n-1)(2^{n-1}-1)}{2^m-1}}.}

The SCV bound coincides with the covering radius bound for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m = n - 1} , and is strictly sharper than the covering radius bound for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m \ge n} . For Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m > n} , the square root in the bound cannot be an integer, and thus the SCV bound can be, and is, tight only for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m=n} . In this case (for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m=n} ), the bound becomes

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle nl(F) \le 2^{n-1} - 2^{ (n-1)/2 }.}

This motivates the definition of Almost Bent Functions as those Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n,n)} -functions that meet the SCV bound with equality.

  1. ↑ Nyberg K. On the construction of highly nonlinear permutations. Workshop on the Theory and Application of Cryptographic Techniques 1992 May 24 (pp. 92-98). Springer, Berlin, Heidelberg.
  2. ↑ Matsui M. Linear cryptanalysis method for DES cipher. Workshop on the Theory and Application of Cryptographic Techniques 1993 May 23 (pp. 386-397). Springer, Berlin, Heidelberg.
  3. ↑ Carlet C, Charpin P, Zinoviev V. Codes, bent functions and permutations suitable for DES-like cryptosystems. Designs, Codes and Cryptography. 1998 Nov 1;15(2):125-56.
  4. ↑ Sidel'nikov VM. On mutual correlation of sequences. InDoklady Akademii Nauk 1971 (Vol. 196, No. 3, pp. 531-534). Russian Academy of Sciences.
  5. ↑ Chabaud F, Vaudenay S. Links between differential and linear cryptanalysis. Workshop on the Theory and Application of Cryptographic Techniques 1994 May 9 (pp. 356-365). Springer, Berlin, Heidelberg.
Retrieved from "http://boolean.wiki.uib.no/index.php?title=Nonlinearity&oldid=367"