June 30, 2016 · Cryptography

Calculating Nonlinearity of Boolean Functions with Walsh-Hadamard Transform

Pedro Miguel Sosa — UCSB, Santa Barbara, CA, USA

It was during Winter 2016 that I took an extremely interesting course on Computational Algebra. This course was solely devoted to analyzing topics that ranged from cryptography to error-resistant functions. Among the many topics, one that stood out for me was LFSRs (Linear Feedback Shift Registers).

LFSRs are simple circuits that use their internal state to calculate a linear function. The output of the function is then fed into the circuit's new state, and the cycle continues. Perhaps that sounds a bit to abstract right now. The truth is that I will most likely write about them in the weeks to come. (Because they are fascinating!). Wikipedia has a nice little animation that shows one in action:

Animation of a linear feedback shift register cycling through its states. — LFSR in Action - Source: Cuddlyable3 @ wikipedia.com

However, this article is not about LFSRs, but rather something even more fundamental: Boolean Functions.

Boolean functions are simply functions whose variables are either a 0 or a 1. While this might seem quite simple, it is the basis of substantially complex cryptographic constructs. In cryptography, researchers are particularly concered on a the "non-linearity" property of boolean function. Non-Linearity is a measure by which we are able to determine the inputs of the function given the output.

For a trivial example, imagine we have a function f(x₁,x₂) = x₁+x₂ and another function g(x₁,x₂) = x₁. Clearly, it is easier to correlate the output of g to it's inputs (namely if g = 1 then x₁ = 1 and if g = 0 then x₁ = 0) than f with its inputs (although it is not that terribly hard). The overall idea is that the harder it is to figure out the inputs of a function given it's output, the more "non-linear" it is and the more cryptographically useful it becomes.

The following is a "tutorial" style paper that explains the basis of boolean functions and how to compute their non-linearity. It explains how to calculate such non-linearity in one of the most refined and proficient ways to do so: with the Fast Walsh-Hadamard Transform. I also included a bit more information on what it means for a function to be "non-linear" and what benefits this brings.

(You can also check this paper out in the Academia.edu link.)

Abstract In this paper we will explain the meaning of nonlinearity in boolean functions, and how to calculate it using Walsh Transform. We will start by providing a brief background on Boolean Functions. We will explain the process by which we calculate nonlinearity and also provide an explanation of the Fast Walsh-Hadamard Transform, which will allow for quicker implementation of this calculation. To conclude, we will provide some motivation behind the importance of nonlinearity and give an overview of Bent Functions.

1Boolean Functions

Overview. Boolean functions are commonly used and quite important in the area of Cryptography. They can be mostly found in the construction of symmetric key algorithms (e.g Substitution Boxes, Linear Feedback Registers, Random Number Generator, among others).

Definition. Mathematically, Boolean functions are defined with the form: $ f_k : B_2^{k} \Rightarrow B_2 $, such that $ B_2 = \left\{0,1\right\} $ and $ k \in \mathbb{Z} $. The $k$ value is referred to as arity of the function and it simply defines how many variables it takes as input. Furthermore, with boolean functions, the additive function is defined with XOR and the multiplicative function is defined with AND.

Affine Boolean Functions. Affine boolean functions are the subset of boolean functions that can be described as:

$$ f = a_k x_k \oplus a_{k-1} x_{k-1} \oplus \dots \oplus a_{1} x_{1} + a_{0} $$

Balance. One of the most important and basic properties that cryptographers seek when choosing to work with certain boolean functions is Balance. This will certainly be important when defining nonlinearity. Balanced functions are those which output 0s and 1s with same probability (50% each) for any given input.

Distance Between Functions. Another important concept to understand nonlinearity is the distance between boolean functions. The distance between two functions $f$ and $g$ represents how many bits need to be inverted on the truth table of function $f$ to match that of function $g$.

example:

f(x) = 0 1 0 1 0 1 1 1 1 0 1 0

g(x) = 0 1 1 0 1 1 1 0 0 0 1 0

$ \text{distance}(f,g) = 5 $

2Nonlinearity

Motivation. The main reason we would want to define the nonlinearity of a given function is to understand how easy it would be to find a correlation between this function's input and its output. These correlations could then be used to attack any crypto-system that uses this function.

Definition. Nonlinearity can be defined as the number of bits that we must invert on a given function $f_k$ truth table to reach the closest k-arity affine function $a_k$.

