Por que a não linearidade desta função booleana avalia para $\frac12$?
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:
- Cálculo da não linearidade de funções booleanas com a transformada de Walsh-Hadamard de Pedro Miguel Sosa
- Medindo a não linearidade da função booleana pela transformação de Walsh de Terry Ritter
Respostas
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?
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:
Adicionar $2^{k-1}$para cada entrada na linha, exceto a primeira entrada. Isso nos dá uma nova linha, chame-a$FHT'$
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$.
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