Почему нелинейность этой логической функции оценивается как $\frac12$?

Dec 17 2020

Я использую метод, представленный в этой статье, чтобы найти нелинейность функции

$$ 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. Вычисление нелинейности булевых функций с преобразованием Уолша-Адамара Педро Мигель Соса
  2. Измерение нелинейности булевой функции с помощью преобразования Уолша Терри Риттер

Ответы

4 kodlu Dec 18 2020 at 05:12

В этой формулировке вам нужно преобразовать выходной диапазон вашей функции в $\{-1,+1\}$ через $$f`(x)=(-1)^{f(x)}$$ и примените Уолша Адамара к новой функции $f`(x)$. Использование формулы нуля или единицы означает, что вы отключены от константы, зависящей от количества переменных, поскольку

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

См. Мой ответ ниже о булевых функциях и криптографии, он может быть полезен с учетом ваших недавних вопросов.

Как булевы функции используются в криптографии?

2 E.Nole Dec 19 2020 at 03:31

Помимо ответа 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 ) предлагается действовать следующим образом: После нахождения быстрого преобразования Уолша,

  1. Добавить $2^{k-1}$для каждой записи в строке, кроме первой записи. Это дает нам новую строку, назовите ее$FHT'$

  2. Если запись меньше, чем $2^{k-1}$он остается без изменений. В противном случае, если запись$FHT'$ больше, чем $2^{k-1}$ затем вычтите это из $2^k$.

  3. Наконец, нелинейность - наименьший из этих регулируемых элементов.

2. Если мы используем быстрое преобразование Уолша для булевых функций, состоящих из $\{1,-1\}$ то формула нелинейности имеет вид

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

Потому что

Использование реальных ценностей $\{1,-1\}$ удваивает величину и меняет знак результатов FWT

Источник