Nonlinearity

From Boolean
Revision as of 19:56, 9 February 2019 by Nikolay (talk | contribs) (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...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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, [math]\displaystyle{ F }[/math] and [math]\displaystyle{ G }[/math], is the Hamming distance, i.e. the metric

[math]\displaystyle{ d_H(F,G) = | \{ x : F(x) \ne G(x) \} |. }[/math]

Formally, the nonlinearity [math]\displaystyle{ nl(F) }[/math] of an [math]\displaystyle{ (n,m) }[/math]-function [math]\displaystyle{ F }[/math] is the minimum distance between any component function of [math]\displaystyle{ F }[/math] and any affine Boolean function. In other words,

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

Properties

Nonlinearity remains invariant under CCZ-equivalence (and, therefore, under extended affine and affine equivalence as well). If [math]\displaystyle{ F }[/math] is [math]\displaystyle{ (n,n) }[/math]-permutation, then [math]\displaystyle{ F }[/math] and [math]\displaystyle{ F^{-1}\lt /mah\gt have the same nonlinearity. The nonlinearity of an \lt math\gt (n,m) }[/math]-function [math]\displaystyle{ F }[/math] can be expressed in terms of its Walsh transform via the identity

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

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

[math]\displaystyle{ nl(F) \le 2^{n-1} - 2^{n/2 - 1} }[/math]

for any [math]\displaystyle{ (n,m) }[/math]-function [math]\displaystyle{ F }[/math].

  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.