Этот вопрос может быть связан с Вот этот, хотя конструкция отличается.
Рассмотрим PRF $f$. Мы определяем $g_k$ как $g_k(x)=f(x)\oplus f(x\oplus k)$. Является $g_k$ PRF, предполагая $к$ выбирается случайно?
Я попытался доказать это следующим образом. Рассмотрим противника $\mathcal{А}$ который способен различать $g_k$ и PRF с существенным преимуществом. Позволять $\mathcal{R}$ быть сокращением, которое имеет доступ к $\mathcal{А}$ и хочет нарушить безопасность PRF $f$. В обеих играх, $б=0$ обозначает реальный мир и $б=1$ случайный мир, где вместо $f$ или же $g_k$.
В начале игры, $\mathcal{R}$ выбирает $к$ случайно. Когда $\mathcal{А}$ запросы на $х$, $\mathcal{R}$ запросы на $х$ и $x\oплюс k$, XOR результат и отправить его обратно в $\mathcal{А}$. Когда $\mathcal{А}$ возвращает свою догадку $b'$, $\mathcal{R}$ возвращает тот же бит.
Чтобы доказать, что $\mathcal{R}$ имеет существенное преимущество, нам просто нужно показать, что он идеально имитирует оракул, реализующий $g_k$. В случае $б=0$, это так, ничем не отличается $\mathcal{R}$ от оракула, реализующего $g_k$. Если $б=1$ Однако, $\mathcal{А}$ рассчитывает получить $\пи(х)$ для случайной функции $\пи$, пока получает $\pi(x)\oplus\pi(x\oplus k)$. $\пи(х)$ равномерно случайна и по определению случайной функции не связана с $\пи(х\оплюс к)$, И что $\mathcal{R}$ возвращается в $\mathcal{А}$ также является равномерно случайным. Следует отметить, что теперь, когда $\пи$ был определен на $х$ и дальше $x\oплюс k$, $\mathcal{А}$ может предсказать стоимость шифрования $x\oплюс k$ так как это было бы то же самое, что $х$с. С $\mathcal{А}$ не знает $к$, это не возможная стратегия. Следовательно, $\mathcal{А}$ не может различить эти ситуации.
Верно ли это доказательство? Что меня беспокоит, так это то, что у этого нового PRF много коллизий, что довольно удивительно для PRF, но я думаю, что противник не может их найти, если не узнает $к$.
