Я выполнял следующее упражнение из введения в современную криптографию от Каца и Линделла:
Позволять $F$ — сохраняющая длину псевдослучайная функция. Для следующих конструкций ключевой функции $F' : \{0,1\}^n \times \{0,1\}^{n-1} \rightarrow \{0,1\}^{2n}$, укажите, является ли $F'$ является псевдослучайной функцией. Если да, докажите это; если нет, покажите атаку.
(г) $F'_k(x) \stackrel{def}{=} F_k(0||x) || F_k(x||1)$
Я понимаю, что в этом случае $F'_k$ не является псевдослучайной функцией, поскольку мы могли бы эффективно и с немалой вероятностью различить $F'$ из случайной функции, запросив $х = 0^{n-2}||1$ и $х = 0^{n-1}$, и проверяя, является ли крайний левый $n$ биты первого запроса равны самому правому $n$ биты второго запроса.
Впрочем, я мог бы также предположить и противника $А$ что отличает $F'$ из случайной функции и использовать ее как подпрограмму для атаки $F$. На любой запрос $х$ от $А$, я запрашиваю $0||х$ и $х||1$, объединить результаты и вернуть их $А$. Что бы ни $А$ ответы, это был бы мой ответ.
К сожалению, я не могу объяснить, почему доказательство неверно. Может потому, что маловероятно, что я смогу использовать результат из $А$ сломать $F$? Но как мне формализовать это, если я ничего не знаю о $А$?
