Schnorr's Protocol & Signature

Dan Boneh와 Victor Shoup의 암호학 책 toc.cryptobook.us/book.pdf의 19장의 첫 부분을 정리한다. 어느 정도 사전지식을 가정한다.

글을 읽기 전에, 이 블로그에 있는 이 글의 앞부분과 Matthew Green의 이 글을 읽고 오는 것을 추천한다. 

이 글의 목표는 다음 내용들을 어느 정도 완전하게 정리하는 것이다. 직관만으로 넘기지 않고 formal 하게 다 증명하는 것이 목표.

가장 대표적이고 기초적인 zero-knowlege proof 중 하나지만 이 글의 포인트는 ZK와 거리가 있다. 

Schnorr's Protocol의 HVZK는 보이는 것이 어렵지 않기 때문인데, HVZK 대신 아예 ZK로 넘어가면 더욱 난이도가 있을 것 같다.

 

이 글의 모든 random은 uniform random이다. 이 글의 목표는 다음과 같다.

• Schnorr's Protocol의 안전성과 HVZK, Rewinding Lemma
• Schnorr's Signature와 그 안전성, Fiat-Shamir Heuristic

 

1. Schnorr's Protocol의 안전성과 HVZK, Rewinding Lemma

기본적인 context를 위하여, Identification Protocol을 생각해보자. 이 Protocol에서는 기본적으로 두 사람, Prover와 Verifier가 있다.

Prover는 자신이 비밀키 $sk$를 가지고 있음을 인증키 $vk$를 소유하고 있는 Verifier에게 증명하려고 한다.

이 둘은 서로 대화를 하면서 정보를 교환하고, 최종적으로는 Verifier가 Prover의 증명을 accept 하거나 reject 한다.

 

이 Protocol이 유용하고 안전하려면, 여러 가지 시나리오를 고려해야 한다.

• $sk$를 가지고 있는 Honest Prover는 Verifier가 accept 하는 증명을 만들 수 있어야 한다.
• $sk$를 가지고 있지 않은 Malicious Prover가 Verifier가 accept 하는 증명을 만들 수 있으면 안된다.
• Prover와 Verifier의 대화를 엿듣는 Eavesdropper가 $sk$에 대한 추가적인 정보를 복원할 수 있으면 안된다.

물론, ~~를 할 수 있다는 것은 모두 효율적인 시간 내에 가능하다는 것이다. 위 성질들을 순서대로 Completeness, Soundness, Zero-Knowledge라고 한다. 특히, 세 번째 성질은 Verifier도 $sk$에 대한 정보를 얻을 수 없다는 것을 의미한다. 이들을 어떻게 formalize 하는지는 Schnorr's Protocol을 보며 설명한다.

 

Schnorr's Protocol

Cyclic Group $\mathbb{G} = \langle g \rangle$ of prime order $q$를 하나 준비한다. Prover의 비밀키는 $sk = \alpha \in \mathbb{Z}_q$, Verifier의 공개 인증키는 $vk = u = g^\alpha \in \mathbb{G}$이다.

이제 증명을 위해서 Prover와 Verifier는 다음과 같은 과정을 거친다. $\mathcal{C}$를 $\mathbb{Z}_q$의 subset이라 하자.

• 1. Prover는 random $\alpha_t \in \mathbb{Z}_q$를 고르고, $u_t = g^{\alpha_t}$를 계산한다. $u_t$를 Verifier에게 보낸다.
• 2. Verifier는 random $c \in \mathcal{C}$를 고르고, 이를 Prover에게 보낸다. 이 값을 Challenge라고 한다.
• 3. Prover는 $\alpha_z = \alpha_t + \alpha c \in \mathbb{Z}_q$를 계산하고, Verifier에게 보낸다.
• 4. Verifier는 $g^{\alpha_z} = u_t \cdot u^c \in \mathbb{G}$인지 확인하고, 그에 맞춰 accept/reject.

이들이 서로에게 보내는 값인 $(u_t, c, \alpha_z) \in \mathbb{G} \times \mathcal{C} \times \mathbb{Z}_q$를 conversation이라 한다.

특히, 그 중 Verifier가 accept 하도록 하는, 즉 $g^{\alpha_z} = u_t \cdot u^c$인 conversation을 accepting conversation (for $u$)이라 한다.

 

Completeness는 자명하다. 말 그대로 대입만 해서 Honest Prover의 proof가 accept가 되는지만 보면 되기 때문이다.

이제 Soundness와 Zero-Knowledge를 (정확하게는 HVZK를) 보면 된다. 둘 다 상당히 재밌는 아이디어를 사용한다.

 

