Nonlinearity - Revision history

Ivi062 at 09:35, 2 October 2019

2019-10-02T09:35:26Z

Ivi062 at 13:48, 23 September 2019

2019-09-23T13:48:07Z

← Older revision		Revision as of 13:48, 23 September 2019
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

Nikolay at 18:20, 10 February 2019

2019-02-10T18:20:45Z

← Older revision		Revision as of 18:20, 10 February 2019
Line 30:		Line 30:
	<div><math> 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}}.</math></div>		<div><math> 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}}.</math></div>

	The SCV bound coincides with the covering radius bound for <math>m = n - 1</math>, and is strictly sharper than the covering radius bound for <math>m \ge n</math>. For <math>m > n</math>, the square root in the bound cannot be an integer, and thus the SCV bound can be, and is, tight only for <math>m=n</math>. This motivates the definition of [[Almost Bent Functions]] as those <math>(n,n)</math>-functions that meet the SCV bound with equality.		The SCV bound coincides with the covering radius bound for <math>m = n - 1</math>, and is strictly sharper than the covering radius bound for <math>m \ge n</math>. For <math>m > n</math>, the square root in the bound cannot be an integer, and thus the SCV bound can be, and is, tight only for <math>m=n</math>. In this case (for <math>m=n</math>), the bound becomes

			<div><math> nl(F) \le 2^{n-1} - 2^{ (n-1)/2 }.</math></div>
			This motivates the definition of [[Almost Bent Functions]] as those <math>(n,n)</math>-functions that meet the SCV bound with equality.

Nikolay at 18:17, 10 February 2019

2019-02-10T18:17:41Z

← Older revision		Revision as of 18:17, 10 February 2019
Line 20:		Line 20:
	= Bounds on the Nonlinearity of Vectorial Boolean Functions =		= Bounds on the Nonlinearity of Vectorial Boolean Functions =

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

	<div><math>nl(F) \le 2^{n-1} - 2^{n/2 - 1}</math></div>		<div><math>nl(F) \le 2^{n-1} - 2^{n/2 - 1}</math></div>

	for any <math>(n,m)</math>-function <math>F</math>.		for any <math>(n,m)</math>-function <math>F</math>. [[Bent Functions]] are defined as those meeting this bound with equality.

			The ''Sidelnikov-Chabaud-Vaudenay (SCV) bound'' <ref>Sidel'nikov VM. On mutual correlation of sequences. InDoklady Akademii Nauk 1971 (Vol. 196, No. 3, pp. 531-534). Russian Academy of Sciences.</ref> <ref>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.</ref> bounds the nonlinearity of any <math>(n,m)</math>-function, with <math>m \ge n-1</math>, by

			<div><math> 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}}.</math></div>

			The SCV bound coincides with the covering radius bound for <math>m = n - 1</math>, and is strictly sharper than the covering radius bound for <math>m \ge n</math>. For <math>m > n</math>, the square root in the bound cannot be an integer, and thus the SCV bound can be, and is, tight only for <math>m=n</math>. This motivates the definition of [[Almost Bent Functions]] as those <math>(n,n)</math>-functions that meet the SCV bound with equality.

Nikolay: Created page with "= Background and Definition = Vectorial Boolean Functions play an essential role in the design of cryptographic algorithms, and as such should be resistant to various typ..."

2019-02-09T19:56:54Z

Created page with "= Background and Definition = Vectorial Boolean Functions play an essential role in the design of cryptographic algorithms, and as such should be resistant to various typ..."

New page

= 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 <ref name="nybergNonlinearity>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.</ref> in order to measure the resistance of vectorial Boolean functions to Matsui's ''linear attack'' <ref>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.</ref>. 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, <math>F</math> and <math>G</math>, is the ''Hamming distance'', i.e. the metric
<div><math>d_H(F,G) = | \{ x : F(x) \ne G(x) \} |.</math></div>

Formally, the ''nonlinearity'' <math>nl(F)</math> of an <math>(n,m)</math>-function <math>F</math> is the minimum distance between any component function of <math>F</math> and any affine Boolean function. In other words,

<div><math>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 } \}.</math></div>

= 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.

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

<div><math> 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 \}.</math></div>

