Является ли эта конструкция OWF?

Подсказка: пусть $G'$ будет PRG. Тогда $G$, определяемый как $G(x_1\|x_2) = G(x_1)||x_2$ для достаточно длинного $x_1$, также является PRG.

@Maeher достаточно долго =?

@kelalaka Подойдет любая постоянная дробь. Скажем, 1/2 входной длины для бетонной конструкции.

@Maeher, я должен построить контрпример с твоей подсказкой?

Это может сработать.

@Maeher, я думаю, что на основе вашей подсказки мы можем построить функцию $f^*(x_1||x_2) = f(G'(x_1)||x_2 \oplus (0^{\lambda}||x1||x2 ))$ и если у нас есть $|G'(x_1)| = \lambda + |x1|$ мы также имеем, что вторая часть входа $f$ всегда равна нулю (из-за xor). Следовательно, вероятность нахождения прообраза $f^*$ ограничена выбором $x_1$ в этом случае. Но нам нужен достаточно большой $x_1$, чтобы иметь PRG... Учитывая $|x_1|=\lambda/2$, как в вашем примере, у нас все еще есть вероятность найти прообраз $2^{-\lambda /2}$, которым можно пренебречь.

Вы уверены, что параметры? делает $f^*$ из $2\lambda$ или $\lambda$, так как $G$ из $\lambda$. Также @Maeher хотел написать $G(x_1\|x_2) = G'(x_1)||x_2$, что является конструкцией для жалкого примера $PRG$ в ....

@kelalaka $f*$ принимает на вход длину $\lambda$, которая может быть $x_1||x_2$. Но я не понимаю, где может быть контрпример, учитывая, что $G(x_1||x_2) = G'(x_1)||x_2 безопасно для достаточно больших $x_1$.

Подсказка 2: гарантированно трудно инвертировать OWF только в том случае, если входные данные отбираются в соответствии с равномерным распределением. Распределение, которое содержит только входные данные, оканчивающиеся на множество нулей, очень далеко (и легко отличимо от) однородного.

Поэтому я подумал о создании «тупого» OWF $f'(x) $, который в случае, если последние биты $\lambda$ его ввода равны нулю, выводит сам ввод или, в противном случае, нормальный вывод $f$. Функция по-прежнему должна быть OWF, потому что вероятность случайного ввода, заканчивающегося на $0^{\lambda}$, равна $2^{-\lambda}$ и, следовательно, незначительна. Но даже если злоумышленник увидит $G'(x)\oplus(0^{\lambda}||x)$, что он может с этим сделать? Как он может вычесть $x$? (Кстати, большое спасибо за помощь!)

Есть и другие способы, с помощью которых OWF может вести себя глупо. Помните, вам не нужно находить $x$. Вам просто нужно найти *прообраз*, а не *тот же* прообраз.

Думаю, я понял! Я строю OWF $f'$, который возвращает $1^{2\lambda}$, если последние ${\lambda/2}$ биты входных данных равны $0$, а на выходе нормального OWF $f$ в противном случае. $f'$ является OWF, потому что вероятность случайного ввода, оканчивающегося на $0^{\lambda/2}$, равна $2^{-\lambda/2}$, но конструкцию $f*$ можно легко сломать, поскольку Злоумышленник всегда будет получать $1^{2\lambda}$, поэтому для победы ему достаточно отправить прообраз, оканчивающийся битами $0^{\lambda/2}$. Это правильно?

Ваш контрпример должен сработать. Хорошей практикой является запись доказательств того, что построенные вами $f$ и $G$ на самом деле являются безопасными OWF и PRG соответственно. Ваша атака тоже работает, но более специфична, чем необходимо. $f^*(x_1\|x_2) = f(G(x_1\|x_2)\oplus(0^\lambda\|x_1\|x_2) = f((G'(x_1)\|x_2)\oplus( 0^\lambda\|x_1\|x_2) = f((G'(x_1)\oplus 0^\lambda\|x_1) \|0^{\lambda/2}) = 1^{2\lambda}$ поэтому $f^*$ является *константной* функцией и *любое* значение $2\lambda$ является допустимым прообразом.

Этот вопрос на других языках: