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

Является ли PRF Xored (или умноженным) со случайным числом безопасным PRF?

флаг cn
zhuo chen

Я знаю, что PRF Xored с его ключом не является безопасным PRF. Затем мне интересно, что, если элемент Xored (или умноженный) является другим случайным числом. Формальное выражение выглядит следующим образом:

Позволять $F_k(x):\{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}^n$ быть ПРФ.

"$<<$" операция указывает на левое вращение, "$\cdot$" операция указывает на модуль двоичного умножения $2^n$ где $n$-битовая строка интерпретируется как число в $Z_{2^n}$ и "$(а, б)$"обозначает наибольший общий делитель $а$ и $b$.

Q1. Определять $F'_{k_1,k_2}(x) = F_{k_1}(x) \oplus k_2$, куда $k_2$ равномерно выбирается из $\{0,1\}^n$. Тогда это $F'_{k_1,k_2}(x)$ ПРФ?

Q2. Определять $F''_{k_1,k_2}(x) = (F_{k_1}(x)<<1) \oplus k_2$, куда $k_2$ равномерно выбирается из $\{0,1\}$. Тогда это $F''_{k_1,k_2}(x)$ ПРФ?

Q3. Определять $F'''_{k_1,k_2}(x) = k_2 \cdot F_{k_1}(x)$, куда $k_2$ равномерно выбирается из $\{0,1\}^{n-1}||1$, т.е. $(k_2,2^n) = 1$. Тогда это $F'''_{k_1,k_2}(x)$ ПРФ?

Я думаю, что это PRF, но я не понимаю, как это официально доказать. $k_2$ в Q.3 должно быть нечетным числом, так как если оно четное, то $F'''$ возвращает четное число и не может быть PRF.

119
0 + 0
флаг cn
Maeher
Относительно Q3: что там означает умножение? Мы там работаем $\pmod {2^{n}}$ что ли?
0
Ответить
zhuo chen avatar
флаг cn
zhuo chen
@Maeher Да, умножение указывает на двоичное умножение $\pmod {2^n}$ и работает в $Z_{2^n}$. Кроме того, $k_2$ и $F_{k_1}(x)$ интерпретируются как числа в $Z_{2^n}$. Извините за то, что описание умножения не очень понятно из-за типографики, и я отредактировал свою типографику.
0
Ответить
флаг cn
Maeher
Достаточным условием было бы то, что умножение $\bmod 2^n$ с нечетной константой является перестановкой над $\mathbb{Z}_{2^n}$. Интуитивно я бы сказал, что это правда, но сейчас мне не приходит в голову формальный аргумент.
0
Ответить
zhuo chen avatar
флаг cn
zhuo chen
@Maeher Да, я тоже так думаю, и я думаю, что именно сейчас нужно доказать, что $F'''$ является PRF. Знания, связанные с теорией чисел, могут быть полезны. Я попробую. Если у меня получится, я сообщу вам. Спасибо за помощь~
0
Ответить
zhuo chen avatar
флаг cn
zhuo chen
Если $A=\{a_1,a_2,\cdots, a_m\}$ является перестановкой, то $K=\{k \cdot a_1,k \cdot a_2,\cdots, k \cdot a_m\}$ также является перестановка над $Z_{2^n}$, где $k$ нечетно и $m \leq 2^n$. Доказательство. Предположим, что $K$ не является перестановкой и $k \cdot a_i \equiv k \cdot a_j \pmod {2^n}$ï¼, где $i,j \in [1, m]$. Тогда имеем $a_i \equiv a_j \pmod {2^n}$, так как $(k, 2^n)=1$, что противоречит предположению. Я прав? И аналогичен ли последующий процесс проверки Q3 Q1?
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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