There is a relation <ref name="cczPaper">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.</ref> between the maximal possible nonlinearity of vectorial Boolean functions and the possible parameters of certain linear codes. If <math>C</math> is a linear <math>[2^n,K,D]</math> containing the Reed-Muller code <math>RM(1,n)</math> as a subcode, let <math>(b_1, b_2, \ldots, b_K)</math> be a basis of <math>C</math> completing a basis <math>(b_1, b_2, \ldots, B_{n+1})</math> of <math>RM(1,n)</math>. Then the <math>n</math>-variable Boolean functions corresponding to the vectors <math>b_{n+2}, \ldots, b_K</math> are the coordinate functions of an <math>(n,K-n-1)</math> functions with nonlinearity <math>D</math>. Conversely, given an <math>(n,m)</math>function <math>F</math> of nonlinearity <math>D > 0</math>, the linear code obtained as the union of all cosets <math> \{ v \cdot F + RM(1,n) : v \in \mathbb{F}_2^m \}</math> has parameters <math>[2^n,n+m+1,D]</math>.

= Bounds on the Nonlinearity of Vectorial Boolean Functions =

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

<div><math>nl(F) \le 2^{n-1} - 2^{n/2 - 1}</math></div>

for any <math>(n,m)</math>-function <math>F</math>.

← Older revision		Revision as of 09:35, 2 October 2019
Line 1:		Line 1:
	= Background and Definition =		= 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 <ref name="nybergNonlinearity>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.</ref> in order to measure the resistance of vectorial Boolean functions to Matsui's ''linear attack'' <ref>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.</ref>. 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, ~~<math>F</math>~~ and ~~<math>G</math>~~, is the ''Hamming distance'', i.e. the metric		[[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 <ref name="nybergNonlinearity>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.</ref> in order to measure the resistance of vectorial Boolean functions to Matsui's ''linear attack'' <ref>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.</ref>. 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 𝐺, is the ''Hamming distance'', i.e. the metric
	<div><math>d_H(F,G) = \| \{ x : F(x) \ne G(x) \} \|.</math></div>		<div><math>d_H(F,G) = \| \{ x : F(x) \ne G(x) \} \|.</math></div>

	Formally, the ''nonlinearity'' ~~<math>nl~~(F)~~</math>~~ of an ~~<math>~~(n,m)~~</math>~~-function ~~<math>F</math>~~ is the minimum distance between any component function of ~~<math>F</math>~~ and any affine Boolean function. In other words,		Formally, the ''nonlinearity'' 𝑛𝑙(𝐹) of an (𝑛,𝑚)-function 𝐹 is the minimum distance between any component function of 𝐹 and any affine Boolean function. In other words,

	<div><math>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 } \}.</math></div>		<div><math>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 } \}.</math></div>
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}</~~math~~> have the same nonlinearity.		Nonlinearity remains invariant under CCZ-equivalence (and, therefore, under extended affine and affine equivalence as well). If 𝐹 is (𝑛,𝑛)-permutation, then 𝐹 and 𝐹<sup>-1</sup> 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 (𝑛,𝑚)-function 𝐹 can be expressed in terms of its Walsh transform via the identity

	<div><math> 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 \}.</math></div>		<div><math> 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 \}.</math></div>

	There is a relation <ref name="cczPaper">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.</ref> between the maximal possible nonlinearity of vectorial Boolean functions and the possible parameters of certain linear codes. If <~~math~~>C</~~math~~> ~~is a linear <math>[2^n~~,K,D]~~</math>~~ containing the Reed-Muller code ~~<math>RM~~(1,n)~~</math>~~ as a subcode, let <~~math~~>~~(b_1~~, ~~b_2~~, ~~\ldots~~, ~~b_K)~~</~~math~~> be a basis of <~~math~~>C</~~math~~> ~~completing a basis~~ <~~math~~>~~(b_1~~, ~~b_2~~, ~~\ldots, B_{n~~+1})</~~math~~> of ~~<math>RM~~(1,n)~~</math>~~. Then the ~~<math>n</math>~~-variable Boolean functions corresponding to the vectors <~~math~~>~~b_{n~~+2}, ~~\ldots~~, ~~b_K~~</~~math~~> are the coordinate functions of an ~~<math>~~(n,K-n-1)~~</math>~~ functions with nonlinearity ~~<math>D</math>~~. Conversely, given an ~~<math>~~(n,m)~~</math>~~function ~~<math>F</math>~~ of nonlinearity ~~<math>D~~ > 0~~</math>~~, the linear code obtained as the union of all cosets <math> \{ v \cdot F + RM(1,n) : v \in \mathbb{F}_2^m \}</math> has parameters <~~math~~>~~[2^n~~,n+m+1,D]~~</math>~~.		There is a relation <ref name="cczPaper">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.</ref> between the maximal possible nonlinearity of vectorial Boolean functions and the possible parameters of certain linear codes. If 𝐶 is a linear
			[2<sup>𝑛</sup>,𝐾,𝐷] containing the Reed-Muller code 𝑅𝑀(1,𝑛) as a subcode, let (𝑏<sub>1</sub>, 𝑏<sub>2</sub>,…,𝑏<sub>𝐾</sub>) be a basis of 𝐶 completing a basis (𝑏<sub>1</sub>, 𝑏<sub>2</sub>,…,𝑏<sub>𝑛+1</sub>) of 𝑅𝑀(1,𝑛). Then the 𝑛-variable Boolean functions corresponding to the vectors 𝑏<sub>𝑛+2</sub>,…, 𝑏<sub>𝐾</sub> are the coordinate functions of an (𝑛,𝐾-𝑛-1) functions with nonlinearity 𝐷. Conversely, given an (𝑛,𝑚)-function 𝐹 of nonlinearity 𝐷>0, the linear code obtained as the union of all cosets <math> \{ v \cdot F + RM(1,n) : v \in \mathbb{F}_2^m \}</math> has parameters [2<sup>𝑛</sup>,𝑛+𝑚+1,𝐷].

	= Bounds on the Nonlinearity of Vectorial Boolean Functions =		= Bounds on the Nonlinearity of Vectorial Boolean Functions =
