¿Por qué la no linealidad de esta función booleana se evalúa a $\frac12$?
Estoy usando el método presentado en este artículo para encontrar la no linealidad de la función
$$ f: \mathbb{F}^1_2 \to \mathbb{F}^1_2 \\ f(x) = x$$
La tabla de la verdad es $f = [0 \space \space 1]$. Ahora, leí del artículo de Terry Ritter que
La no linealidad es el número de bits que deben cambiar en la tabla de verdad de una función booleana para alcanzar la función afín más cercana.
Esto significa que el valor de no linealidad debe ser un número entero.
El algoritmo para calcular la no linealidad es usar primero la Transformada rápida de Walsh para encontrar el espectro de Walsh, luego usar la fórmula
$$Nl(f_k) = 2^{k-1} - \dfrac12 \cdot\max_{a\in\mathbb{F_2^{2^k}}} |W_f(a)| $$
donde el espectro de Walsh se calcula multiplicando la tabla de verdad de la función por la matriz de Hadamard correspondiente.
Entonces, desde $k = 1$, utilizamos la matriz de tamaño de Hadamard $2^1$ dando el siguiente 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 $$
Por lo tanto
$$ Nl(f_{k=1}) = 2^{0} - \dfrac12 \cdot 1 = \dfrac12$$
¿Qué me estoy perdiendo?
En caso de que los enlaces estén muertos, los artículos vinculados son:
- Cálculo de la no linealidad de funciones booleanas con la transformada de Walsh-Hadamard por Pedro Miguel Sosa
- Medición de la no linealidad de la función booleana mediante la transformación de Walsh de Terry Ritter
Respuestas
En esta formulación, necesita convertir el rango de salida de su función a $\{-1,+1\}$ vía $$f`(x)=(-1)^{f(x)}$$ y aplicar el Walsh Hadamard a la nueva función $f`(x)$. Usar la formulación cero uno significa que está fuera de una constante dependiendo del número de variables ya que
$$ (-1)^u=1-2u $$ para $u\in \{0,1\}.$
Vea mi respuesta a continuación sobre funciones booleanas y criptografía, puede ser útil dadas sus preguntas recientes.
¿Cómo se utilizan las funciones booleanas en criptografía?
Además de la respuesta de kodlu, después de releer cuidadosamente los artículos, pude resolverlo. Aspectos clave a tener en cuenta:
1. Si usamos la Transformada rápida de Walsh en funciones booleanas que consisten en $\{0,1\}$ entonces la fórmula para la no linealidad es
... la mitad del número de bits de la función, menos el valor absoluto de la distancia inesperada.
Es decir $$ 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)| $$
Por lo tanto, para la pregunta en la publicación original tenemos
$$Nl(f) = 2^{0} - |1| = 0$$
Alternativamente, la página 20 aquí ( enlace alternativo ) sugiere proceder de la siguiente manera: Después de encontrar la transformación Fast Walsh,
Añadir $2^{k-1}$a cada entrada de la fila excepto la primera entrada. Esto nos da una nueva fila, llámalo$FHT'$
Si una entrada en menos de $2^{k-1}$permanece sin cambios. De lo contrario, si una entrada de$FHT'$ es mayor que $2^{k-1}$ luego restarlo de $2^k$.
Finalmente, la no linealidad es el más pequeño de estos elementos ajustados.
2. Si usamos la Transformada rápida de Walsh en funciones booleanas que consisten en $\{1,-1\}$ entonces la fórmula para la no linealidad es
$$ Nl(f) = 2^{k-1} - \dfrac12 \cdot\max_{a\in\mathbb{F}_2^{2^k}} |W_f(a)| $$
Porque
Usando valores reales $\{1,-1\}$ duplica la magnitud y cambia el signo de los resultados de FWT
Fuente