저번 글에 이어서, 이번에는 19장의 내용을 끝까지 정리한다. 본격적으로 최적화 공부를 하기 위해서 이거 읽는 건 잠시 중단.

 

이번 글에서는 Schnorr's Protocol을 일반화한 Sigma Protocol에 대해서 다룬다. 이전 글을 읽고 왔다고 가정한다.

이 블로그에 있는 글인 Diophantine Argument of Knowledge와 같이 읽으면 좋을 것 같다. 내용이 꽤 많이 겹친다.

이 글에서도 모든 random은 uniform random이다. 이전 글의 앞부분에서 말한 모든 내용이 그대로 적용된다.

 

이 글의 내용은 다음과 같다.

  • Schnorr's Protocol을 일반화하여 Sigma Protocol을 얻고, 비슷하게 Signature Scheme도 얻는다. 이들에 대한 구체적인 정의와 사례들을 살펴보고, 그 안전성을 증명한다. Schnorr's Protocol을 다룰 때 사용되었던 방법들이 거의 그대로 등장하지만, 일반적인 상황을 다루기 위해 준비가 필요하다.
  • Sigma Protocol을 통해서 더욱 강력한 adversary의 공격에도 안전한 Protocol을 만드는 방법을 살펴본다. 우리는 지금까지 adversary가 Eavesdrop 하거나 Malicious Prover가 되는 경우만을 고려하였다. 이번에는 adversary가 Malicious Verifier의 역할을 하더라도 깨지지 않는 Protocol을 만든다.

 

1. Sigma Protcols : A Generalization of Schnorr's Protocol

Definitions

정의 : Effective Relation이란 binary relation $\mathcal{R} \subset \mathcal{X} \times \mathcal{Y}$로, 이때 $\mathcal{X}, \mathcal{Y}, \mathcal{R}$은 모두 efficiently recognizable set이다. (즉, 어떤 값이 집합의 원소인지를 쉽게 판별할 수 있다) $\mathcal{Y}$의 원소를 statement라고 하고, $(x, y) \in \mathcal{R}$이면 $x$를 $y$의 witness라고 정의한다. 

 

 

정의 : Sigma Protocol을 정의하기 위해서는 Effective Relation $\mathcal{R} \subset \mathcal{X} \times \mathcal{Y}$와 Prover, Verifier가 필요하다. 두 사람은 모두 $y \in \mathcal{Y}$를 갖고 있으며, Prover는 $y$에 대한 witness $x \in \mathcal{X}$에 대한 지식을 증명하려고 한다. 이들은 다음 구조를 갖는 대화를 통해서 Prover의 증명을 검토한다.

  • Prover는 commitment라고 불리는 값 $t$를 하나 계산해서 Verifier에게 전달한다.
  • Verifier는 challenge라고 불리는 값 $c$를 challenge space $\mathcal{C}$에서 random하게 골라 Prover에게 전달한다.
  • Prover는 response라고 불리는 값 $z$를 계산하여 Verifier에게 전달한다. 
  • 이제 Verifier는 conversation $(t, c, z)$를 이용하여 증명을 accept/reject 한다. 
  • Accept를 받는 conversation을 accepting conversation이라고 부른다. challenge space는 super-poly임을 가정한다.
  • 이미 Schnorr's Protocol에서 알고 있는 사실이지만, accepting conversation의 집합은 $y$에 dependent 함에 유의하라.

독자들은 Schnorr's Protocol이 Sigma Protocol의 한 경우임을 파악할 수 있을 것이다. 특히, 이 경우 $\mathcal{R}$은 결국 $(x, y)$ such that $g^x = y$이다.

 

 

우리가 이전에 사용했던 표현인 Completeness, Soundness와 HVZK의 정의를 다시 살펴보자. Completeness는 그대로 가져와도 된다.

 

정의 : Knowledge Soundness란, $y \in \mathcal{Y}$에 대한 accepting conversation $(t, c, z)$와 $(t, c', z')$이 주어졌고, $c \neq c'$일 때, $y$에 대한 witness $x$를 효율적으로 계산하는 알고리즘이 존재한다는 것이다. 이러한 알고리즘을 Witness Extractor라고 부르기도 한다.

 

Schnorr's Protocol이 Knowledge Soundness를 가짐은 이미 알고 있는 사실이다. 이는 우리의 기존 Soundness에 대한 정의보다 더욱 강력하다.

