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

Докажите, что функция G не является псевдослучайным генератором.

флаг de
archie09

Функция G(x) = x || x (где â||â обозначает конкатенацию строк). Дано, что G не является псевдослучайным генератором. Может кто-нибудь описать, как мы можем это доказать. Я немного запутался в концепции псевдослучайного генератора.

Что я понял до сих пор. Формальное определение псевдослучайного генератора дается как $\Pr[PRG_{A,G(n)} = 1] ≥ 1/2 + negl(n)$. Здесь мы можем заметить, что для этой функции G выходные данные будут иметь равные первую и вторую половины. Как использовать это с формальным определением, чтобы доказать, что G небезопасна?

92
0 + 0
Maarten Bodewes avatar
флаг in
Maarten Bodewes
Как указано, это все еще задание без четкого указания усилий. Пожалуйста, [отредактируйте] вопрос, чтобы включить свои рассуждения; это не обязательно должно быть правильно, это просто должно быть *здесь*.
4
Ответить
Marc Ilunga avatar
флаг tr
Marc Ilunga
Добро пожаловать в Crypto.SE! Полезным подходом здесь было бы записать определение PRG и гарантии безопасности такого объекта. Отсюда, может быть, видно, почему не работает именно этот экземпляр? Это также может помочь при корректном редактировании комментария (см. первый комментарий).
2
Ответить
archie09 avatar
флаг de
archie09
Спасибо, что сообщили мне об этом. Я отредактировал вопрос. Был бы очень признателен за помощь с концепцией.
0
Ответить
fgrieu avatar
флаг ng
fgrieu
@ archie09: вы пропустили большую часть формального определения PRG.Как и домены ввода и вывода, возможно, это свойство расширения (некоторые источники пропускают это), и, конечно же, контекст формулы: что-то вроде «для любого вероятностного полиномиального алгоритма $\mathcal A$ существует пренебрежимо малое значение». функция $\mathrm{negl}$ такая, что..." В качестве относительно незначительной побочки я не узнаю формулу как формулу в определении PRG, которую я изучал, но, возможно, я использовал другую ссылку.
0
Ответить
archie09 avatar
флаг de
archie09
@fgrieu Не могли бы вы сказать мне хороший источник, на который я могу ссылаться для этого определения. Я пытался искать, но не смог правильно понять эту концепцию.
1
Ответить
Maarten Bodewes avatar
флаг in
Maarten Bodewes
В конце концов вы сможете каким-то образом доказать, что бит в выводе не имеет шанса 0,5 + $e$ быть равным 0 или 1, включая предыдущий вывод. Это должно быть легко, верно? Однако я не понимаю, как это сделать, учитывая только вероятность в определении, поэтому я оставлю вас сделать это формально.
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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