Skip to content

Instantly share code, notes, and snippets.

@abiriadev
Created October 14, 2025 09:44
Show Gist options
  • Save abiriadev/4b17022065bb985f415a801aaa89dc3e to your computer and use it in GitHub Desktop.
Save abiriadev/4b17022065bb985f415a801aaa89dc3e to your computer and use it in GitHub Desktop.

problem:

  1. $f$는 one-way function이다.
  2. $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'$을 구성한다.

  1. $(y, n)$을 입력받는다.
  2. 내부적으로 adverary $\mathcal B$$\mathcal B((y, y), n) = (x', z)$와 같이 호출한다.
  3. $x'$을 반환한다.

$x'$은 non-negligible한 확률로 $f(x') = y$를 만족시킨다. 따라서, $\mathcal A'$$f$를 역산할 수 있으며, 이는 $f$가 one-way function이라는 사실과 모순된다.

가정1. 에서 모순이 발견되었으므로 $g$는 one-way function이다.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment