problem:
-
$f$는 one-way function이다.
-
$g(x_1, x_2) = (f(x_1), x_2)$ where $|x_1| = |x_2|$.
$g$가 one-way function임을 보여라.
proof.
$f$가 one-way function이라면, $x$에 대해 $(f(x), |x|)$를 받았을 때 $f(x') = f(x)$를 만족시키는 $x'$을 non-negligible한 확률로 구해내는 adversary $\mathcal A$는 존재하지 않는다.
가정 1. $g$가 one-way function이 아니라고 가정한다.
가정에 의해 $(x_1, x_2)$에 대해 $((f(x_1), x_2), |x_1|)$를 받았을 때 $(f(x_1'), x_2') = (f(x_1), x_2)$를 만족시키는 $(x_1', x_2')$을 non-negligible한 확률로 구해내는 adversary $\mathcal B$가 존재한다.
다음과 같은 adversary $\mathcal A'$을 구성한다.
-
$(y, n)$을 입력받는다.
- 내부적으로 adverary $\mathcal B$를 $\mathcal B((y, y), n) = (x', z)$와 같이 호출한다.
-
$x'$을 반환한다.
$x'$은 non-negligible한 확률로 $f(x') = y$를 만족시킨다. 따라서, $\mathcal A'$은 $f$를 역산할 수 있으며, 이는 $f$가 one-way function이라는 사실과 모순된다.
가정1. 에서 모순이 발견되었으므로 $g$는 one-way function이다.