Boolean Functions and their Cryptographic Criteria (0)

2018       * Univeristy of Tartu, Estonia     Lomonosov Moscow State University, Russia                    Boolean Functions and their  Cryptographic Criteria     


Contents 
1.  Introduction ..................................................................................................................................... 3 
2.  Boolean functions and their representations ................................................................................. 4  2.1  Truth table ............................................................................................................................... 4  2.1.1  Disjunctive normal form .................................................................................................. 4  2.1.2  Conjunctive normal form ................................................................................................ 5  2.2  Algebraic normal form ............................................................................................................. 5  3.  Walsh and Fourier transforms ......................................................................................................... 7  3.1  Hadamard matrices ................................................................................................................. 8  4.  Correlation immunity and algebraic immunity ............................................................................... 9  4.1  Cross-correlation and autocorrelation .................................................................................... 9  4.2  Correlation immunity .............................................................................................................. 9  4.3  Algebraic immunity ............................................................................................................... 10  5.  Nonlinearity of Boolean functions ................................................................................................ 11  5.1  Bent functions ....................................................................................................................... 12  Bibliography ........................................................................................................................................... 13 
 


3    1.  Introduction 
Boolean functions have various applications in cryptography. Linear feedback shift registers (LFSR) use  Boolean functions to generate pseudo-random numbers while S-boxes used in block cyphers are just  vectorial Boolean functions.  
To  make  the  cryptanalysis  more  difficult  to  implement,  we  have  to  be  careful  when  choosing  the  Boolean  functions  for  our  cryptosystem  and  follow  several  recommendations,  often  called  cryptographic criteria. For example, the combining and filtering Boolean functions used in stream and  block cyphers must have certain properties to resist different kinds of attacks. Nonlinearity must be  high for resisting linear approximation attacks while correlation immunity determines the number of  LFSRs needed for a correlation attack. 
This paper gives an overview on the topic of Boolean functions, starting with generalities of Boolean  functions  and  their  representations  and  moving  on  to  different  cryptographic  criteria  of  Boolean  functions,  including  correlation  immunity,  nonlinearity  and  algebraic  immunity.  Both  Walsh  and  Fourier transforms are introduced. The paper also includes a short chapter on Bent functions. 
These  topics  are  covered  shortly,  introducing  the  main  points  and  giving  their  most  important  properties. Thus the paper contains many definitions and properties, while only giving proofs to some  of  them.  The  result  is  a  concise  material,  covering  the  generalities  of  Boolean  functions  and  their  properties relevant in cryptography. 


4    2.  Boolean functions and their representations  
In the following chapters the vector space of all binary vectors of length n will be denoted as  𝔽2𝑛. For  two  vectors  𝑎 = (𝑎1, … , 𝑎𝑛)  and  𝑏 = (𝑏1, … , 𝑏𝑛)  in  𝔽2𝑛  we  define  the  scalar  product  < 𝑎, 𝑏 > = 𝑎1𝑏1 ⊕ …⊕ 𝑎 𝑛𝑏𝑛, where all the operations are over a finite field with two elements  𝔽2 .  The logical negation (or complement) of a Boolean function 𝑓 is 𝑓 = 𝑓 ⊕ 1 . 
Definition 2.1. A Boolean function 𝑓 of 𝑛 variables is a map from 𝔽2𝑛 to 𝔽2 . 
𝐹𝑛 will be used to mark the set of all Boolean functions of 𝑛 variables. 
The value vector of a Boolean function is very important term when describing the function. The weight  and the support of a Boolean function refer to the weight and support of its value vector. 
Definition 2.2. A value vector of a Boolean function is a binary vector 𝑣𝑓 of length 2𝑛 composed of all  𝑓(𝑥) when 𝑥 ∈ 𝔽2𝑛. 
Definition 2.3. The weight of a Boolean function  𝑓 of 𝑛 variables is the number of vectors from the  field 𝔽2𝑛, where the 𝑓 obtains the value of one:  𝑤𝑡(𝑓) = |{𝑥 ∈ 𝔽2𝑛 ∶ 𝑓(𝑥) = 1}|  We say that a Boolean function 𝑓 is balanced if 𝑡(𝑓) = 2 𝑛−1 .  2.1  Truth table 
A Boolean function 𝑓 is often expressed through its truth table, which gives the values of function  𝑓   of 𝑛 variables using all of the elements in 𝔽2𝑛. Those values combine into its value vector. 
For example, the following Table 1 represents a truth table of a function 𝑓 over 𝔽23, where the last row  is its value vector.    𝑥1  0  0  0  0  1  1  1  1  𝑥2  0  0  1  1  0  0  1  1  𝑥3  0  1  0  1  0  1  0  1  𝑓(𝑥1, 𝑥2, 𝑥3)  0  0  0  1  0  0  0  1  Table 1.1. Truth table of function 𝑓 of three variables    2.1.1  Disjunctive normal form 
Since making a table of all possible values is impractical at larger values of 𝑛, other representations of  Boolean functions are often used. One of them is disjunctive normal form (abbreviated DNF) which  presents a Boolean function in a form of disjunction consisting of conjunctive clauses. 
In order to find the DNF of a Boolean function 𝑓(𝑥1, … , 𝑥𝑛) we must present all those sets of values of  𝑥1, … , 𝑥𝑛 where the function 𝑓 obtains the value of one in a form of a conjunction and combine those  conjunctions into a single disjunction.  
For example, function  𝑓(𝑥1, 𝑥2, 𝑥3) presented in the Table 1 has two sets of  𝑥1, 𝑥2, 𝑥3 values, where  the function obtains the value of one:  𝑥1𝑥2𝑥3 and 𝑥1𝑥2𝑥3. Thus, the DNF of function  𝑓(𝑥1, 𝑥2, 𝑥3) is  𝑥1𝑥2𝑥3 + 𝑥1𝑥2𝑥3, where + marks the binary operation or. 


