Предположим, что существует односторонняя функция. Покажите, что существует односторонняя функция, ни один из входных битов которой не является хардкорным.

Я только что выучил определение хардкорного бита, и у меня нет интуиции на этот счет. Я хочу знать, каковы возможные подходы к этой проблеме.

Я получаю хорошую идею от моего одноклассника.

Предположим, что $f:\{0,1\}^n\to\{0,1\}^m$ является однонаправленной функцией.

Построим еще одну одностороннюю функцию $F:\{0,1\}^{n+1+\log(n+1)}\to\{0,1\}^{m+\log(n+1)+1}$ : Для входа $x=x_0x_1\cdots x_{n-1}x_n||s$, куда $s\in\{0,1,2,\cdots,n\}$ это $\лог(n+1)$-битовая строка, мы имеем $$ F(x)=f(x_0x_1\cdots x_{s-1}x_{s+1}\cdots x_n)||s||x_s $$ Тогда мы можем доказать, что $F$ является односторонней функцией, ни один из входных битов которой не является хардкорным битом.