이렇게 강력한 조건을 주는 이유는, 역시 Schnorr's Protocol에서 사용했던 증명을 그대로 쓰고 싶기 때문이다.

생각해보면, Witness Extractor가 존재해야 Rewinding Lemma를 사용하는 증명을 할 수 있다. Rewinding Lemma가 해주는 것은 $(t, c, z)$와 $(t, c', z')$를 얻어주는 것이고, 그 뒤의 일은 Witness Extractor의 몫이다. Schnorr's Protocol에서는 "연립일차방정식을 푸는 것"이라고 불렀다. 

 

 

정의 : Special HVZK란, $(y, c) \in \mathcal{Y} \times \mathcal{C}$를 input으로 받아 다음을 output으로 내는 효율적인 Simulator가 존재한다는 것이다.

  • 모든 $(y, c) \in \mathcal{Y} \times \mathcal{C}$에 대하여, Simulator의 output이 $(t, z)$일 때, $(t, c, z)$는 무조건 accepting conversation for $y$이다.
  • $(x, y) \in \mathcal{R}$이라고 하자. 이제 $c$를 $\mathcal{C}$에서 random하게 고른 후, $(t, z)$를 $(y, c)$에 대해 Simulator를 돌려서 얻은 값이라고 하자.
  • 이때, $(t, c, z)$는 $x$를 갖고 있는 Prover와 Verifier 사이의 conversation과 동일한 분포를 갖는다.

여기서 HVZK와 Special HVZK를 비교하면서 강조할 점은 다음 두 가지다.

  • $y$가 witness가 애초에 없는 원소여도, Simulator는 accepting conversation for $y$를 만들어야 한다.
  • Simulator는 $x$를 모르지만, $x$를 갖고 있는 Prover가 만들어내는 증명과 같은 분포를 뽑아내야 한다. 
  • $y$에 대한 witness $x$가 여러 개 있을 수 있음에 주목하라. 이러면 Special HVZK의 의미를 다음과 같이 생각할 수 있다.
  • Accepting Conversation으로는 $x$가 witness인 것 외에는 아무 정보도 얻을 수 없다. 특히, $x$가 witness 중에 어떤 witness인지도 알 수 없다.

 

Sigma Protocol for Pre-Image of a Homomorphism

이제 Sigma Protocol의 큰 family 하나를 소개하고, 그 구체적인 사례를 매우 간단하게만 나열한다.

 

$H_1, H_2$가 finite abelian group of known order라고 하고, $\phi : H_1 \rightarrow H_2$를 group homomorphism이라 하자. Schnorr's Protocol과 notation을 맞추기 위해서, $H_1$에서의 이항연산은 덧셈으로, $H_2$에서의 이항연산은 곱셈으로 표기하도록 한다. 이제, Effective Relation은 $$(\alpha, u) \in H_1 \times H_2 : \quad \phi(\alpha) = u$$이다. 즉, Prover는 $u$에 대한 $\phi$의 preimage를 알고 있음을 Verifier에게 증명하려고 한다. 이때, challenge space 적당한 자연수 $N$에 대하여 $\mathcal{C} = \{0, 1, \cdots, N-1\}$이다. 이제 Prover와 Verifier는 Schnorr's Protocol처럼 다음 과정을 거친다.

  • Prover는 $\alpha_t$를 $H_1$에서 랜덤하게 고르고, $u_t = \phi(\alpha_t)$를 Verifier에게 보낸다.
  • Verifier는 $\mathcal{C}$에서 challenge $c$를 랜덤하게 고르고, Prover에게 보낸다.
  • Prover는 $\alpha_z = \alpha_t + \alpha \cdot c \in H_1$을 계산하고, Verifier에게 보낸다.
  • Verifier는 $\phi(\alpha_z) = u_t \cdot u^c$인지 확인하고, 이를 기반으로 accept/reject.

정리 : 위 Protocol은 Sigma Protocol이며, Special HVZK이다. $|H_1| \times |H_2|$의 최소 소인수가 $|\mathcal{C}|= N$ 이상이면, Knowledge Soundness를 갖는다.

  • Effective Relation이 정말 Effective Relation인 것은 자명하다. 이 Protocol이 Sigma Protocol임도 자명하다.
  • Special HVZK임은 Schnorr's Protocol과 같은 방식으로 Simulator를 만들어주면 된다. 증명은 연습으로 남긴다.
  • Knowledge Soundness로 Schnorr's Protocol과 같은 방식으로 하면 된다. 이때, modular inverse를 취하기 위하여 소인수 조건이 필요하다.