5    2.1.2  Conjunctive normal form 
Similarly to disjunctive normal form, a Boolean function can also be expressed by a conjunction of  disjunctive clauses.  
To find the conjunctive normal form (CNF) of a Boolean function  𝑓(𝑥1, … , 𝑥𝑛) we must select those  sets of values of  𝑥1, … , 𝑥𝑛 where the function  𝑓 obtains a value of zero, invert those values and join  them into a single disjunction. Then all such disjunctions are combined into a single conjunction, which  is called the CNF of function 𝑓. 
Thus the CNF of the function 𝑓(𝑥1, 𝑥2, 𝑥3) presented in the Table 1 is:  (𝑥1 + 𝑥2 + 𝑥3)(𝑥1 + 𝑥2 + 𝑥3)(𝑥1 + 𝑥2 + 𝑥3)(𝑥1 + 𝑥2 + 𝑥3)(𝑥1 + 𝑥2 + 𝑥3)(𝑥1 + 𝑥2 + 𝑥3)  2.2  Algebraic normal form 
One of the most classical representations of Boolean functions is in a form of a 𝑛-variable polynomial  over the field  𝔽2 . It is also most commonly used in cryptography and coding. This representation is  called the algebraic normal form (ANF), also known as a Zhegalkin polynomial. 
Definition 2.4. Let 𝑓 be a Boolean function of 𝑛 variables. Then the polynomial in the following form   𝑓(𝑥1, … , 𝑥𝑛) = ⊕𝑢∈𝔽 2 𝑛 µ𝑓  ∏ 𝑥 𝑖 𝑢𝑖 𝑛 𝑖=1   is called the algebraic normal form of function 𝑓. The monomial ∏ 𝑥𝑖 𝑢𝑖 𝑛 𝑖=1  is often denoted by 𝑥𝑢.  The µ𝑓 is also a Boolean function of 𝑛 variables, which is called the Möbius transformation of  𝑓. The  coefficients of ANF satisfy the following equation:  µ𝑓 =   ∑ 𝑓(𝑥) 𝑥≤𝑢 𝑢∈𝔽2𝑛     where the sum is in 𝔽2  and 𝑥 ≤ 𝑢  if and only if 𝑥𝑖 ≤ 𝑢𝑖 for all 1 ≤ 𝑖 ≤ 𝑛 . 
Let us compute the coefficients 𝑎𝑢 of the function 𝑓(𝑥1, 𝑥2, 𝑥3) shown in Table 1 above:  𝑎000 = 𝑓(000) = 0  𝑎001 = 𝑓(000) + 𝑓(001) = 0  𝑎010 = 𝑓(000) + 𝑓(010) = 0  𝑎011 = 𝑓(000) + 𝑓(010) + 𝑓(001) + 𝑓(011) = 1  𝑎100 = 𝑓(000) + 𝑓(100) = 0  𝑎101 = 𝑓(000) + 𝑓(001) + 𝑓(100) + 𝑓(101) = 0  𝑎110 = 𝑓(000) + 𝑓(010) + 𝑓(100) + 𝑓(110) = 0 
𝑎111 = ∑ 𝑓 (𝑥) = 𝑤𝑡(𝑓) 𝑚𝑜𝑑 2 = 𝑥∈𝔽23  0    Thus the ANF of the function 𝑓 is 𝑥2𝑥3.  It is important to note that a unique ANF exists for every Boolean function. 
Definition  2.5.  The  (algebraic)  degree  of  a  function  𝑓  is  the  degree  of  the  largest  monomial  in  its  algebraic normal form. In other words:  deg 𝑓 = max 𝑢∈𝔽2𝑛 𝑎𝑢≠0  𝑤𝑡(𝑢) 


