Утверждение (которое я нигде не могу найти в ответах на связанный вопрос) неверно. Постоянная функция не может быть однонаправленной. Чтобы понять почему, давайте вспомним определение односторонней функции.
Функция $f : \{0,1\}^* \к \{0,1\}^*$ является односторонним, если
- Существует полиномиальный алгоритм времени $M_f$ такой, что $M_f(x) = f(x)$ для всех $х\в\{0,1\}^*$.
- Для каждого алгоритма PPT $\mathcal{А}$ существует пренебрежимо малая функция $\mathsf{negl}$ такой, что для всех $\каппа\в\mathbb{N}$ он считает, что
$$\Pr[x\gets\{0,1\}^\каппа, y:=f(x)\;:\;f(\mathcal{A}(1^\kappa,y))=y] \leq \mathsf{negl}(\каппа)$$
Однако для любой постоянной функции легко указать алгоритм PPT $\mathcal{А}$ для которого
$$\Pr_{x\gets\{0,1\}^\каппа}\bigl[f\bigl(\mathcal{A}(1^\kappa,f(x))\bigr)=f(x) \bigr] = 1$$
для всех $\каппа\в\mathbb{N}$.
Например, мы можем определить $\mathcal{А}$ как алгоритм, который всегда выводит $1^\каппа$. то есть для всех $x\in\{0,1\}^\каппа$ у нас есть $f\bigl(\mathcal{A}(1^\каппа,f(x))\bigr) = f(1^\каппа)$ а так как функция $f$ постоянна, она выполняется для всех $x\in\{0,1\}^\каппа$ что $f(1^\каппа) = f(x)$. Таким образом $\mathcal{А}$ ломает односторонность $f$ с вероятностью $1$ и $f$ не является односторонним.
