Почему нелинейность этой логической функции оценивается как $\frac12$?
Я использую метод, представленный в этой статье, чтобы найти нелинейность функции
$$ f: \mathbb{F}^1_2 \to \mathbb{F}^1_2 \\ f(x) = x$$
Таблица истинности $f = [0 \space \space 1]$. Я прочитал из статьи Терри Риттера, что
Нелинейность - это количество битов, которое должно измениться в таблице истинности логической функции, чтобы достичь ближайшей аффинной функции.
Это означает, что значение нелинейности должно быть целым числом.
Алгоритм вычисления нелинейности состоит в том, чтобы сначала использовать быстрое преобразование Уолша для нахождения спектра Уолша, а затем использовать формулу
$$Nl(f_k) = 2^{k-1} - \dfrac12 \cdot\max_{a\in\mathbb{F_2^{2^k}}} |W_f(a)| $$
где спектр Уолша вычисляется путем умножения таблицы истинности функции на соответствующую матрицу Адамара.
Итак, поскольку $k = 1$, мы используем матрицу Адамара размера $2^1$ давая следующий спектр Уолша:
$$ \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 $$
Следовательно
$$ Nl(f_{k=1}) = 2^{0} - \dfrac12 \cdot 1 = \dfrac12$$
Что мне не хватает?
В случае, если ссылки мертвы, связанные документы:
- Вычисление нелинейности булевых функций с преобразованием Уолша-Адамара Педро Мигель Соса
- Измерение нелинейности булевой функции с помощью преобразования Уолша Терри Риттер
Ответы
В этой формулировке вам нужно преобразовать выходной диапазон вашей функции в $\{-1,+1\}$ через $$f`(x)=(-1)^{f(x)}$$ и примените Уолша Адамара к новой функции $f`(x)$. Использование формулы нуля или единицы означает, что вы отключены от константы, зависящей от количества переменных, поскольку
$$ (-1)^u=1-2u $$ для $u\in \{0,1\}.$
См. Мой ответ ниже о булевых функциях и криптографии, он может быть полезен с учетом ваших недавних вопросов.
Как булевы функции используются в криптографии?
Помимо ответа kodlu, внимательно перечитав бумаги, я смог разобраться. Ключевые моменты, на которые следует обратить внимание:
1. Если мы используем быстрое преобразование Уолша для булевых функций, состоящих из $\{0,1\}$ то формула нелинейности имеет вид
... половина числа бит в функции, за вычетом абсолютного значения неожиданного расстояния.
Это $$ 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)| $$
Поэтому для вопроса в исходном сообщении у нас есть
$$Nl(f) = 2^{0} - |1| = 0$$
В качестве альтернативы, на странице 20 здесь ( ссылка alt ) предлагается действовать следующим образом: После нахождения быстрого преобразования Уолша,
Добавить $2^{k-1}$для каждой записи в строке, кроме первой записи. Это дает нам новую строку, назовите ее$FHT'$
Если запись меньше, чем $2^{k-1}$он остается без изменений. В противном случае, если запись$FHT'$ больше, чем $2^{k-1}$ затем вычтите это из $2^k$.
Наконец, нелинейность - наименьший из этих регулируемых элементов.
2. Если мы используем быстрое преобразование Уолша для булевых функций, состоящих из $\{1,-1\}$ то формула нелинейности имеет вид
$$ Nl(f) = 2^{k-1} - \dfrac12 \cdot\max_{a\in\mathbb{F}_2^{2^k}} |W_f(a)| $$
Потому что
Использование реальных ценностей $\{1,-1\}$ удваивает величину и меняет знак результатов FWT
Источник