6    Algebraic  degree  is  one  of  the  most  important  properties  of  Boolean  functions,  when  it  comes  to  cryptography. One of the basic requirements relative to the Boolean functions used in stream ciphers  is that they allow to increase the linear complexity, which is obtained if these functions have a high  algebraic degree.[7] 
Lemma 2.1. The weight of a Boolean function 𝑓 over 𝔽2𝑛 is an odd number if and only if deg 𝑓 = 𝑛. 
Theorem 2.1. If a Boolean function 𝑓 of 𝑛 variables has a degree of deg 𝑓 = 𝑑  > 1 , then the following  inequality stands correct:   2𝑛−𝑑 ≤ 𝑤𝑡(𝑓) ≤ 2𝑛 − 2𝑛−𝑑   Proof. Let 𝑥𝑖 1 𝑥𝑖 2 … 𝑥𝑖𝑑 be the monomial with the highest degree enclosed in the ANF of function  𝑓. Let  us decompose the function  𝑓 through  𝑛 − 𝑑 variables not included in the highest order monomial   𝑥𝑖 1 𝑥𝑖 2 … 𝑥𝑖𝑑,  let  𝑓1, … , 𝑓2𝑛−𝑑   be  coefficients  of  this  decomposition.  Since  the  degree  of   𝑓𝑐 ∈ {𝑓1, … , 𝑓2𝑛−𝑑  } is 𝑑 we know from the Lemma 2.1 that 𝑤𝑡(𝑓𝑐) is an odd number. From that we can  easily deduce that 1  ≤ 𝑤𝑡 (𝑓𝑐) ≤ 2𝑑 − 1. Since  𝑤𝑡(𝑓) = ∑ 𝑓 𝑐 2𝑛−𝑑 𝑐=1   it is clear, that  2𝑛−𝑑 ≤ 𝑤𝑡(𝑓) ≤ 2𝑛 − 2𝑛−𝑑 .  ∎ 