이제 구체적인 사례를 몇 가지 제시한다. 

  • Okamoto's Protocol : $H_1 = \mathbb{Z}_q \times \mathbb{Z}_q$, $H_2 = \mathbb{G}$, $\phi(x, y) = g^x h^y$. 
  • Chaum-Petersen Protocol : $H_1= \mathbb{Z}_q$, $H_2 = \mathbb{G} \times \mathbb{G}$, $\phi(x) = (g^x, u^x)$. (Diffie-Hellman Context)
  • General Linear Protocol : $H_1 = \mathbb{Z}_q^n$, $H_2 = \mathbb{G}^m$, $\displaystyle \phi(x_1, \cdots,  x_n) = \left(\prod_{i=1}^n g_{1i}^{x_i}, \cdots , \prod_{i=1}^n g_{mi}^{x_i} \right)$.
  • GQ Protocol : $H_1 = \mathbb{Z}_n^{*}$, $H_2 = \mathbb{Z}_n^{*}$, $\phi(x) = x^e$. (RSA Context)

GQ Protocol에서는 사실 $H_1, H_2$의 group order를 모른다. 그래서 따로 증명을 해줘야 한다. 여기서 $(n, e)$는 RSA 공개키이며, $e$는 큰 소수라고 가정한다. 또한, challenge space는 $\{0, 1, \cdots, e-1\}$으로 설정한다. 말이 따로 증명이지, 사실 기존 증명 방식을 그대로 적용하면 증명이 된다.

자신있게 말할 수는 없으나, 내 생각에는 아마 $\mathbb{Z}_n^{*}$에서 random한 원소를 뽑는 것이 어렵지 않기 때문에 가능한 증명일 것이다. Simulator를 만들거나 아니면 단순히 Protocol을 따를 때, group의 random element를 뽑는 과정이 필수적이다. 그런데 group order를 모른다면 이걸 하기가 상당히 난감할 것이다.

하지만 $\mathbb{Z}_n^{*}$에서는 단순히 $\mathbb{Z}_n$의 원소를 하나 뽑은 다음 GCD를 계산해, $1$이 나오면 그 값을 그대로 제출하면 되므로 문제가 없다.

 

Sigma Protocol : Security Analysis

이제 다양한 Sigma Protocol들의 안전성을 분석해보자. 이를 위해서는 Schnorr's Protocol의 안전성 증명을 복습할 필요가 있다.

  • HVZK (Special HVZK) : accepting conversation을 엿듣는 것이 의미가 없다는 것을 증명한다. (Eavesdrop = Direct Attack)
  • Soundness (Knowledge Soundness) : 증명을 만들 수 있다면 $sk$를 복원하는 것이 (Schnorr에서는 DL을 해결) 가능함을 증명한다. 

여기서 우리가 바꿔야 할 부분은 "Schnorr에서는 DL을 해결" 부분이다. 그러니, 다음 정의는 자연스럽다.

 

정의 (One-Way KeyGen) : $G$는 $(sk, pk) = (x, y) \in \mathcal{R}$을 생성하는 알고리즘이다. adversary가 $y$를 받았을 때, 효율적인 알고리즘으로 $y$에 대한 witness를 계산하는 게임을 생각하자. 이 게임에 대한 adversary의 advantage가 negligible이라면, 이 KeyGen 알고리즘을 one way라고 부른다. 

 

이제 앞선 Schnorr's Protocol에 대한 증명에서 Discrete Logarithm에 대한 advantage를 위 게임에 대한 advantage로 바꾸면, 모든 증명을 그대로 할 수 있다. 즉, KeyGen 자체가 one way라면 이 Sigma Protocol도 안전함을 증명할 수 있다. 결국 $sk$를 $pk$를 통해서 계산하기 어렵다는 가정만 있으면 된다.

 

다시 한 번 강조하지만 구체적인 advantage에 대한 식들은 이전 글과 동일하므로, 여기서는 생략한다. 

 

Signatures from Sigma Protocol : Security Analysis

Fiat-Shamir Heuristic을 적용하면, Schnorr's Signature와 같은 방식으로 Sigma Protocol에서도 Signature를 만들 수 있다. 

