Рейтинг:0

PRG подразумевает доказательство OWF

флаг lk

введите описание изображения здесь У меня возникла идея этого доказательства, что, поскольку PRG расширяется от n до 2n, она не может проецироваться на все {0,1}^{2n}, а только на незначительную часть, которой мы можем злоупотреблять, чтобы сделать хорошее различение, просто говоря, если A удалось найти прообраз в X. Случайная строка из U2n, скорее всего, не имеет прообраза в X. Таким образом, мы можем отличить U2n от G(Un). Но я думаю, что плохо понимаю конструкцию f. Какова цель нашего y? Можем ли мы просто доказать это, используя f(x) := G(x)? Кроме того, почему переменная f? Если мы определим f таким образом, не должна ли она быть проекцией из 2n в 2n? Я что-то упускаю.

флаг cn
Используемое здесь определение OWF, вероятно, требует, чтобы функция сохраняла длину. Поскольку G расширяется, вам нужно дополнить ввод.
killertoge avatar
флаг lk
Хорошо, это имеет смысл. Я перескочил обратно на страницу 40: «В дальнейшем мы будем иметь дело только с односторонними функциями, которые являются регулярными по длине [...] в основном с функциями, сохраняющими длину». Я использую книгу Гольдрейха, чтобы читать доказательства, о которых наша лекция не говорит, поэтому я должен быть более осторожным. Спасибо.
kodlu avatar
флаг sa
Ваш вопрос больно читать. Пожалуйста, используйте матжакс
killertoge avatar
флаг lk
@kodlu В настоящее время я немного изучаю латекс, я обязательно попытаюсь использовать его в своем следующем вопросе.

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

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