Soundness 증명 : 직관편

$\alpha$를 모르는 Malicious Prover가 증명을 시도한다고 하자. 그러면 Step 2에서 Verifier가 challenge $c$를 보내면, Malicious Prover는 $\alpha_t + \alpha c$의 값을 정확하게 반환해야 한다. 만약 Malicious Prover의 성공 확률이 높다면, Verifier가 다른 challenge $c'$을 보냈더라도 $\alpha_t + \alpha c'$의 값을 정확하게 반환할 수 있을 것이다. 그런데 애초에 $\alpha_t + \alpha c$와 $\alpha_t + \alpha c'$을 맞춘 시점에서 Malicious Prover는 간단한 연립방정식을 통해서 $\alpha$를 복원할 수 있다.

이는 결국, 직관적으로, "두 번 연속해서 증명에 성공할 수 있다면 Discrete Logarithm을 깰 수 있다"는 의미가 된다.

Discrete Logarithm이 어려운 문제라는 것은 우리의 기본적인 가정이다. 그러니 증명을 한 번 성공할 확률도 낮다는 것이 결론이고 직관적인 증명 끝.

 

Soundness 증명 : formal

빠르게 advantage라는 표현을 정립하고 가자. advantage란, 대강 "문제 효율적인 시간 안에 해결할 확률"이다.

예를 들어서, Discrete Logarithm 문제에 대한 advantage는 효율적인 시간 내에 DL을 구해낼 확률이다.

즉, Discrete Logarithm이 어렵다는 말은 사실 advantage가 negligible 하다는 말과 같다. 이 advantage로 많은 암호학 증명이 이루어진다.

 

정리 : $\mathbb{G}$ 위에서의 Discrete Logarithm이 어렵고, $N = |\mathcal{C}|$가 super-poly라면 이 Protocol은 Soundness를 갖는다.