2.1Calculating Nonlinearity

Expected Distance. Assume we have a function $f_k$ that we want to test against an affine function $a_k$. When we compare the distance between each function, we expect it to be: $ \frac{2^k}{2} $. In other words, we expect about half the bits to be different between the two functions.

Notice that while it might seem counter intuitive, having a lesser distance between $f_k$ and $a_k$ would simply indicate that $f_k$ is actually close to the inverse of $a_k$ (which can be defined as: $ a_k^{-1} = a_k \oplus 1 $).

1 0 0 0 0 1 1 1 = f(x) 1 0 0 0 0 1 1 1 = f(x)

0 0 1 1 1 1 0 0 = a(x) 1 1 0 0 0 0 1 1 = a^-1(x)

$ \text{dist}(f(x), a(x)) = 6 \qquad \text{dist}(f(x), a^{-1}(x)) = 2 $

Thus a distance of $ \frac{2^k}{2} $ is the best we can expect.

Unexpected Distance. We will define the unexpected distance as the amount by which the $ \text{distance}(f,g) $ differs from our expected distance.

example:

f₃ = 1 0 1 0 0 0 1 1

g₃ = 0 1 1 0 1 1 0 0

In the example above the expected distance would be $ \frac{2^3}{2} = 4 $ and the unexpected distance would be $ 4 - 6 = -2 $ which means that $f$ had $2$ more extra bits of difference that we weren't expecting.

Walsh-Hadamard Transform. The Walsh-Hadamard Transform (WHT) is a generalized class of Fourier Transform, which will calculate the unexpected distances between a given function $f_k$ and all k-arity affine functions.

This transform will take the $f_k$'s truth table (TT), multiply it against the Hadamard matrix, and return the Walsh spectrum of the function (which in our case will represent the unexpected distances between $f$ and all k-arity affine functions).

$$ \begin{bmatrix} f\text{'s TT} \end{bmatrix} \cdot \begin{bmatrix} \text{Hadamard Matrix} \end{bmatrix} = \begin{bmatrix} \text{Walsh Spect.} \end{bmatrix} $$

Building the Hadamard matrix. The Hadamard matrix is defined as an n×n matrix whose entries are mutually orthogonal and can only take values of −1 or 1. Hadamard matrices are defined recursively by the following sequence:

$$ H_1 = \begin{bmatrix} 1 \end{bmatrix} ; \qquad H_2 = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} ; $$ $$ H_{2^k} = \begin{bmatrix} H_{2^{k-1}} & H_{2^{k-1}} \\ H_{2^{k-1}} & -H_{2^{k-1}} \end{bmatrix} = H_2 \otimes H_{2^{k-1}} $$

If one is to carefully examine the rows of these matrices, one will find that they represent the truth table for a particular affine function of size n. Thus, to solve a k-arity function one will need to use the Hadamard matrix of size $ n = 2^{k} $.

Fast Walsh Hadamard. The fast Hadamard Transform is a Divide & Conquer algorithm to compute the Walsh-Hadamard function with a computational complexity of $ O(N \log N) $.

The FWH procedure can be understood as follows (where FTT refers to the $f_{k}$ Truth Table):

procedure FWH(FTT) n = size(FTT) for r = 1 to (n/2 − 1): for i = 0 to (n − r): FTT[i] = FTT[i] + FTT[i+r] FTT[i+r] = FTT[i] − FTT[i+r]

Butterfly diagram of the Fast Walsh-Hadamard Transform on 8 inputs: three stages of additions (green) and subtractions (red) combining pairs of values. — Fast Walsh Hadamard Transform¹

Calculating Nonlinearity. Once the Walsh spectrum has been calculated we can measure nonlinearity by the formula:

$$ N(f_k) = 2^{k-1} - \frac{1}{2}\, \max_{a \in \mathbb{F}_{2^{k}}} \left| W_f(a) \right| $$

Essentially, nonlinearity is the difference between our expected distance $ 2^{k-1} $ and the absolute value of the maximum unexpected distance we found between our $f_k$ and some affine function $a_k$.

3Example Calculation

Assume one wishes to test the non-linearity of a function $ f_{k=3} $ whose truth table is:

$$ f = \begin{bmatrix} 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 \end{bmatrix} $$

Thus, one would compute the 8×8 Hadamard Matrix to be:

