3
$\begingroup$

I am using the method presented in this paper to find the nonlinearity of the function

$$ f: \mathbb{F}^1_2 \to \mathbb{F}^1_2 \\ f(x) = x$$

The truth table is $f = [0 \space \space 1]$. Now, I read from the paper by Terry Ritter that

Nonlinearity is the number of bits which must change in the truth table of a Boolean function to reach the closest affine function.

This means the nonlinearity value should be a whole number.

The algorithm to calculate nonlinearity is to first use the Fast Walsh Transform to find the Walsh spectrum, then use the formula

$$Nl(f_k) = 2^{k-1} - \dfrac12 \cdot\max_{a\in\mathbb{F_2^{2^k}}} |W_f(a)| $$

where the Walsh spectrum is calculated by multiplying the truth table of the function by the corresponding Hadamard matrix.

So, since $k = 1$, we use the Hadamard matrix of size $2^1$ giving the following Walsh spectrum:

$$ \begin{bmatrix}0 & 1\end{bmatrix} \begin{bmatrix}1 & 1\\1 & -1\end{bmatrix} = \begin{bmatrix}1 & -1\end{bmatrix} \implies \max_{a\in\mathbb{F_2^{2^k}}} |W_f(a)| = |-1| = 1 $$

Therefore

$$ Nl(f_{k=1}) = 2^{0} - \dfrac12 \cdot 1 = \dfrac12$$

What am I missing?


In case the links are dead, the linked papers are:

  1. Calculating Nonlinearity of Boolean Functions with Walsh-Hadamard Transform by Pedro Miguel Sosa
  2. Measuring Boolean Function Nonlinearity by Walsh Transform by Terry Ritter
$\endgroup$
4
$\begingroup$

In this formulation you need to convert your function's output range to $\{-1,+1\}$ via $$f`(x)=(-1)^{f(x)}$$ and apply the Walsh Hadamard to the new function $f`(x)$. Using the zero one formulation means you are off by a constant depending on the number of variables since

$$ (-1)^u=1-2u $$ for $u\in \{0,1\}.$

See my answer below on Boolean functions and crypto, it may be useful given your recent questions.

How are boolean functions used in cryptography?

$\endgroup$
2
$\begingroup$

In addition to the answer by kodlu, after carefully re-reading the papers, I was able to figure it out. Key things to note:

1. If we use the Fast Walsh Transform on Boolean functions consisting of $\{0,1\}$ then the formula for nonlinearity is

... half the number of bits in the function, less the absolute value of the unexpected distance.

That is $$ Nl(f) = \dfrac12 \cdot 2^k - \max_{a\in\mathbb{F}_2^{2^k}} |W_f(a)|\\ = 2^{k-1} - \max_{a\in\mathbb{F}_2^{2^k}} |W_f(a)| $$

Therefore, for the question in the original post we have

$$Nl(f) = 2^{0} - |1| = 0$$

Alternatively, page 20 here (alt link) suggests to proceed as follows: After finding the Fast Walsh transform,

  1. Add $2^{k-1}$ to each entry in the row except the first entry. This gives us a new row, call it $FHT'$

  2. If an entry in less than $2^{k-1}$ it remains unchanged. Otherwise, if an entry of $FHT'$ is greater than $2^{k-1}$ then subtract it from $2^k$.

  3. Finally, the nonlinearity is the smallest of these adjusted elements.

2. If we use the Fast Walsh Transform on Boolean functions consisting of $\{1,-1\}$ then the formula for nonlinearity is

$$ Nl(f) = 2^{k-1} - \dfrac12 \cdot\max_{a\in\mathbb{F}_2^{2^k}} |W_f(a)| $$

Because

Using real values $\{1,-1\}$ doubles the magnitude and changes the sign of the FWT results

Source

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.