Регистрация Войти
Рейтинг:1
avatar Crypto

Каковы алгебраические нормальные формы для каждого бита $z$, где $z = (x \oplus y) \oplus ((x \wedge y) \ll 1)$ (нелинейная операция в NORX)?

флаг de
lyrically wicked

Позволять $х, у, г$ обозначают три $n$-битные слова такие, что $$z = (x \oplus y) \oplus ((x \land y) \ll 1).$$

Статья NORX содержит обобщенное описание алгебраических нормальных форм для каждого бита $х$ данный $у$ и $z$: $$\begin{массив}{л} x_0 = (z_0 \oplus y_0),\ x_1 = (z_1 \oplus y_1) \oplus (x_0 \land y_0),\ \vdots\ x_i = (z_i \oplus y_i) \oplus (x_{i-1} \land y_{i-1}),\ \vdots\ x_{n-1} = (z_{n-1} \oplus y_{n-1}) \oplus (x_{n-2} \land y_{n-2}), \end{массив}$$

куда $w_i$ обозначает $я$-й бит слова $w \in \{x, y, z\}$.

Каково соответствующее обобщенное описание алгебраических нормальных форм для каждого бита $z$ данный $х$ и $у$?

98
1 + 0
Рейтинг:2
Fractalice avatar Crypto
флаг in
Fractalice

От $$x_i = z_i \oplus y_i \oplus (x_{i-1} \land y_{i-1})$$ мы получили $$z_i = x_i \oplus y_i \oplus (x_{i-1} \land y_{i-1}).$$

0 + 9
флаг de
lyrically wicked
Тогда мне интересно, почему в документе утверждается, что эта функция «на первый взгляд не является явно обратимой». Правда ли, что это треугольная [T-функция](https://en.m.wikipedia.org/wiki/T-функция) (а также сложение и вычитание)?
0
Ответить
Fractalice avatar
флаг in
Fractalice
Он треугольный, но словесного выражения для инверсии, как для сложения/вычитания, нет. Наверное, в этом причина.
0
Ответить
флаг de
lyrically wicked
Кажется, что обратная функция H в NORX треугольная, но сама функция H не является треугольной, потому что алгебраическая нормальная форма для $z_i$ _не_ зависит от каждого младшего значащего бита. Это правда?
0
Ответить
флаг pe
Samuel Neves
Это верно; отсутствие обратного с таким же количеством словесных операций, что и прямое направление, поэтому мы назвали это «неочевидным». И прямое, и обратное направления являются Т-функциями; Т-функция не должна включать каждый предыдущий бит, чтобы быть треугольной, она просто должна включать _исключительно_ предыдущие биты.
1
Ответить
флаг de
lyrically wicked
@SamuelNeves: «Т-функция не обязательно должна включать каждый предыдущий бит, чтобы быть треугольной» - это зависит от того, что подразумевается под словом «вовлекать». Согласно [этой статье в Википедии] (https://en.m.wikipedia.org/wiki/T-function), «если каждый младший бит включен в обновление каждого бита в состоянии, такой T- функция называется треугольной». Обратите внимание на формулировку: «каждый младший бит». [1/2]
0
Ответить
флаг de
lyrically wicked
@SamuelNeves: обратное направление функции H соответствует определению «треугольной», но прямое направление — нет, потому что ANF для $i$-го бита слова $x$ (т.е. обратное направление) содержит $x_{i -1}$, но АНФ для $i$-го бита слова $z$ (т.е. прямого направления) не содержит $z_{i-1}$. Правильно ли я понимаю «треугольность»? [2/2]
0
Ответить
флаг pe
Samuel Neves
Мне кажется немного глупым говорить о треугольных Т-функциях, поскольку Т уже означает треугольный. Я не совсем знаю, откуда статья в Википедии взяла это определение, поскольку я не помню, чтобы встречала его в литературе.
0
Ответить
флаг de
lyrically wicked
@SamuelNeves: раздел 4 статьи «Новый класс обратимых отображений» [A. Климов, А. Шамир] дает описание того, к чему относится название «Т-функция», и объясняет разницу между неявной триангуляцией и явной триангуляцией... Так что, возможно, «треугольная Т-функция» подразумевает «Т-функцию». функция, которая имеет явную треугольную форму"?
0
Ответить
флаг pe
Samuel Neves
Хорошо, насколько я могу судить, Википедия имеет гораздо более ограниченное определение Т-функции, что делает ее обратимой (это не обязательно так). То, что она называет Т-функцией, — это то, что обычно называют обратимой или биективной Т-функцией, а то, что она называет треугольной Т-функцией, — это то, что называют одноцикловой Т-функцией. Итак, NORX op является биективной Т-функцией, но точно не одноцикловой Т-функцией (при фиксации одного из аргументов).
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.