특히, efficient adversary $\mathcal{A}$가 $sk$ 없이 Verifier가 accept 하는 증명을 만드는 문제에 대한 advantage를 $\epsilon$이라 한다면, $\mathbb{G}$ 위의 Discrete Logarithm을 advantage $\epsilon'$으로 해결하는 efficient adversary $\mathcal{B}$가 존재하여, $\epsilon' \ge \epsilon^2 - \epsilon / N$이 성립한다. 이를 정리하면, $$\epsilon \le \frac{1}{N} + \sqrt{\epsilon'}$$

직관적으로 말하면, [Protocol을 "직접 공격"으로 깰 수 있다면 Discrete Logarithm 문제도 풀 수 있다]는 의미가 되겠다. 

 

증명을 위해서는 위의 직관적인 증명을 엄밀하게 바꿔야 한다. 우리의 궁극적인 목표는 efficient adversary $\mathcal{B}$를 $\mathcal{A}$를 이용해서 만드는 것이다. 

이제부터 $\mathcal{B}$의 입장에서 설명을 한다. 우리는 $\mathcal{A}$의 알고리즘을 모르지만 알고 있다. 이게 무슨 뜻이냐면,

• 애초에 $\mathcal{A}$의 존재 자체가 증명을 위한 하나의 가정이니, $\mathcal{A}$의 알고리즘은 모른다.
• 하지만 $\mathcal{B}$를 construct 하는 입장에서, 우리는 $\mathcal{A}$의 알고리즘을 적극적으로 사용할 수 있다.

이제 다음과 같은 과정을 거치자.

• 우리는 $\mathcal{A}$를 위한 Verifier 행세를 할 것이다. 첫 단계처럼, $\mathcal{A}$에게 $u_t$를 받는다.
• 이제 우리가 Challenge를 줄 차례다. 그러니 $c_1 \in \mathbb{Z}_q$를 하나 전달하자. $\mathcal{A}$가 $\alpha_{z_1}$을 줄 것이다. 이게 맞는지 판단하자.
• 이제 $\mathcal{A}$의 내부 상태를 Challenge를 주기 전 상태로 Rewind 하자. 이 부분이 핵심인데, 이게 가능한 이유는 우리가 $\mathcal{A}$의 알고리즘을 알고 있기 때문이다. $\mathcal{B}$와 $\mathcal{A}$가 서로 "싸우고 있는" 두 사람인 게 아니라, Protocol을 깨기 위해서 서로 역할극을 하고 있는 기계임에 집중하자. 이렇게 생각하면 앞선 직관적인 증명에서 우리가 사용한 일종의 시간여행과 what if 형태의 증명이 더욱 이해가 잘 되고 엄밀해진다. 최소한 나한테는 그랬다 ㅋㅋ
• 다시 Challenge를 줄 차례다. 그러니 $c_2 \in \mathbb{Z}_q$를 하나 전달하자. $\mathcal{A}$가 $\alpha_{z_2}$를 줄 것이다. 이게 맞는지 판단하자.
• 직관적인 증명에서도 언급했지만, 두 번 연속 accept가 뜨고 $c_1 \neq c_2$면 Discrete Logarithm이 깨진다.

그러니, 우리가 볼 확률은 "두 번 연속 accept가 뜨고 $c_1 \neq c_2$일 확률"이다. 이 확률의 lower bound를 구하면 되겠다.

 

이를 위해서 사용하는 정리가 Rewinding Lemma다. 사실 이거 보고 싶어서 책을 읽기 시작한 것이다 ㅎㅎ..

 

정리 (Rewinding Lemma) : $S, T$는 finite nonempty set이고 $f : S \times T \rightarrow \{0, 1\}$은 random function이다. 즉, $S \times T$의 원소가 input으로 들어오면 $0$ 또는 $1$을 그 원소에 대해 정해진 확률로 뽑아내는 함수이다. 이제 $X, Y, Y'$가 mutually independent random variable이고 $X$는 $S$ 위의 random variable, $Y, Y'$은 $T$ 위의 uniform random variable이라 하자. 이때, $\epsilon = P(f(X, Y) = 1)$이라 하고, $N = |T|$라 하자. 그러면 $$P(f(X, Y) = f(X, Y') = 1, Y \neq Y') \ge \epsilon^2 - \epsilon / N$$

 

첨언하자면, 원래 책에서는 $f$를 random function이 아니라 그냥 function으로 둔다. 하지만 개인적인 생각으로 이 context에서 $f$를 그냥 function으로 두면 안된다고 생각한다. adversary $\mathcal{A}$가 challenge $c$를 받은 뒤에도 확률적인 알고리즘을 사용할 수 있기 때문이다. 하지만 증명은 책처럼 그냥 계산이다.

 

정리 증명 : $p_x$를 $P(X = x)$라고 하고, $p_{xy}$를 $f(x, y) = 1$일 확률이라고 하자. (기존 증명에서는 $p_{xy}$가 0 or 1)

먼저 $s_x = \sum_{y \in T} p_{xy}$라 정의하면, $\epsilon N = \sum_{x \in S} p_x s_x$이 성립함은 정의상 자명하다. 이제 $$ P(f(X, Y) = f(X, Y') = 1, Y \neq Y') \ge \frac{1}{N^2} \sum_{x \in S} p_x (s_x^2 - s_x) \ge \frac{1}{N^2}((\epsilon N)^2 - \epsilon N) = \epsilon^2 - \epsilon / N$$을 얻는다. 첫 부등식은 단순 식 전개와 $0 \le p_{xy} \le 1$이므로 $p_{xy}^2 \le p_{xy}$가 성립함에서 얻어진다. 두 번째 부등식은 Cauchy-Schwarz에서 얻어진다.

 

이제 $S$를 $\alpha, u, u_t$ 등의 선택을 이루는 집합, $T$를 challenge space라고 하고, $f$값이 $1$이 나오는 것을 accept에 대응시키자.

그러면 모든 context가 정확하게 일치하고, 결국 $\epsilon' \ge \epsilon^2 - \epsilon / N$을 얻는다. 여기서 $\epsilon \le 1/N + \sqrt{\epsilon'}$을 얻는 것은 단순 식 조작. 증명 끝.

 

Honest Verifier Zero-Knowledge

정의 : Protocol이 Honest Verifier Zero-Knowledge라는 (HVZK) 것은, $vk$를 input으로 받고 Honest Prover와 Honest Verifier이 만드는 accepting conversation의 분포를 정확히 따르는 output을 뽑아내는 효율적인 Simulator가 존재한다는 것이다. 이는 모든 정당한 $(vk, sk)$ 쌍에 대해 성립해야 한다. 

 

정의 자체가 formal 하니, 이 정의가 우리의 직관과 맞는 이유를 설명해야 한다.

이 정의의 의미는, accepting conversation처럼 보이는 걸 만들기 위해서 $vk$만 알아도 충분하다는 것이다.

이는 역으로 생각하면, accepting conversation을 보는 것으로는 $vk$를 넘어서는 다른 정보를 뽑기가 불가능하다는 것이다.

만약 가능하다면, $vk$로 accepting conversation을 simulate 한 후, 그 결과를 그대로 사용해서 정보를 뽑으면 된다.

그러니 "accepting conversation을 활용해서 뽑을 수 있는 정보는 $vk$로도 그대로 뽑을 수 있다". 우리가 원하는 것이다. 

 

결론 : 공격자 또는 Verifier가 accepting conversation을 듣더라도 $sk$에 대한 추가적인 정보를 얻을 수 없다.

 

결국 Schnorr's Protocol에서 우리가 필요한 것은 $g^{\alpha_z} = u_t \cdot u^c$이다.

Protocol 자체에서는 $u_t$를 고르고, $c$를 받은 다음 $\alpha_z$를 제출해야 했고, 이 순서 때문에 Discrete Logarithm의 지식이 필요했다.

그러나 accepting conversation을 뽑아내기 위해서는, 순서를 바꿔서 $\alpha_z$와 $c$를 고른 다음 $u_t$를 계산하면 된다.

이 두 방법이 뽑아내는 결과가 같은 확률분포를 따름은 자명하고, 결국 Schnorr's Protocol이 HVZK임을 얻는다.

이와 같이, Simulator를 하나 설계하는 방식으로 HVZK를 증명한다. 비슷한 컨셉으로 Statistical ZK도 존재한다.

이 경우는, Simulator가 뽑아내는 분포가 Prover-Verifier가 뽑는 분포와 "가까우면" (Statistical Distance) 된다.

 

 

2. Schnorr's Signature와 그 안전성, 그리고 Fiat-Shamir Heuristic

이제 우리는 Schnorr's Protocol을 Signature Scheme으로 바꾸는 작업을 할 것이다. 이를 위해서, Fiat-Shamir Heuristic을 동원한다.

나중에 보면 알겠지만, 이는 interactive한 Schnorr's Protocol을 non-interactive 하게 바꾸는 역할도 할 수 있다.

 

Schnorr's Signature

그대로 비밀키는 $sk = \alpha$, 공개키는 $pk = u = g^{\alpha} \in \mathbb{G}$다. 해시 함수 $H : \mathcal{M} \times \mathbb{G} \rightarrow \mathcal{C}$를 하나 준비한다.

메시지 $m \in \mathcal{M}$을 서명하고 싶다면, 랜덤한 $\alpha_t \in \mathbb{Z}_q$를 고르고, $u_t = g^{\alpha_t}$를 계산한다.

그 후, $c = H(m, u_t)$를 계산한 다음, $\alpha_z = \alpha_t + \alpha c \in \mathbb{Z}_q$를 계산한다. 최종 서명은 $(u_t, \alpha_z)$가 된다. 

 

이제 이 서명을 Verify하려면, $m$과 그 서명 $(u_t, \alpha_z)$를 받고 $c = H(m, u_t)$을 계산한 다음, $g^{\alpha_z} = u_t \cdot u^c$인지 확인하면 된다.

이 과정은 공개키를 알고 있는 사람이면 할 수 있다. 핵심은 challenge를 해시 함수로 고른다는 것이다. 그리고 이게 Fiat-Shamir Heuristic이다.

 

Schnorr Signature's Security, Fiat-Shamir Heuristic : 직관

직관적으로는 해시 함수가 나오면 "아무것도 못하기 때문에", challenge를 해시로 잡나 완전히 랜덤으로 잡나 별 차이가 없을 것이다.

challenge가 정말 랜덤이면 서명을 만들기가 어렵다는 것을 이미 증명했으니, 해시를 어떻게 잘 비벼먹지 못한다면 이 서명 알고리즘도 안전할 것이다. 

암호학에서는 이처럼 "해시 함수가 나오면 아무것도 못한다"는 말을 formalize 하고, 하나의 model로 만들었다. 이를 Random Oracle Model이라고 한다.

상당히 사기같은 가정을 하나 깔고 가는데, 힘이 굉장히 강력하다. Random Oracle Model에 대한 고찰은 Matthew Green의 이 글 참고.

 

Random Oracle Model이란, 최소한 지금의 context에서는, 해시 함수 $H$를 하나의 Random Oracle로 보자는 것이다.

Random Oracle이란, 각 input에 대해서 output을 uniform random하게 뽑아내는 black-box이다.

단, 동일한 input이 이전에 들어왔다면, 이전에 뱉은 output을 그대로 뱉는다. 함수를 input을 받아가면서 uniform random하게 제작한다고 생각하자.

 

이렇게 생각하면, 해시 함수가 정말 "나오면 아무것도 못하는" 대상이 된다. 이 가정을 깔아야 안전성을 증명할 수 있다.

 

Schnorr Signature's Security, Fiat-Shamir Heuristic  : formal proof

이제 엄밀한 증명을 시작하기 전에, Signature Scheme이 안전하다는 것이 무엇인지를 정의할 필요가 있다.

 

Signature Security Game : 우리의 adversary $\mathcal{A}$는

• $Q_s$개의 signing query를 보낼 수 있다. 즉, $m \in \mathcal{M}$을 보내서 그에 대한 정당한 서명을 얻는다.
• $Q_{ro}$개의 random oracle query를 보낼 수 있다. 즉, $H$에 대한 input을 보내서 그에 대한 output을 얻는다.

목표는 메시지 하나에 대한 정당한 서명을 만들어 내는 것이다. 단, signing query에서 보냈던 메시지와 달라야 한다.

이 문제에 대한 advantage가 작다는 것을 보이는 것이 우리의 목표가 되겠다. 증명을 위해서, 하나의 게임을 더 정의해야 한다.

 

$r$-impersonation Game : 다시 Identification Protocol로 돌아오자. 우리의 adversary $\mathcal{A}$는

• $r$명의 독립적인 Verifier와 동시에 대화할 수 있다. 그 중 아무 한 명에게 accept를 받는 증명을 만들면 성공. 

 

또한, 확률 계산을 편하게 하기 위해서 사용하는 보조정리를 몇 개 소개한다.

 

Difference Lemma : 사건 $W_0$와 $W_1$가 있다. 이때, 사건 $Z$가 있어 $W_0 \cap Z^C$가 발생하는 것이 $W_1 \cap Z^C$가 발생하는 것과 동치라면, $$ |P(W_0) - P(W_1)| \le P(Z)$$가 성립한다. 증명은 간단하다. $P(W_0 \cap Z^C) = P(W_1 \cap Z^C)$이므로, 결국 $$ |P(W_0) - P(W_1)| = |P(W_0 \cap Z) - P(W_1 \cap Z)| \le P(Z)$$

 

Union Bound : $P(A_1 \cup A_2 \cup \cdots \cup A_n) \le \sum_{i=1}^n P(A_i)$. 증명은 자명하므로 생략.

 

이제 본격적으로 증명을 하자. Singature Security => $r$-impersonation => Discrete Logarithm 순으로 증명을 한다.

 

Step 1 : $r$-impersonation에 대한 advantage의 upper bound를 구하자.

정리 (Forking Lemma) : $|\mathcal{C}| = N$이라 하자. efficient adversary $\mathcal{A}$가 $r$-impersonation을 advantage $\epsilon$으로 공격할 수 있다면, efficient adversary $\mathcal{B}$가 있어 $\mathbb{G}$ 위에서의 Discrete Logarithm 문제를 advantage $\epsilon'$으로 해결할 수 있다. 이때, $\epsilon' \ge \epsilon^2 / r - \epsilon / N$이 성립하고, 이를 정리하면 $$\epsilon \le r/N + \sqrt{r \epsilon'}$$

 

증명은 Schnorr's Protocol의 Soundness 증명과 크게 다르지 않다. $\mathcal{A}$가 승리하려면, 결국 $r$개의 Verifier 중 하나에게 accept를 얻어내야 한다.

이제 $i$번째 Verifier에게 accept를 얻어낼 확률을 $\epsilon_i$라 하면, 정의상 $\epsilon = \sum_{i=1}^r \epsilon_i$임이 자명하다. 이제 $\mathcal{A}$를 활용해서, $\mathcal{B}$를 제작해보자.

Soundness를 증명할 때와 같은 마음가짐으로 생각하자. 이제부터 우리는 $\mathcal{B}$의 입장에서 생각한다. 

• 우리는 우선 $\mathcal{A}$를 위해서 $r$개의 Verifier 역할을 모두 해줘야 한다. 
• $\mathcal{A}$ 역시 공개키 $u$는 알고 있는 상태다. $\mathcal{A}$에게 $u_t$들을 받자.
• 이제 $r$개의 challenge $c_1, c_2, \cdots , c_r$을 $\mathcal{A}$에게 순서대로 주자. 
• 그러면 $\mathcal{A}$가 그 $r$개의 challenge 중 하나에 대한 답을 줄 것이다. 이게 정당한지 확인을 하자.
• $\mathcal{A}$가 $i$번째 challenge에 대한 답을 줬다고 하자. "$i$번째 challenge $c_i$를 주기 전"으로 $\mathcal{A}$를 Rewind 하자.
• 우리는 $\mathcal{A}$에게 $i$번째 challenge로 $c_i$ 대신 새로운 random challenge $c'$을 준다.
• 그 후, $i+1, i+2, \cdots, r$번째 challenge는 기존의 challenge $c_{i+1}, \cdots , c_r$을 그대로 준다.
• 이제 다시 $\mathcal{A}$에게 $r$개의 challenge 중 하나에 대한 답을 받자. 이게 정당한지 확인을 하자.
• $\mathcal{A}$가 $i'$번째 challenge에 대한 답을 줬다고 하자. 이제 알고리즘 종료.

만약 $i = i'$이고 $c_i \neq c'$이라면, 연립방정식을 통해서 $\alpha$를 계산할 수 있을 것이다. 

이제 index $i$를 통해서 $\alpha$를 계산하는 것에 성공할 확률을 (얻는 advantage를) $\epsilon'$이라 하자. 그러면 Rewinding Lemma에 의해서 $$\epsilon'_i \ge \epsilon_i^2 - \epsilon_i / N$$이 성립한다. 자세하게 설명하자면, Rewinding Lemma에서 $T$를 $i$번째 challenge로 놓고, $S$를 나머지 선택 모두라고 설정한다.

또한, $f$ 값이 $1$인 것을 "$i$번째 challenge에서 accept가 나왔다"라는 것으로 둔다. 그러면 모든 context가 맞고 Rewinding Lemma를 적용할 수 있다.

 

이제 남은 것은 마무리다. $\epsilon' = \sum_{i=1}^r \epsilon'_i$임은 자명하므로, Cauchy-Schwarz 부등식에서 $$\epsilon' = \sum_{i=1}^r \epsilon'_i \ge \sum_{i=1}^r \epsilon_i^2 - \epsilon_i / N \ge \epsilon^2 / r - \epsilon / N$$이며, 간단한 식 조작으로 $\epsilon \le r/N + \sqrt{r\epsilon'}$을 얻을 수 있다. 증명 끝.

 

Step 2 : Signature Scheme을 깨는 것에 대한 advantage의 upper bound를 구하자.

정리 : $Q_s$개의 signing query와 $Q_{ro}$개의 random oracle query를 날릴 수 있는 efficient adversary $\mathcal{A}$가 Signature Scheme을 advantage $\epsilon$으로 깰 수 있다고 하자. 그러면, efficient adversary $\mathcal{B}$가 존재하여 $Q_{ro}+1$-impersonation을 advantage $\epsilon'$으로 성공할 수 있으며, 이때 $$\epsilon \le Q_s(Q_s + Q_{ro} + 1) / q + \epsilon'$$

 

증명의 핵심 아이디어는 "signing query는 Simulator로 대답해도 된다"와 "Verifier의 challenge를 그냥 random oracle의 결과값으로 넣어도 된다".

 

기본 가정을 하나 가져간다. 만약 adversary $\mathcal{A}$가 최종적으로 제출하는 서명이 $(m, u_t, \alpha_z)$라면, $(m, u_t)$에 대한 random oracle query를 이미 한 것으로 간주한다. random oracle query를 날려서 $\mathcal{A}$가 볼 수 있는 손해는 query 개수가 하나 줄어든다는 것 외에는 없다는 것은 자명하다. 그러니, adversary가 사용할 수 있는 random oracle query의 개수를 $Q_{ro} + 1$로 늘려주는 것으로 이 가정에 대한 보상을 해주도록 한다.

 

notation이 몇 개 필요하다. random oracle의 함수를 저장하기 위한 $Map : \mathcal{M} \times \mathbb{G} \rightarrow \mathcal{C}$와, random oracle query를 저장하기 위한 $Explicit : \mathcal{M} \times \mathbb{G} \rightarrow \mathbb{N}$을 정의한다. 이들의 구체적인 정의는 뒤에서 할 것이다. 이제 본격적으로 증명을 하자.

 

$\mathcal{A}$가 $\epsilon$ 이상의 advantage로 다음 게임을 이길 수 있음은 자명하다.

 

Detail 1 : Signing Query

• $i$번째 signing query로 메시지 $m_i$를 날리는 경우, 다음과 같은 알고리즘으로 생성된 대답을 받는다.
• $\alpha_{ti}$를 $\mathbb{Z}_q$에서 랜덤하게 고르고, $u_{ti} = g^{\alpha_{ti}}$를 계산한다. $c_i$ 역시 $\mathcal{C}$에서 랜덤하게 고른다.
• 만약 $(m_i, u_{ti})$가 Map의 domain에 있다면, $c_i = Map(m_i, u_{ti})$로 교체한다. - (*)
• $Map(m_i, u_{ti})$의 값을 $c_i$로 설정한다. 이제 $\alpha_{zi} = \alpha_{ti} + \alpha c_i \in \mathbb{Z}_q$를 계산하고, $(u_{ti}, \alpha_{zi})$를 반환.

Detail 2 : Random Oracle Query

• $j$번째 random oracle query로 $(\hat{m_j}, \hat{u_j})$를 날리는 경우, 다음과 같은 알고리즘으로 생성된 대답을 받는다.
• 만약 $(\hat{m_j}, \hat{u_j})$가 Map의 domain에 있다면, $Map(\hat{m_j}, \hat{u_j})$를 반환한다.
• 그렇지 않다면, $Explicit(\hat{m_j}, \hat{u_j}) = j$라고 하고 (받은 random oracle query의 index를 저장한다)
• $Map(\hat{m_j}, \hat{u_j})$의 값을 $\mathcal{C}$에서 random하게 고른 뒤, 이 값을 반환한다.

$\mathcal{A}$가 서명을 하나 제출한다. 이때 $(m, u_t)$는 Explicit의 domain에 속한다고 가정한다. 이게 정당한 서명이면 승리.

 

$\mathcal{A}$가 제출하는 최종 서명의 $(m, u_t)$ 값이 Explicit 배열의 domain에 속해야 한다는 것에 대한 보충설명을 한다. random oracle query에 $(m, u_t)$를 보내야 함은 이미 가정을 통해서, (그리고 $Q_{ro}$를 $Q_{ro}+1$로 대체하는 것으로) 알고 있는 사실이다. 그런데 이미 이 순서쌍이 Map의 domain에 있다면 문제가 생긴다. 하지만, Map의 domain에 속하려면 애초에 Explicit 배열 안에 들어있거나 (즉, 이전 random oracle query에서 $(m, u_t)$가 이미 들어왔다) signing query에서 Map의 domain에 $(m, u_t)$가 들어와야 한다. 그런데 signing query에서 $(m, u_t)$가 Map의 domain에 들어왔다는 것은 사실 $m$에 대한 signing query가 들어왔다는 것이다. 우리는 이미 signing query를 제출한 메시지들에 대한 서명 제작은 공격으로 간주하지 않으므로, 이 경우는 일어날 수 없다. 

 

이제 굵은 글씨로 쓴 (*) 부분을 생각하자. 여기서 $(m_i, u_{ti})$가 겹칠 확률은, 즉 (*) 부분에 도달할 확률을 얼마일까?

겹치려면 기본적으로 $\alpha_{ti}$의 값이 겹쳐야 한다. random oracle을 access 하는 총 횟수가 최대 $Q_s + Q_{ro} + 1$번이므로, 임의의 signing query에서 겹칠 확률은 $(Q_s+Q_{ro}+1)/q$ 이하이다. 또한, signing query가 총 $Q_s$번 있으니, Union Bound에 의하여 한 번이라도 (*)에 도달할 확률은 최대 $Q_s(Q_s+Q_{ro}+1)/q$가 된다. 여기서 Difference Lemma를 사용하면, (*) 부분의 알고리즘을 지워도 $\mathcal{A}$가 이 게임을 이길 확률이 (advantage) 최소 $$\epsilon - Q_s(Q_s+Q_{ro}+1)/q$$ 이상이 된다는 것을 얻는다. 이제부터 (*) 부분의 알고리즘을 지운 상태에서 생각한다.

 

중간 점검을 하자. $\mathcal{A}$는 다음 게임을 $\epsilon - Q_s(Q_s+Q_{ro}+1)/q$ 이상의 advantage로 이긴다.

 

Detail 1 : Signing Query

• $i$번째 signing query로 메시지 $m_i$를 날리는 경우, 다음과 같은 알고리즘으로 생성된 대답을 받는다.
• $\alpha_{ti}$를 $\mathbb{Z}_q$에서 랜덤하게 고르고, $u_{ti} = g^{\alpha_{ti}}$를 계산한다. $c_i$ 역시 $\mathcal{C}$에서 랜덤하게 고른다. 
• $Map(m_i, u_{ti})$의 값을 $c_i$로 설정한다. 이제 $\alpha_{zi} = \alpha_{ti} + \alpha c_i \in \mathbb{Z}_q$를 계산하고, $(u_{ti}, \alpha_{zi})$를 반환.

Detail 2 : Random Oracle Query

• $j$번째 random oracle query로 $(\hat{m_j}, \hat{u_j})$를 날리는 경우, 다음과 같은 알고리즘으로 생성된 대답을 받는다.
• 만약 $(\hat{m_j}, \hat{u_j})$가 Map의 domain에 있다면, $Map(\hat{m_j}, \hat{u_j})$를 반환한다.
• 그렇지 않다면, $Explicit(\hat{m_j}, \hat{u_j}) = j$라고 하고 (받은 random oracle query의 index를 저장한다)
• $Map(\hat{m_j}, \hat{u_j})$의 값을 $\mathcal{C}$에서 random하게 고른 뒤, 이 값을 반환한다.

이제 이 $\mathcal{A}$를 이용하여, $Q_{ro}+1$-impersonation을 성공시키는 $\mathcal{B}$를 제작하자.

$\mathcal{B}$는 $\mathcal{A}$를 위하여 두 종류의 쿼리를 답해야 하고, 동시에 $Q_{ro}+1$-impersonation도 진행해야 한다.

이제부터 우리는 $\mathcal{B}$ 입장에서 모든 것을 설명한다. 이제 이러한 사고방식이 익숙해졌을 것이라고 믿는다.

 

Detail 1 : Signing Query 대답하기

• $i$번째 signing query로 메시지 $m_i$를 받은 경우, 다음과 같은 알고리즘으로 생성된 대답을 보낸다.
• 이제 $(u_{ti}, c_i, \alpha_{zi})$를 accepting conversation에서 랜덤하게 뽑아도 된다. 이는 HVZK 성질에서 $\alpha$가 없어도 할 수 있다.
• $Map(m_i, u_{ti})$의 값을 $c_i$로 설정하고, $(u_{ti}, \alpha_{zi})$를 보낸다. 다시 한 번 강조하지만, 우리는 $\alpha$의 값이 필요가 없었다.
• 이렇게 해도 기존의 Signing Query의 대답 방식과 동일하다. 이것을 위해서 우리가 (*) 부분을 날린 것이다. 

Detail 2 : Random Oracle Query 대답하기

• $j$번째 random oracle query로 $(\hat{m_j}, \hat{u_j})$를 받은 경우, 다음과 같은 알고리즘으로 생성된 대답을 보낸다.
• 일단 $(\hat{m_j}, \hat{u_j})$가 이미 Map의 domain에 있다면, $Map(\hat{m_j}, \hat{u_j})$를 보내면 된다.
• 아이디어는, 여기서 Explicit하게 대답한 결과를 challenge로, (즉 해시 결과로) 하는 서명이 $\mathcal{A}$에게 나온다는 것이다.
• 그러니 $\mathcal{B}$는 새로운 Verifier $V_j$를 하나 불러서, $\hat{u_j}$를 보내고 challenge 값 $c_j$를 받는다. 
• 이제 Random Oracle 값을 $c_j$로 돌려준다. 즉, $Map(\hat{m_j}, \hat{u_j}) = c_j$라 한다. $c_j$ 역시 random이니 문제 없다.
• 만약 $\mathcal{A}$가 이에 대한 대답에 성공하면 그대로 $V_j$에게 제출하면 된다!!

즉, $(m, u_t, \alpha_z)$가 새로운 서명이라면, $(\hat{m_j}, \hat{u_j}) = (m, u_t)$인 $j$가 있을 것이고, $V_j$에 $\alpha_z$를 제출하면 성공.

 

그러니 $\epsilon' \ge \epsilon - Q_s(Q_s + Q_{ro} + 1)/q$로 성공하는 $r$-impersonation adversary를 제작하는 것에 성공했다.

 

즉, Signature를 깨는 adversary => $r$-impersonation을 깨는 adversary => Discrete Logarithm을 깨는 adversary를 차례대로 제작했다.

위 결과들을 전부 합치는 것으로 Discrete Logarithm이 어렵다는 가정 + Random Oracle Model에서 Schnorr's Signature의 안전성을 얻는다.

 

정리 : 이전 정리들의 notation을 그대로 가져온다. Signature Scheme을 $\epsilon$의 advantage로 깨는 efficient adversary $\mathcal{A}$가 있다면, Discrete Logarithm을 $\epsilon'$의 advantage로 해결하는 efficient adversary $\mathcal{B}$가 존재한다. 이때, 다음 식이 성립한다. (즉, DL이 어려우면 Signature를 깨는 것도 어렵다) $$\epsilon \le Q_s(Q_s+Q_{ro}+1)/q + (Q_{ro} + 1)/N + \sqrt{(Q_{ro}+1) \epsilon'}$$