이제 이 Signature의 안전성을 분석해보자. 이를 위해서는, 역시 Schnorr's Signature의 안전성 증명을 복습할 필요가 있다.

  • $r$-impersonation에 대한 분석은 여전히 유효하다. Discrete Logarithm을 위에서 정의한 One-Way KeyGen으로 바꾸면 된다.
  • Signature Scheme에 대한 분석을 보자. 여기서 핵심은 signing query에서 random oracle access가 겹치는 경우를 전부 제거하기 위해 Union Bound + Difference Lemma를 사용한 것이다. 특히, 우리는 random oracle access가 겹치는 확률에 대한 upper bound를 구하기 위해서 $u_{ti}$에 대한 분포를 사용하였다. Schnorr's Signature에서는 $u_{ti}$가 $\mathbb{G}$ 위에서 uniform random이었으므로, 각 원소가 될 확률이 $1/q$라고 결론낼 수 있었다. 그러나 지금의 우리는 commitment $t$의 값이 어떤 분포를 따르는지 강제하지 않았다. 이 부분을 해소해야 한다. 이제 다음 정의는 자연스럽다. 

정의 (Unpredictable Commitments) : conversation $(t, c, z)$가 집합 $\mathcal{T} \times \mathcal{C} \times \mathcal{Z}$에 속한다고 하자. 각 $(x, y) \in \mathcal{R}$과 $\hat{t} \in \mathcal{T}$에 대하여, $y$에 대한 witness $x$를 증명하고자 하는 Prover와 이를 인증하는 Verifier가 conversation $(t, c, z)$를 만들었을 때, $t = \hat{t}$가 성립할 확률이 최대 $\delta$인 경우, 이를 $\delta$-unpredictable commitment를 가지는 Sigma Protocol이라 한다. 특히, $\delta$가 negligible이면 단순히 unpredictable commitment를 가진다고 한다.

 

결국에는 Signature Scheme의 안전성 증명의 context에서 각 원소에서 겹칠 확률이 $\delta$ 이하라는 것이다.

즉, Schnorr's Signature의 안전성 증명에서 $1/q$ 부분을 전부 $\delta$로 바꾸기만 하면 모든 결과가 그대로 적용된다.

 

2. Actively Secure Identification Protocols with Sigma Protocols

Actively Secure하다는 것은, 앞에서 예고했듯이 adversary가 Malicious Verifier의 역할을 할 수 있는 경우까지 고려했을 때도 안전하다는 것이다. 즉, 우리가 상대할 adversary는 Verifier 행세를 하면서 Honest Prover와 대화할 수 있는데, challenge를 자기 마음대로 (즉, uniform random이 아니어도 된다) 고를 수 있다는 것이다. 이러한 Protocol을 만들려면 재료가 필요하다. AND/OR-proofWitness Independence가 그 재료들이다. 

 

AND/OR-proof 

이제부터 두 개의 Efficient Relation $\mathcal{R}_0 \subset \mathcal{X}_0 \times \mathcal{Y}_0$와 $\mathcal{R}_1 \subset \mathcal{X}_1 \times \mathcal{Y}_1$이 있다고 하자. 또한, 각각에 대한 Sigma Protocol이 있다고 가정한다. 특히, 이 Sigma Protocol들이 Special HVZK와 Knowledge Soundness를 보장한다고 가정하겠다. 또한, OR-proof을 위하여 $\mathcal{C} = \{0,1\}^n$ 형태를 가정하겠다. (다르게 표현하면, $\mathcal{C}$는 $2^n$ 미만의 음이 아닌 정수들의 집합이다) 이제 이 Sigma Protocol의 AND/OR을 생각해보자. 

 

AND-proof : 두 Relation에 대한 witness가 전부 있음을 증명한다. 즉, 목표는 $$\mathcal{R}_{AND} = \{ ((x_0, x_1), (y_0, y_1)) : (x_0, y_0) \in \mathcal{R}_0, (x_1, y_1) \in \mathcal{R}_1 \}$$을 생각하고, 이 새로운 Efficient Relation에 대한 Sigma Protocol을 만드는 것이다. 이는 어렵지 않은 게, 그냥 $\mathcal{R}_0$와 $\mathcal{R}_1$에 대한 Sigma Protocol을 동시에 돌리면 된다. 한 가지 차이는 Verifier가 두 Protocol에 대한 challenge를 같은 값 $c$로 준다는 것인데, 그래도 Special HVZK와 Knowledge Soundness는 여전히 가져올 수 있다. 증명은 자명하고 직관적이므로 생략한다. Proof Sketch는 책의 Theorem 19.18에 설명되어 있으니 필요하면 참고하자.

 

