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

Односторонняя функция с фиксированной точкой

флаг ke
yankovs

Как часть упражнения в курсе криптографии, я хочу придумать одностороннюю функцию, для которой «легко» найти коллизию из заданного OWF. Чтобы добиться этого, я попробовал следующее: учитывая OWF $f$ (можно предположить, что он существует), построить $f'$ следующее: $$f'(x)=\begin{cases}f(y), &x=x^*\ f(x),& \text{else} \end{cases}$$ для некоторых $x^*,y\in \{0,1\}^*$. теперь противник может вывести эти два, когда его попросят найти столкновение в $f'$. Моя интуиция такова $f'$ все еще является OWF, потому что эта фиксированная точка пренебрежимо мала $f$ относительно сложности вычисления псевдообратного.

Имеет ли это смысл?

примечание: определение OWF, с которым я работаю, взято из википедия

45
0 + 0
Fractalice avatar
флаг in
Fractalice
Выглядит правильно! Хотя это не фиксированная точка (но вы можете легко ее сделать).
2
Ответить
kelalaka avatar
флаг in
kelalaka
Это должно быть похоже на $f'(x)=\begin{cases}x, &x=x^* \bmod n \ f(x),& \text{else} \end{cases}$, чтобы он исправил точка и столкновение...
1
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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