$$ H_8 = \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 & 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 & 1 & -1 & -1 & 1 \\ 1 & 1 & 1 & 1 & -1 & -1 & -1 & -1 \\ 1 & -1 & 1 & -1 & -1 & 1 & -1 & 1 \\ 1 & 1 & -1 & -1 & -1 & -1 & 1 & 1 \\ 1 & -1 & -1 & 1 & -1 & 1 & 1 & -1 \end{bmatrix} $$

One then proceeds to calculate the Walsh spectrum by multiplying $ f_{k=3} $'s truth table with our Hadamard Matrix.

$$ f \cdot H_{8} = \begin{bmatrix} 4 & 2 & -2 & 0 & 0 & -2 & -2 & 0 \end{bmatrix} $$

Finally, one can see that the maximum unexpected distance is $ |2| $. Notice that one disregards the first element (i.e. 4) of the Walsh Spectrum since this element actually refers to the $ \text{weight}(f) $. So the final nonlinearity calculation becomes:

$$ N(f_{k=3}) = 2^{3-1} - |2| = \mathbf{2} $$

*Note: one could use a truth table described with $ \{\text{True}=1, \text{False}=-1\} $. This would yield a spectrum where all values are $ 2 \cdot $ unexpected distance.

Try it: compute the Walsh spectrum yourself

Tap any bit to flip its truth-table value. The two spectra and the nonlinearity recompute live. The top row is the paper's {0,1} form (its first cell is weight(f)); the bottom row is the equivalent {+1,−1} form whose largest magnitude (highlighted) feeds the formula $N(f_3)=2^{k-1}-\tfrac12\max|W|$.

Truth table f = [ b₀ … b₇ ]

f · H₈ — Walsh spectrum, {0,1} form (cell 0 = weight)

(−1)^f · H₈ — {+1,−1} form (|max| highlighted)

— = N(f₃), the nonlinearity

4Bent Functions

4.1Definition

In Cryptography we are interested in finding the functions with highest possible nonlinearity. By definition, the nonlinearity of a k-ary function f ranges from $0$ (meaning f is itself an affine function) to $ 2^{k-1} - 2^{\frac{k}{2}-1} $. Functions that achieve this upper bound are considered bent.

4.2Characteristics of Bent Functions

Propagation Criteria. Bent functions will satisfy the Propagation Criteria (PC) of degree $k$. The propagation criteria is a higher-order formalization of the Avalanche effects. PC(k) refers to the behavior observed in boolean functions where for any given input, if n bits ($ 0 < n < k $) are flipped each of the output bits will change with a 50% probability. Mathematically we can define this as:

$$ f \text{ is } PC(n) \text{ if } \forall\, a \text{ with } w_{H}(a) \leq n $$ $$ D_{a}f(x) = f(x) \oplus f(x \oplus a) \text{ is balanced} $$

Generation of Hadamard Matrix. Given any bent function $f_k$ we are able to generate the Hadamard Matrix. The process to do this is defined as:

$$ H_{k} = \left[ (-1)^{f(x \oplus y)} \right]_{x,y \in \mathbb{F}_{2}^{k}} $$

4.3Characterization of Bent Functions

The most common characterization of bent functions is the mod m type, defined as:

$$ f : \mathbb{Z}_m^n \to \mathbb{Z}_m $$ $$ \hat{f}(a) = \sum_{x \in \mathbb{Z}_m^n} e^{\frac{2 \pi i}{m} (f(x) - a \cdot x)} $$

However, there is still no complete characterization of bent functions to date, partially because these are quite atypical among higher arity boolean functions. This is still considered an open problem within Cryptography.

References

C. Carlet. Encyclopedia of Cryptography and Security, chapter Nonlinearity of Boolean Functions, pages 416–417. Springer US, Boston, MA, 2005.
C. Carlet. Boolean functions for cryptography and error correcting codes, 2007.
B. Fino and V. Algazi. Unified matrix treatment of the fast walsh-hadamard transform. Computers, IEEE Transactions on, C-25(11):1142–1146, Nov 1976.
T. R. O'Dowd. Discovery of bent functions using the fast walsh transform. Master's thesis, Naval Postgraduate School (U.S.), Monterey, California, 12 2010.
T. Ritter. Measuring boolean function nonlinearity by walsh transform, 1998.
O. Rothaus. On "bent" functions. Journal of Combinatorial Theory, 20(3):300–305, May 1976.

¹ Image by: Timako. ↩