6.19 풀이

(a)

우선, $({\rm Gen}_H,{\cal MT}_t)$에 대해 다음과 같은 실험 $\text{MT-coll}_{\mathcal A,({\rm Gen}_H,{\cal MT}_t)}(n)$ 을 정의한다:

1. 키를 $s \gets {\rm Gen}_H(1^n)$ 로 생성한다.

2. adversary $\mathcal A$는 $s$를 받고 $(x_1, x_2, x_3, \dots, x_t)$와 $(x'_1, x'_2, x'_3, \dots, x'_t)$를 반환한다.

3. 실험의 결과는 ${\cal MT}^s(x_1, x_2, x_3, \dots, x_t) = {\cal MT}^s(x'_1, x'_2, x'_3, \dots, x'_t)$인 경우 1로 정의된다.

모든 PPT adversary $\mathcal A$에 대해 다음을 만족하는 negligible한 함수 ${\rm negl}$이 항상 존재한다면, $({\rm Gen}_H,{\cal MT}_t)$는 collision-resistant하다.

$$P(\text{MT-coll}_{\mathcal A,({\rm Gen}_H,{\cal MT}_t)}(n) = 1) \leq {\rm negl}(n)$$

(b)

총 두 개의 party가 있다. 각각 클라이언트($\mathcal C$), 서버($\mathcal S$)로 명명한다. 클라이언트는 유일하다고 가정한다.

1. 아래 두 조건을 모두 만족시키는 파일 $x_1, x_2, x_3, \dots, x_t$를 생각한다.

   1. $t$는 power of two.

   2. $|x_i| = 2n$.

2. 클라이언트 $\mathcal C$에서 키 $s \gets {\rm Gen}_H(1^n)$를 생성한다.

3. $h_{i \dots i} = H^s(x_i)$ 로 정의한다.

4. $h_{i \dots j} = H^s(h_{i \dots (i + j) / 2} || h_{(i + j) / 2 + 1 \dots j}) \quad (\text{where } i \neq j)$ 로 정의한다.

5. $h_{1 \dots t}$ 를 구한다.

6. 클라이언트 $\mathcal C$의 키 $s$를 서버 $\mathcal S$에 전달한다.

7. 클라이언트 $\mathcal C$의 파일 $x_1, x_2, x_3, \dots, x_t$를 서버 $\mathcal S$에 전달한다.

8. 파일 $x_1, x_2, x_3, \dots, x_t$를 클라이언트 $\mathcal C$에서 제거한다.

파일 검증 과정 $\text{MT-vrfy}(h_{1 \dots t}, x_i, \pi_i)$:

1. 서버 $\mathcal S$가 클라이언트 $\mathcal C$에 $(x_i, \pi_i)$를 전달한다. $\pi_i$는 길이 $(\log t) - 1$짜리 튜플로, 각각의 $h'_{j \dots k}$가 담겨 있다.

2. 위의 3, 4번 과정을 통해 $h'_{1 \dots t}$를 구한다.

3. 클라이언트 $\mathcal C$의 $h_{1 \dots t}$가 $h'_{1 \dots t}$와 같다면, $\text{MT-vrfy}(h_{1 \dots t}, x_i, \pi_i) = 1$을 반환한다.

(c)

우선, ${\cal MT}_t$의 충돌이 항상 내부 해시 $H$의 충돌을 imply함을 보이자.

어떤 두 $x = (x_1, x_2, x_3, \dots, x_t)$와 $x' = (x'_1, x'_2, x'_3, \dots, x'_t)$이 서로 충돌한다고 하자.

가정에 의해 $x \neq x'$이어야 하기에 두 순서쌍 중 적어도 한 쌍의 $i \leq t$번째 $x_i$랑 $x'_i$는 달라야 한다.$\quad\dots (1)$

이제 $x_i$가 계산 과정에 들어가는 모든 $h$를 찾아서 $h_{j \dots k} = h'_{j \dots k} \quad (\forall j \leq i \leq k)$ 라고 가정하자. 이 가정이 참이라면, $x_i \neq x'_i$에 대해 $H^s$가 $h_{i \dots i} = h'_{i \dots i}$를 반환했다는 것이므로 $H$의 충돌이다.

위 가정이 거짓이라고 가정하자. 그렇다면 적어도 하나의 $h_{j \dots k} \neq h'_{j \dots k}$ 를 발생시키는 $j,k$가 존재한다. 이제 $(1)$로 돌아가 서로 다른 $x_i, x'_i$ 대신 $h_{j \dots k}, h'_{j \dots k}$를 집어넣고 $(j, k)$가 $(1, t)$이게 될 때까지 반복한다.

가정에 의해 $x$와 $x'$은 충돌이 나므로 $h_{1 \dots 8} = h'_{1 \dots 8}$이다. 위 과정을 반복했을 때 여전히 $h_{j \dots k} \neq h'_{j \dots k}$라면 이는 모순이다. 따라서 충돌이 나지 않을 것이라는 가정은 부정되어야 한다. 따라서 $H^s$는 충돌이 발생한다.

이제 reduction과 귀류법을 사용해 증명할 수 있다.

먼저, $({\rm Gen}_H,{\cal MT}_t)$가 collision-resistant하지 않다고 가정하자. 가정에 의해, 어떤 PPT adversary $\mathcal A_{\cal MT}$가 존재해 ${\cal MT}_t(x_1, x_2, x_3, \dots, x_t) = {\cal MT}_t(x'_1, x'_2, x'_3, \dots, x'_t)$를 만족시키는 $(x_1, x_2, x_3, \dots, x_t), (x'_1, x'_2, x'_3, \dots, x'_t)$를 매우 빠르게 찾을 수 있다.

이를 이용해 또다른 adversary $\mathcal A_H$를 구성하자. $\mathcal A_H$는 내부적으로 $\mathcal A_{\cal MT}$를 호출하고, $\mathcal A_{\cal MT}$는 $\mathcal A_H$에게 $(x_1, x_2, x_3, \dots, x_t), (x'_1, x'_2, x'_3, \dots, x'_t)$를 반환한다. 이제 $\mathcal A_H$는 앞서 보인 것처럼 두 순서쌍에서 서로 다른 $x_i$를 찾고, 이를 거슬러 올라가면 $\mathcal O(\log n)$ 만에 $H^s(h_{j \dots k}) = H^s(h'_{j \dots k})$를 만족시키는 $h_{j \dots k} \neq h'_{j \dots k}$를 찾을 수 있다. 따라서 $\mathcal A_H$는 $(\text{Gen}_H, H)$의 충돌을 PPT안에 negligible하지 않은 확률로 찾을 수 있으므로 $(\text{Gen}_H, H)$는 collision-resistant하지 않다.

이는 $(\text{Gen}_H, H)$는 collision-resistant하다는 전제와 모순된다. 따라서 $({\rm Gen}_H,{\cal MT}_t)$는 collision-resistant하다.