LAT sboxes, сумма столбцов и строк

пусть у нас есть sbox s: Vn -> Vn.

Если мы составим таблицу LAT для s, зафиксируем любую строку и получим сумму по столбцам, эта сумма будет $+-2^{n-1}$.

И наоборот, если мы зафиксируем любой столбец и получим сумму по строкам, эта сумма будет $+-2^{n-1}$ тоже. Почему это так?

Элемент в строке «a», столбце «b» LAT $#{<a, x>=<b,s(x)>} - 2^{n-1}$. Где <,> скалярное произведение.

Сумма — это сумма целых чисел, находящихся в одном столбце матрицы/одной строке матрицы.

Во-первых, строка/столбец LAT соответствует компонентной функции S-блока/ее инверсии (линейной комбинации выходов). Итак, выведем значение суммы всех коэффициентов Уолша любой булевой функции.

Я буду использовать это определение преобразования Уолша. Результаты для других могут быть легко адаптированы.

$$W_f(a) = \sum_{x\in F_n} (-1)^{\langle a, x\rangle + f(x)},$$ $$\sum_{a \in F_n}W_f(a) = \sum_{a \in F_n}\sum_{x\in F_n} (-1)^{\langle a, x\rangle + f(x)} = \sum_{x\in F_n}\big((-1)^{f(x)}\sum_{a \in F_n}(-1)^{\langle a, x\rangle}\big).$ $ Внутренняя сумма равна нулю, если $х\п 0$ (линейные функции уравновешены), и равен $2^n$ когда $х=0$. Мы получили $$\sum_{a \in F_n}W_f(a) = 2^n\cdot (-1)^{f(0)}.$$

Это вы можете наблюдать, например. на SageMath BooleanFunction.walsh_hadamard_transform.