7    3.  Walsh and Fourier transforms 
The terminology on these two transforms vary a lot in different materials. Often, the Walsh transform  is also called Hadamard transform or Walsh-Hadamard transform. In many cases, the Walsh transform  is defined in a same way as we define the Fourier transform. In this article the Walsh transform is 
defined as a Fourier transform of its sign function 𝑓χ = (−1)𝑓(𝑥).   Definition 3.1. The Fourier transform of a function  𝑓 on 𝔽2𝑛 is the map from 𝑓 to function 𝐹𝑓 defined  by  𝐹𝑓(𝑢) =   ∑ 𝑓(𝑥) (−1)<𝑥,𝑢>  𝑥∈𝔽2𝑛   Function 𝑓 can be recovered by the inverse Fourier transform:   𝑓(𝑥) = 2−𝑛 ∑ 𝐹 𝑓(𝑢)(−1)<𝑥,𝑢>  𝑥∈𝔽2𝑛   Definition 3.2. The Walsh transform of a function 𝑓 on 𝔽2𝑛 is the map 𝑊𝑓: 𝔽2𝑛 → ℝ, defined by  𝑊𝑓(𝑢) =   ∑ (−1)𝑓(𝑥)⊕<𝑥,𝑢>  𝑥∈𝔽2𝑛   The value 𝑊𝑓(𝑢) is called the Walsh coefficient of the function 𝑓.  
Function 𝑓 can be recovered by the inverse Walsh transform:   (−1)𝑓(𝑥) = 2−𝑛 ∑ 𝑊 𝑓(𝑢)(−1)<𝑥,𝑢>  𝑥∈𝔽2𝑛     Definition 3.3. The Walsh spectrum of 𝑓 is the set of all 2𝑛 Walsh coefficients {𝑊𝑓(𝑢) ∶ 𝑢 ∈ 𝔽 2𝑛} as 𝑢  varies. 
Lemma 3.1. If 𝑢 ∈ 𝔽 2𝑛  ∑ (−1)<𝑥,𝑢> 𝑥∈𝔽2𝑛 = { 0, 𝑢 ≠ 0 𝑛 2𝑛, 𝑢 = 0𝑛    Proof. Firstly, we can easily see that if  𝑢 = 0 𝑛, then all summands are 1 and the sum is  2𝑛. Now, if   𝑢 ≠ 0𝑛,  we  can  look  at  two  sets 𝐴 = {𝑥  ∈ 𝔽2𝑛 ∶ < 𝑥, 𝑢 > = 0 }  and 𝐴′ = {𝑥  ∈ 𝔽2𝑛 ∶ < 𝑥, 𝑢 > = 1 }.  Obviously, those sets belong to 𝔽2𝑛 and their cardinalities are the same 2𝑛−1. Since for any 𝑥 ∈ 𝐴 , the  summand is 1 and for any 𝑥 ∈ 𝐴 , the summand is −1, we get the equation. ∎ 
If and only if the function is balanced the weight of a Boolean function can be expressed though it’s  Walsh transform:  𝑤𝑡(𝑓) =   2𝑛−1  − 1
2 𝑊𝑓(0 𝑛 )   
Lemma 3.2. There is a straight relation between the Fourier and Walsh transform of a function:  𝑊𝑓(𝑢) = 2𝑛𝛿(𝑢) − 2𝐹𝑓(𝑢),  where 𝛿(𝑢) = {1, 𝑢 = 0 𝑛 0, 𝑢 ≠ 0𝑛  .   
 


8    Lemma 3.3.  ∑ 𝑊 𝑓(𝑥)𝑊𝑓(𝑥 𝑥∈𝔽2𝑛 ⊕ 𝑣) = { 0, 𝑣 ≠ 0 𝑛 22𝑛, 𝑣 = 0𝑛    
Proof. Using the equations 𝑊𝑓(𝑥) = 𝐹𝑓 χ(𝑥)  and 𝑓χ(𝑦)2 = 1 we complete following steps:  ∑ 𝑊 𝑓(𝑥)𝑊𝑓(𝑥 𝑥∈𝔽2𝑛 ⊕ 𝑣) = ∑ (−1)<𝑥,𝑦> 𝑓χ(𝑦) 𝑥∈𝔽2𝑛 𝑦∈𝔽2𝑛 ∑ (−1)<𝑥⊕𝑣,𝑧> 𝑓χ(𝑧) 𝑧∈𝔽2𝑛 = ∑ (−1)<𝑣,𝑧>𝑓χ(𝑦) 𝑦∈𝔽2𝑛 𝑧∈𝔽2𝑛 𝑓χ(𝑧) ∑ (−1)<𝑥,𝑦⊕𝑧> 𝑧∈𝔽2𝑛 = ∑ (−1)<𝑣,𝑦>𝑓χ(𝑦)2 = 2𝑛 ∑ (−1)<𝑣,𝑦> 𝑦∈𝔽2𝑛   𝑦∈𝔽2𝑛     Based on Lemma 3.1 the equation stands.  ∎  3.1  Hadamard matrices 
Definition 3.4. A Hadamard matrix 𝐻 of order 𝑛 is an 𝑛 × 𝑛 matrix with elements from {−1, 1}, such  that 𝐻𝐻𝑡 = 𝑛𝐼𝑛, where 𝐻𝑡 is the transpose of 𝐻 and 𝐼𝑛 is the 𝑛 × 𝑛 identity matrix.  
The  product  of  any  two  distinct  rows  or  columns  of  𝐻  is  zero.    Hadamard  matrix  is  often  defined  recursively by:  𝐻𝑛 = ( 𝐻𝑛−1 𝐻𝑛−1 𝐻𝑛−1 −𝐻𝑛−1) ,  𝐻𝑜 = (1)   For example:  𝐻1 = (1 1 1 −1) ,    𝐻2 =   ( 1 1 1 −1 1 1 1 −1 1 1 1 −1 1 1 1 −1 )  etc.  2𝑛 × 2𝑛  matrices  𝐻𝑖 are  also  called  Sylvester-Hadamard  matrices.  Hadamard  matrix  can  also  be  described  as  a  Kronecker  product: 𝐻𝑛 = 𝐻1 ⊗ 𝐻𝑛−1,  where  the  Kronecker  product  is  defined  as  follows:   𝐴 ⊗ B = ( 𝑎11𝐵 ⋯ 𝑎1𝑛𝐵 ⋮ ⋱ ⋮ 𝑎𝑚1 ⋯ 𝑎 𝑚𝑛 𝐵 ) ,  where  𝐴  is  a 𝑚 × 𝑛  matrix.  It  is  important  to  note,  that  Kronecker  product  is  not  commutative,  although it is associative and distributive.  
Now the Fourier transform of function 𝑓 can be described through a Sylvester-Hadamard function as  follows: 𝐹𝑓 = 𝑓𝐻𝑛. Inverse of that is similarly 𝑓 = 2−𝑛𝐹𝑓𝐻𝑛. 


9    4.  Correlation immunity and algebraic immunity  4.1  Cross-correlation and autocorrelation 
Definition 4.1. The following function is called the cross-correlation function of two functions 𝑓 and 𝑔  is a map from 𝔽2𝑛 to [−2𝑛, 2𝑛] defined by:  ∆𝑓,𝑔(𝑢) = ∑ (−1)𝑓(𝑥)⊕𝑔(𝑥⊕𝑢)  𝑥∈𝔽2𝑛   Let us note that cross-correlation is the difference between the number of cases where 𝑓(𝑥) coincides  with 𝑔(𝑥 ⊕ 𝑢) and the number of cases where it does not. 
Definition  4.2.  If 𝑓 = 𝑔   the  cross-correlation  function  is  called  the  autocorrelation  function  and  is  defined by:  ∆𝑓(𝑢) = ∆𝑓,𝑓(𝑢) = ∑ (−1)𝑓(𝑥)⊕𝑓(𝑥⊕𝑢)  = ∑ (−1)𝑓𝑢 ′ (𝑥) 𝑥∈𝔽2𝑛 𝑥∈𝔽2𝑛   Here are some basic properties of autocorrelation:  1.  ∆𝑓(0𝑛) = 2𝑛  2.  ∆𝑓(𝑢) = 0 if and only if function 𝑓 is balanced  3.  ∆𝑓(𝑢) = ∆𝑊 𝑓 (𝑢) for every 𝑢  4.  ∆𝑓(𝑢) = ∆𝑊 𝑓𝑢′ (0𝑛)  Theorem 4.1. If 𝑓, 𝑔  ∈ 𝔽2 , then  (∆𝑓,𝑔(0𝑛), … , ∆𝑓,𝑔(1𝑛)) 𝐻2𝑛 = (𝑊𝑓(0𝑛)𝑊𝑔(0𝑛), … , 𝑊𝑓(1𝑛)𝑊𝑔(1𝑛)),  where 𝐻2𝑛 is a Sylvester-Hadamard matrix. 
Proof.   ∑ ∆ 𝑓,𝑔(𝑢)(−1)<𝑢,𝑣> 𝑢∈𝔽2𝑛 = ∑   𝑢∈𝔽2𝑛 ∑ (−1)𝑓(𝑥)⊕𝑔(𝑥⊕𝑢)(−1)<𝑢,𝑣> 𝑥∈𝔽2𝑛 = ∑ (−1)𝑓(𝑥) 𝑥∈𝔽2𝑛 ∑ (−1)𝑔(𝑥⊕𝑢)⊕<𝑢,𝑣> 𝑢∈𝔽2𝑛 𝑧=𝑥⊕𝑢 ⇒      ∑ (−1)𝑓(𝑥) 𝑥∈𝔽2𝑛 ∑ (−1)𝑔(𝑧)⊕<𝑧,𝑣> 𝑧∈𝔽2𝑛 = ∑ (−1)𝑓(𝑥)⊕<𝑥,𝑣> 𝑥∈𝔽2𝑛 ∑ (−1)𝑔(𝑧)⊕<𝑧,𝑣> 𝑧∈𝔽2𝑛 = 𝑊𝑓(𝑣)𝑊𝑔(𝑣)   ∎    4.2  Correlation immunity 
Correlation immunity is an important property of Boolean functions, since using  Boolean functions  with  low  correlation  immunity  can  allow  effective  attacks  on  the  cryptosystem.  For  example,  correlation immunity plays a crucial role when attacking a stream cipher based on two or more linear  feedback  shift  registers,  whose  outputs  are  combined  by  a  nonlinear  Boolean  function.  In  such  a  combination generator, the correlation-immunity order  𝑘 of the combining function determines the  minimal number of LFSRs which must be considered in a correlation attack - the smallest number of  LFSRs involved in a correlation attack must be 𝑘  +  1. 


10    Definition  4.3.  A Boolean function 𝑓  on 𝔽2𝑛  is said  to  be  correlation  immune of order 𝑘,  where m  satisfies  1  ≤  𝑘  ≤  𝑛 ,  if  the  values  of  𝑓  and  any  subset  of  𝑘  input  variables  are  statistically  independent. 
If a function is correlation immune of order 𝑘, it is also correlation immune of order 𝑘 − 1. 
There is a strong connection between correlation immunity and the Walsh transform of a function. 
Theorem 4.2. A Boolean function  𝑓 on 𝔽2𝑛 is correlation-immune of order  𝑘 if and only if  𝑊𝑓(𝑢) = 0  for all vectors 𝑢  ∈ 𝔽2𝑛, such that 1  ≤  𝑤𝑡(𝑢)   ≤  𝑘. 
A balanced correlation immune function of order  𝑘 is called an  𝑘-resilient function. That means that  the Boolean function 𝑓 is 𝑘-resilient if 𝑤𝑡(𝑓’)   =   2𝑛−𝑚−1  for any subfunction 𝑓′ of 𝑛  −  𝑚 variables. 
Theorem 4.3. (Siegenthaler’s inequality) Let 𝑓 be a Boolean function of 𝑛 variables. Then its correlation  immunity order 𝑘 satisfies  𝑘 + deg 𝑓 ≤  𝑛.  If 𝑓 is balanced (it is 𝑘-resilient function) and 𝑘 < 𝑛 − 1 , then 𝑘 + deg 𝑓 ≤ 𝑛 − 1 . 
That is a very important notion, since it shows that it is not possible to have both a very high degree  and high correlation immunity. 
Theorem  4.4.  If  𝑓  is  a  correlation  immune  function  of  order  𝑘  on  𝔽2𝑛,  where  𝑘 ≤ 𝑛 − 1 ,  then   𝑊𝑓(𝑢)   ≡  0 (𝑚𝑜𝑑 2𝑘 + 1)  Moreover, if f is 𝑘-resilient and 𝑘 ≤ 𝑛 − 2 , then 𝑊𝑓(𝑢) ≡ 0 (𝑚𝑜𝑑 2𝑘 + 2) .  4.3  Algebraic immunity 
In 2003 a new kind of attack, called algebraic attack, was introduced. Algebraic attacks recover the  secret key by solving a system of algebraic equations. High algebraic immunity is needed to resist this  kind of attacks. 
Definition  4.4.  An  annihilator  of  a  polynomial  𝑓(𝑥)  is  a  nonzero  polynomial  𝑔(𝑥)  such  that  𝑓(𝑥)𝑔(𝑥) = 0   Definition 4.5. The minimum degree of  𝑔(𝑥) ≠ 0 𝑛 such that  𝑓(𝑥)𝑔(𝑥) = 0 or (𝑓(𝑥) ⊕ 1)𝑔(𝑥) = 0   is called the algebraic immunity of 𝑓 and denoted by 𝐴𝐼(𝑓).  It is known, that algebraic degree has an upper bound of 𝐴𝐼(𝑓) ≤ ⌈ 𝑛 2⌉ . Thus, a good design aims to use  a function 𝑓 such that neither 𝑓 nor 𝑓 ⊕ 1 has an annihilator at a degree less than ⌈ 𝑛
2⌉ .  An interesting connection between algebraic immunity and the weight of a Boolean function has been  found. Weight of a Boolean function 𝑓 with given algebraic immunity satisfies:  ∑ ( 𝑛 𝑖 ) ≤ 𝑤𝑡 (𝑓) ≤ 𝐴𝐼(𝑓)−1 𝑖=0 ∑ ( 𝑛 𝑖 ) 𝑛−𝐴𝐼(𝑓) 𝑖=0   where (𝑛𝑖) are binomial coefficients (choose 𝑖 elements from 𝑛 elements). 
 


11    5.  Nonlinearity of Boolean functions 
Nonlinearity is one of the most important cryptographic criteria, since it provides confusion. According  to Shannon, confusion refers to making the link between the key and the ciphertext as complex as  possible. Nonlinearity must be high to resist different kinds of attack, including the fast correlation  attack. 
In  order  to  understand  nonlinearity  of  Boolean  functions,  the  definition  of  Hamming  distance  is  needed. 
Definition 5.1. The Hamming distance between two Boolean functions  𝑓 and  𝑔 on  𝔽2𝑛 is defined as  𝑑𝑖𝑠𝑡(𝑓, 𝑔) = 𝑤𝑡(𝑓 ⊕ 𝑔)   Here are some properties of Hamming distance:  1.  𝑑𝑖𝑠𝑡(𝑓, 𝑔) = |{𝑥 ∈ 𝔽 2𝑛 ∶ 𝑓(𝑥) ≠ 𝑔(𝑥)}|  2.  𝑑𝑖𝑠𝑡(𝑓, 𝑔) + 𝑑𝑖𝑠𝑡(𝑔, ℎ) ≥ 𝑑𝑖𝑠𝑡(𝑓, ℎ)  3.  𝑑𝑖𝑠𝑡(𝑓, 𝑔) = 2𝑛 − 𝑑𝑖𝑠𝑡(𝑓, 𝑔)    Definition 5.2. The nonlinearity of a function 𝑓 is defined as 𝑛𝑙(𝑓) =   min φ∈A n 𝑑𝑖𝑠𝑡(𝑓, φ), where 𝐴𝑛 is the  class of all affine functions on 𝔽2𝑛.  
Nonlinearity can be expressed through the Walsh transform: 𝑛𝑙(𝑓) = 2𝑛−1 − 1
2 max 𝑢∈𝔽2𝑛 |𝑊𝑓(𝑢)|.   Since max |𝑊𝑓(𝑢)| > 0, it is trivial that  𝑛𝑙(𝑓) < 2𝑛−1. Furthermore, the following and more precise  upper bound for nonlinearity has been proven: 
Theorem 5.1. The nonlinearity of function 𝑓 satisfies:  𝑛𝑙(𝑓) ≤ 2𝑛−1 − 2 𝑛 2−1   It is important to note that this stands true only if n is even. In the case where  𝑛 is odd, the value of  the maximal nonlinearity is unknown. 
Definition 5.3. A Boolean function  𝑓 is perfect nonlinear if and only if  𝑓(𝑥) ⊕ 𝑓(𝑥 ⊕ 𝑢) is balanced  for any 𝑢 ∈ 𝔽2𝑛, such that 1 ≤ 𝑤𝑡(𝑢) ≤ 𝑛 . 
For a perfect nonlinear Boolean function, any change of input causes the change of output with the 
probability of 1 2 . [10]  There  is  a  straight  connection  between  perfect  nonlinearity  and  the  autocorrelation  of  a  Boolean  function:  
Lemma  5.1.  A  Boolean  function 𝑓  is  perfect  nonlinear  if  and  only  if ∆𝑓(𝑢) = 0  for  every 𝑢 ∈ 𝔽2𝑛,  excluding 0𝑛. 
Another substantial cryptographic criterion, closely linked to perfect nonlinearity is the propagation  criterion, which is important in Boolean functions used in block ciphers. It is difficult to find balance  between  propagation  criteria  and  algebraic  immunity,  thus  designing  Boolean  functions  with  high  algebraic degree and high degree of propagation is a subject of many papers. 
Definition 5.4. A Boolean function  𝑓 is said to satisfy the propagation criterion of degree  𝑘 (denoted  𝑃𝐶(𝑘)) if and only if 𝑓(𝑥) ⊕ 𝑓(𝑥 ⊕ 𝑢) is balanced for any 𝑢 ∈ 𝔽 2𝑛, such that 1 ≤ 𝑤𝑡(𝑢) ≤ 𝑘 . 
We can see, that a perfect nonlinear function satisfies the propagation criterion of degree  𝑛. Important  narrowing of propagation criterion is the strict avalanche criteria: 
Definition 5.5 A Boolean function  𝑓 is said to satisfy the strict avalanche criteria (SAC) if and only if  𝑓(𝑥) ⊕ 𝑓(𝑥 ⊕ 𝑢) is balanced for any 𝑢 ∈ 𝔽2𝑛, such that 𝑤𝑡(𝑢) = 1. 


12    Thus SAC is equivalent to  𝑃𝐶(1). The SAC is a useful property of Boolean functions in cryptography  because satisfying the SAC means that a slight change in the input leads to a large change in the output.  5.1  Bent functions 
Bent  functions  are  functions  with  maximal  nonlinearity,  meaning  their  nonlinearity  is  equal  to  
2𝑛 − 2 𝑛 2−1 .  Lemma 5.2. A Boolean function 𝑓 is called bent if and only if the Walsh transform coefficients are all 
±2 𝑛 2  . That indicates that 𝑊𝑓2 is constant.  Here are some main properties on bent Boolean functions:  1.  Bent functions exist only in even size Boolean spaces, 𝑛 = 2𝑘 .   2.  Bent functions are not balanced.  3.  Bent functions are not correlation immune. 
4.  All of the bent functions have a weight of either 2𝑛−1 − 2 𝑛 2−1  or 2𝑛−1 + 2 𝑛 2−1 .  5.  If 𝑓(𝑥) is a bent function and 𝜑(𝑥) is an affine function on 𝔽2𝑛, then the function 𝑓(𝑥) + 𝜑(𝑥)  is also bent.  For example, function 𝑓 on 𝔽2𝑛 such as 𝑓(𝑥) = 𝑥1𝑥2 is a bent function, since 𝑊𝑓(𝑢) = ±2. 
Theorem 5.2. Any  𝑛-variable Boolean function, where  𝑛 is even, is bent if and only if it satisfies the  propagation criterion of degree 𝑛. Thus, bent functions are perfect nonlinear functions. 
Even though bent functions have maximal nonlinearity, they are improper for use in cryptosystems,  because  they  are  unbalanced.  Stream  ciphers  using a  bent  combining  function  are  vulnerable to  a  correlation attacks. On the other hand, it is possible to modify bent functions randomly to achieve  balancedness, so that the function will preserve its high nonlinearity. This method will be faster than  a brute-force search. It is important to undergo careful testing though, since functions produced in this  way may lose other desirable properties like satisfying the SAC. 
 
 


13    Bibliography  1.  Cusick, T.W. Stănică, P. (2009) Cryptographic Boolean Functions and Applications. San Diego.  Elsevier Inc.  2.  Carlet, C. Boolean Functions for Cryptography and Error Correcting Codes. University of Paris.  3.  Canteaut A. Lecture Notes on Cryptographic Boolean Functions. Paris. Inria.  4.  Cheng-Xin Qu. (2002) Boolean functions in cryptography. University of Wollongong.  5.  Pankratova, I. (2014) Булевы функции в криптографии. Tomsk State University.   6.  Tarannikov, Y. Korolev, P. Botev, A. Autocorrelation Coefficients and Correlation Immunity of  Boolean Functions. Moscow State University.  7.  Climent, J. J. Garcia, F. J. Requena, V. The degree of a Boolean function and some algebraic  properties of its support. Universitat d’Alacant. Universidad Miguel Hernandez de Elche.  8.  Çalik, Ç. (2013) Nonlinearity Computation for Sparse Boolean Functions. Ankara. Middle East  Technical University.  9.  Rodier, F. On the nonlinearity of boolean functions. Marseille. Institut de Math´ematiques de  Luminy.  10. Hirose, S. Ikeda, K. (1994) Nonlinearity criteria of Boolean functions. Kyoto University.  11. Deepak, K. D. Subhamoy, M. (2008) Algebraic Immunity of Boolean Functions – Analysis and  Construction. National Institute of Science Education and Research. Indian Statistical Institute.  12.  Mesnager,  S.  (2014)  A  note  on  linear  codes  and  algebraic  immunity  of  Boolean  functions.  Groningen. 

Document Outline

• Slide 1
• Slide 2
• Slide 3
• Slide 4
• Slide 5
• Slide 6
• Slide 7
• Slide 8
• Slide 9
• Slide 10
• Slide 11
• Slide 12
• Slide 13