OR-proof : 두 Relation 중 적어도 하나에 대한 witness가 있음을 증명한다. 중요한 것은, 어느 것에 대한 witness인지는 밝히면 안된다는 것이다. 목표는 $$ \mathcal{R}_{OR} = \{ ((b,x),(y_0, y_1)) : (x, y_b) \in \mathcal{R}_b \} $$에 대한 Special HVZK, Knowledge Soundness를 갖는 Sigma Protocol이다. 이를 위해서, 다음과 같은 과정을 설계한다.

  • Prover가 $\mathcal{R}_b$에서 $y_b$에 대한 witness $x$를 갖고 있다고 가정하자. $d = 1-b$라 하자.
  • 먼저 Prover는 $c_d$를 $\mathcal{C}$에서 random하게 고르고, $(t_d, z_d)$를 $\mathcal{R}_d$에 대한 Simulator에 $(y_d, c_d)$를 넣어서 계산하자.
  • 또한, $(x, y_b) \in \mathcal{R}_b$를 알고 있으니 $\mathcal{R}_b$에 대한 Sigma Protocol을 돌려서 commitment $t_b$를 구한다. 이제 $(t_0, t_1)$을 Verifier에게 보낸다.
  • Verifier는 역시 challenge $c$를 $\mathcal{C}$에서 random하게 고르고, 이를 Prover에게 전달한다.
  • Prover는 $c_b = c \oplus c_d$를 계산하고, $c_b$를 $\mathcal{R}_b$에 대한 Sigma Protocol의 commitment 값으로 둔다.
  • 이제 $t_b, c_b$를 사용하여 response $z_b$를 계산한다. 그 후, $(c_0, z_0, z_1)$을 Verifier에게 보낸다.
  • Verifier는 $c_1 = c \oplus c_0$를 계산하고, $(t_0, c_0, z_0)$와 $(t_1, c_1, z_1)$이 accepting conversation인지 확인하고 accept/reject.

이제 이 Protocol의 다양한 성질들을 증명하자. Completeness는 자명하다. 

  • Knowledge Soundness : 여기서 중요한 점은 $c$의 값이 $c'$으로 달라지면, $c_0$의 값이 달라지거나 $c_1$의 값이 달라지거나 둘 중 하나는 일어난다는 것이다. 이는 $c_0 \oplus c_1 = c$이기 때문이다. 그러니 결국 $\mathcal{R}_0$ 또는 $\mathcal{R}_1$에서 Witness Extractor를 사용할 수 있고, 증명 끝.
  • Special HVZK : $y_0, y_1, c$를 input으로 받으면 $c_0$를 $\mathcal{C}$에서 random하게 고르고, $c_1$을 $c_0 \oplus c$로 둔 다음, $(y_0, c_0)$와 $(y_1, c_1)$ 각각에 대하여 Simulator를 돌려주면 된다. 분포가 같음은 직관적으로 자명하고 직접 보이기도 어렵지 않다. 이러면 증명 끝.

 

Witness Independence

앞에서 우리는 Special HVZK면 accepting conversation을 보는 것으로는 verifying key/public key에서 얻을 수 있는 정보 외에는 얻을 수 있는 것이 없다고 했고, 특히 Prover가 어떤 witness를 사용하고 있는지에 대한 정보가 없다고 말했다. 이에 대한 엄밀한 설명이 필요하다.

 

정의 : Sigma Protocol을 갖는 Efficient Relation $\mathcal{R}$이 있고, $(x, y) \in \mathcal{R}$이 있다. 우리의 adversary는 $y$의 값을 알고 있으며, [자신이 $y$에 대한 witness $x$를 알고 있음을 증명하려고 하는 Prover 여러 명]과 동시에 대화할 수 있다. 즉, 이들을 상대로 Verifier 행세를 할 수 있으며, 이때 꼭 Verifier의 Protocol을 정직하게 따를 필요는 없다. 이제 adversary는 output space $\mathcal{S}$에 속하는 output $s$를 낸다. $\theta (x, y, s)$를 adversary가 $s$를 output으로 낼 확률이라 하자. 

 

