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

Хэш-функция, создающая циклы с ожидаемой максимальной длиной

флаг nc
Marcin Król

Есть ли известная хэш-функция $H_k: от X\к X$ так что: $\forall{x\in{X}},\exists{n\in{\mathbb{N}}}, n<k \land H^n(x)=x$

=== РЕДАКТИРОВАТЬ ===

К хэш-функция Я имею в виду, что любой другой способ нахождения прообраза $х \в X$ чем повторение $H_k$ вычислимо невыполнимо или, по крайней мере, значительно сложнее.

Моей мотивацией является использование такой функции, как последовательный POW.

44
0 + 0
fgrieu avatar
флаг ng
fgrieu
Какое именно определение «хеш-функции» вы используете? Если мы игнорируем "хэш", очевидным примером является $H_k$ функция идентификации. Подсказка: докажите, что любое такое $H_k$ является перестановкой множества $X$, а значит, абсолютно устойчиво к коллизиям, и что (первый и единственный) прообраз любого $x\in X$ можно найти с не более чем $k- 1$ оценок $H_k$, что ограничивает устойчивость к прообразу. Но если $k$ и $|C|$ могут расти экспоненциально с параметром безопасности для сопротивления прообразу, возможно, мы сможем создать кандидата $H_k$. Для полного ответа убедите нас, что это не домашнее задание, или вы над ним работали.
2
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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