Line 24:		Line 25:
	<div><math>nl(F) \le 2^{n-1} - 2^{n/2 - 1}</math></div>		<div><math>nl(F) \le 2^{n-1} - 2^{n/2 - 1}</math></div>

	for any ~~<math>~~(n,m)~~</math>~~-function ~~<math>F</math>~~. [[Bent Functions]] are defined as those meeting this bound with equality.		for any (𝑛,𝑚)-function 𝐹. [[Bent Functions]] are defined as those meeting this bound with equality.

	The ''Sidelnikov-Chabaud-Vaudenay (SCV) bound'' <ref>Sidel'nikov VM. On mutual correlation of sequences. InDoklady Akademii Nauk 1971 (Vol. 196, No. 3, pp. 531-534). Russian Academy of Sciences.</ref> <ref>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.</ref> bounds the nonlinearity of any ~~<math>~~(n,m)~~</math>~~-function, with ~~<math>m \ge n~~-1~~</math>~~, by		The ''Sidelnikov-Chabaud-Vaudenay (SCV) bound'' <ref>Sidel'nikov VM. On mutual correlation of sequences. InDoklady Akademii Nauk 1971 (Vol. 196, No. 3, pp. 531-534). Russian Academy of Sciences.</ref> <ref>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.</ref> bounds the nonlinearity of any (𝑛,𝑚)-function, with 𝑚≥𝑛-1, by

	<div><math> 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}}.</math></div>		<div><math> 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}}.</math></div>

	The SCV bound coincides with the covering radius bound for ~~<math>m~~ = n - 1~~</math>~~, and is strictly sharper than the covering radius bound for ~~<math>m \ge n</math>~~. For ~~<math>m > n</math~~>, the square root in the bound cannot be an integer, and thus the SCV bound can be, and is, tight only for ~~<math>m~~=~~n</math>~~. In this case (for ~~<math>m~~=~~n</math>~~), the bound becomes		The SCV bound coincides with the covering radius bound for 𝑚=𝑛-1, and is strictly sharper than the covering radius bound for 𝑚≥𝑛. For 𝑚>𝑛, the square root in the bound cannot be an integer, and thus the SCV bound can be, and is, tight only for 𝑚=𝑛. In this case (for 𝑚=𝑛), the bound becomes

	<div><math> nl(F) \le 2^{n-1} - 2^{ (n-1)/2 }.</math></div>		<div><math> nl(F) \le 2^{n-1} - 2^{ (n-1)/2 }.</math></div>
	This motivates the definition of [[Almost Bent Functions]] as those ~~<math>~~(n,n)~~</math>~~-functions that meet the SCV bound with equality.		This motivates the definition of [[Almost Bent Functions]] as those (𝑛,𝑛)-functions that meet the SCV bound with equality.