정의 : Witness Independence란, 모든 adversary $\mathcal{A}$에 대해서, 각 $y \in \mathcal{Y}$와 $x, x' \in \mathcal{X}$, $s \in \mathcal{S}$에 대하여, $(x, y), (x', y) \in \mathcal{R}$이라면, $$ \theta (x, y, s) = \theta(x',y,s)$$라는 것이다. 특히, adversary는 efficient 하지 않아도 된다. 결국 output과 witness는 완전히 독립적이라는 뜻.

 

이제 Special HVZK면 Witness Independent함을 보일 수 있다. 증명은 책의 Theorem 19.21에 나와있으나, 여기서는 생략한다. 

핵심은 어쨌든 어떤 witness $x$를 사용했냐와 무관하게 accepting conversation의 분포가 (Simulator의 그것과) 같다는 것이다.

우리의 adversary가 바라보는 정보가 $x$와 아예 독립적인데 그것에서 $x$에 대한 정보를 뽑아낼 수는 없을 것이다.

 

이제 준비가 끝났으니, 우리의 목표인 Actively Secure Identification Protocol에 대하여 알아보자.

 

Actively Secure Identification Protocol

아이디어는 Eavesdrop/Direct에 안전한 Sigma Protocol을 두 개 가져와서 OR-proof를 만드는 것이다.

 

즉, $\mathcal{R} \subset \mathcal{X} \times \mathcal{Y}$가 있고, 이에 대한 Special HVZK, Knowledge Soundness를 가지는 Sigma Protocol이 있다고 가정하자. 또한, 이 $\mathcal{Y}$의 임의의 원소에 대해서 witness를 찾는 것이 어렵다고 가정하자. 즉, one-way임을 가정하자. 이제 $\mathcal{R}$과 $\mathcal{R}$을 가지고 OR-proof에 대응되는 Sigma Protocol을 만들자.

이제부터 이 Protocol이 Actively Secure함을 증명할 것이다. 

 

정리 : 위 context에서, 새로운 Protocol을 Active Attack으로 (즉, Malicious Verifier 행세) advantage $\epsilon$으로 깨는 efficient adversary $\mathcal{A}$가 있다고 가정하자. 이때, $\mathcal{R}$의 one-way 게임을 (즉, witness를 찾는 게임을) advantage $\epsilon'$으로 이기는 efficient adversary $\mathcal{B}$가 있으며, 특히 $$\epsilon' \ge \frac{1}{2} (\epsilon^2 - \epsilon / N)$$

증명을 위해서는 $\mathcal{B}$를 하나 만들어주면 된다. 이제 $y' \in \mathcal{Y}$를 하나 받고, $\mathcal{A}$를 활용하여 $y'$의 witness를 하나 구해주는 알고리즘을 설계해보자.

이를 위해서, 우리는 먼저 $(x, y) \in \mathcal{R}$을 하나 random하게 생성하고, (KeyGen) $b \in \{0, 1\}$을 하나 random하게 고른다.

만약 $b=0$이라면, $Y = (y, y')$를, $b=1$이라면, $Y = (y', y)$를 $\mathcal{A}$가 증명을 시도할 대상으로 선정한다. 이제 $X = (b,x)$라 하자.

이때, $(X, Y)$의 분포가 $\mathcal{R}$ 두 개를 OR해서 얻은 Relation의 원소의 분포와 동일함에 주목하라. 

  • $\mathcal{A}$가 Malicious Verifier 행세를 하기를 원한다면, 우리는 $X = (b, x)$가 witness임을 이미 알고 있으니 이를 이용하여 Sigma Protocol에 따라주면 된다. 물론, $\mathcal{A}$가 어떻게 challenge를 고르는지에 대해서는 신경쓰지 않는다. 알아서 자기 할 일 하게 두면 된다...

이제 $\mathcal{A}$가 $Y$의 witness를 안다는 것을 보이기 위해서 증명을 시도할 것이다. 우리는 이때 정직하게 challenge를 random하게 주면 된다. $\mathcal{A}$가 이 증명에 성공할 확률은 정의상 $\epsilon$이다. 그러니 Rewinding Lemma를 이용하면 우리는 $\epsilon^2 - \epsilon / N$의 확률로 증명에 두 번 성공하는 사례를 찾을 수 있고, Witness Extractor를 이용하여 $Y$의 witness를 하나 얻을 수 있다. 그런데, Witness Independence에 의하여 이 witness가 $y'$의 witness를 포함할 확률은 정확히 $1/2$이다. 그러니 우리가 여기서 $y'$의 witness를 얻을 advantage는 $$\epsilon' \ge \frac{1}{2} (\epsilon^2 - \epsilon / N)$$

 

OR-proof를 꺼내지 않더라도 Active Attack을 막을 수 있다. 주어진 $y$에 대한 witness 2개를 찾기가 힘든 Protocol을 이용하면 된다. 대충 이런 방식.

  • 주어진 $y$에 대한 witness가 정말 많으나, 서로 다른 witness 2개를 찾기가 어렵다고 가정하자.
  • $(x, y) \in \mathcal{R}$을 하나 갖고, adversary에게 Active Attack으로 $y$의 witness를 찾아보라고 하자.
  • 특히, 우리가 이미 $(x, y) \in \mathcal{R}$을 하나 알고 있으니, 마음껏 증명을 제공할 수 있다.
  • adversary가 성공하고 witness $x'$을 찾았다고 가정하자. $x' \neq x$이면 witness 2개를 찾았으니 가정을 깼다.
  • 특히 Witness Independence가 있으니 $x' \neq x$일 확률은 (가능한 witness가 많다면) 매우 높다.

그 예시가 Okamoto's Identification Protocol이다. Finite Abelian Group of (Known) Prime Order $q$인 $\mathbb{G}$를 잡자. 또한, $g, h$를 $\mathbb{G}$의 두 원소라고 하자. Okamoto's Protocol에서는 $u \in \mathbb{G}$가 있을 때, $g^\alpha h^\beta = u$인 $(\alpha, \beta)$를 알고 있는지 물어본다. 이는 앞에서도 언급했듯이 Homomorphism의 Pre-Image를 물어보는 것과 같으며, Special HVZK와 (Witness Independence) Knowledge Soundness를 가진다. 또한, $u$의 서로 다른 witness를 두 개 알고 있다면, 이를 이용해 $h$의 $g$에 대한 이산로그를 계산할 수 있다. 또한, witness의 개수는 항상 ($g, h$가 identitiy인 경우는 제외하자) $q$개다. 이제 준비가 끝났다.

 

정리 : Okamoto's Protocol을 Active Attack으로 advantage $\epsilon$으로 깰 수 있는 efficient adversary $\mathcal{A}$가 있다고 하자. 이때, $\mathbb{G}$ 위에서의 Discrete Logarithm 문제를 advantage $\epsilon'$으로 해결할 수 있는 efficient adversary $\mathcal{B}$가 존재한다. 이때, $$\epsilon' \ge (1-1/q) (\epsilon^2 - \epsilon / N)$$

증명은 위에서 말한대로 하면 된다. $\mathcal{B}$가 $g, h$를 갖고 있고, $h$의 $g$에 대한 이산로그를 구하려고 한다고 하자.

이제 $\alpha, \beta$를 $\mathbb{Z}_q$에서 각각 random하게 고르고, $u = g^{\alpha} h^{\beta}$를 구한다.

그 후, $\mathcal{A}$에게 $g, h, u$를 주면서 witness를 찾아보라고 하자. 증명은 우리가 이미 $(\alpha, \beta)$를 알고 있으니 시키는대로 전달하자.

만약 $\mathcal{A}$가 Verifier에게서 accept를 얻는 것에 성공했다면, Rewinding Lemma를 적용하여 $u$에 대한 witness를 복구하자.

이때, Witness Independence 성질에서 이 witness가 $(\alpha, \beta)$와 다를 확률은 $1-1/q$가 된다.

이 경우, 우리는 서로 다른 두 witness를 얻는 것에 성공하고, 이를 통해 Discrete Logarithm을 계산할 수 있다. 증명 끝.

 

'Cryptography' 카테고리의 다른 글

Lattice Attacks Introductory Survey  (0) 2021.07.22
Inequality Solving with CVP  (0) 2021.03.26
Schnorr's Protocol & Signature  (0) 2021.02.13
Diophantine Argument of Knowledge  (4) 2021.01.20
Leftover Hash Lemma and its Applications  (0) 2020.10.18