Por que a não linearidade desta função booleana avalia para $\frac12$?

Dec 17 2020

Estou usando o método apresentado neste artigo para encontrar a não linearidade da função

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

A tabela de verdade é $f = [0 \space \space 1]$. Agora, eu li no jornal de Terry Ritter que

A não linearidade é o número de bits que devem mudar na tabela verdade de uma função booleana para alcançar a função afim mais próxima.

Isso significa que o valor da não linearidade deve ser um número inteiro.

O algoritmo para calcular a não linearidade é usar primeiro a Transformada Walsh Rápida para encontrar o espectro de Walsh e, em seguida, usar a fórmula

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

onde o espectro de Walsh é calculado multiplicando a tabela verdade da função pela matriz de Hadamard correspondente.

Então, desde $k = 1$, usamos a matriz Hadamard de tamanho $2^1$ dando o seguinte espectro de Walsh:

$$ \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 $$

Portanto

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

o que estou perdendo?


Caso os links estejam mortos, os artigos vinculados são:

  1. Cálculo da não linearidade de funções booleanas com a transformada de Walsh-Hadamard de Pedro Miguel Sosa
  2. Medindo a não linearidade da função booleana pela transformação de Walsh de Terry Ritter

Respostas

4 kodlu Dec 18 2020 at 05:12

Nesta formulação, você precisa converter o intervalo de saída de sua função para $\{-1,+1\}$ através da $$f`(x)=(-1)^{f(x)}$$ e aplique o Walsh Hadamard à nova função $f`(x)$. Usar a formulação zero um significa que você está errado por uma constante, dependendo do número de variáveis ​​desde

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

Veja minha resposta abaixo sobre funções booleanas e criptografia, pode ser útil devido às suas perguntas recentes.

Como as funções booleanas são usadas na criptografia?

2 E.Nole Dec 19 2020 at 03:31

Além da resposta de kodlu, depois de reler cuidadosamente os jornais, consegui descobrir. Principais coisas a serem observadas:

1. Se usarmos a Transformada Walsh Rápida em funções booleanas que consistem em $\{0,1\}$ então a fórmula para não linearidade é

... metade do número de bits na função, menos o valor absoluto da distância inesperada.

Isso é $$ 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)| $$

Portanto, para a pergunta na postagem original, temos

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

Como alternativa, a página 20 aqui ( link alternativo ) sugere que você proceda da seguinte forma:

  1. Adicionar $2^{k-1}$para cada entrada na linha, exceto a primeira entrada. Isso nos dá uma nova linha, chame-a$FHT'$

  2. Se uma entrada em menos de $2^{k-1}$ele permanece inalterado. Caso contrário, se uma entrada de$FHT'$ é melhor que $2^{k-1}$ então subtraia de $2^k$.

  3. Finalmente, a não linearidade é o menor desses elementos ajustados.

2. Se usarmos a Transformada Walsh Rápida em funções Booleanas que consistem em $\{1,-1\}$ então a fórmula para não linearidade é

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

Porque

Usando valores reais $\{1,-1\}$ dobra a magnitude e muda o sinal dos resultados do FWT

Fonte