Schwartz-Zippel Lemma

본 글에서는 앞서 살펴본 상호작용 증명(Interactive Proof)과 논증 시스템(Argument System)의 엄밀한 정의와 Schwartz-Zippel Lemma, 그리고 몇가지 수학적 테크닉을 살펴보겠습니다.

결정 문제와 언어

결정 문제(Decision problems)란 모든 입력 $x$에 대해 결과 $f(x)$가 항상 1 또는 0 (참 또는 거짓)으로 결정되는 문제를 말합니다. (즉, $f: \{0,1\}^n \to \{0,1\}$.)

이 때, 주어진 결정 문제 $f$가 참 ($f(x)=1$)이 되도록 하는 입력값 $x$ 들의 집합 $\mathcal L\sub \{0,1\}^n$을 언어(language) 라고 합니다.

이제 해당 정의를 사용하여 상호작용 증명을 수학적으로 정의해보겠습니다.

상호작용 증명 (IP)

상호작용 증명 시스템(Interactive Proof system; IP)은 결정 문제 ($f: \{0,1\}^n \to \{0,1\}$)에 대해, 다항 시간 안에 동작하는 확률적 검증자 알고리즘 $\mathcal V$와 결정적(deterministic) 증명자 알고리즘 $\mathcal P$의 쌍 $(\mathcal V, \mathcal P)$으로 정의됩니다. 두 사람은 공통 입력 $x \in \{0,1\}^n$을 공유하며, 증명자는 $f(x)=1$ (참) 을 주장하고 검증자는 그것이 참임을 검증합니다.

이후 두 알고리즘은 $m_1, m_2, \dots, m_k$의 형태로 메시지를 번갈아가며 교환합니다. 이 때 증명자 $\mathcal P$와 검증자 $\mathcal V$는 입력 값과 메시지 시퀀스 $(x, m_1, m_2, \dots, m_{i-1})$을 받아 다음 메시지 $m_i$를 보내는 계산 알고리즘으로 생각할 수 있습니다.

이 메시지들의 전체 시퀀스를 필사(transcript)라 부르며, 검증자는 모든 메시지를 받은 뒤 최종적으로 $1$ (accept) 또는 $0$ (reject)을 출력합니다.

검증자의 출력은 내부 난수 $r$과 transcript $t$에 의존하며, 이를

$$\text{out}(\mathcal{V}, x, r, \mathcal{P}) \in \{0,1\}$$

로 나타냅니다.

이는 검증자가 특정 난수 $r$과 입력 $x$에 대해 증명자 $\mathcal{P}$와 상호작용한 결과를 의미하며, 고정된 난수값 $r$에 대해선 결정적 함수로 볼 수 있습니다.

Definition

정의 3.1. 언어 $\mathcal L$의 IP 시스템 $(\mathcal V, \mathcal P)$에 대해, 완전성 오류 $\delta_c$와 건전성 오류 $\delta_s$를 다음과 같이 정의한다.

1

완전성 (completeness)

모든 $x\in\mathcal L$ 에 대해,

$$\Pr_{r}[\text{out}(\mathcal{V}, x, r, \mathcal{P}) = 1] \ge 1 - \delta_c.$$

즉, honest prover와 상호작용 시 검증자가 대부분의 경우(확률 최소 $1-\delta_c$), 이를 받아들인다.

2

건전성 (soundness)

모든 $x\notin \mathcal L$ 와 모든 결정적 증명자 $\mathcal P'$ 에 대해,

$$\Pr_{r}[\text{out}(\mathcal{V}, x, r, \mathcal{P}') = 1] \le \delta_s.$$

즉, 어떠한 (심지어 악의적인) 증명자라도 거짓을 받아들이게 할 확률은 적다(최대 $\delta_s$).

이 때, IP 시스템은 $\delta_c, \delta_s\le 1/3$ 일때 유효하다고 말합니다.

Details

몇가지 중요한 포인트를 짚고 넘어가겠습니다.

저희가 IP를 결정 문제를 이용해 정의한 이유는, 이렇게 하면 IP를 알고리즘의 복잡도 클래스(complexity class)로 해석할 수 있으며 이를 통해 중요한 결과들도 도출할 수 있기 때문입니다. (예, $\text{IP}=\text{PSPACE}$, $\text{MIP}=\text{NEXP}$.)

또한 위 IP의 정의에서 증명 시스템의 상호 작용성과 무작위성을 없애면 $\text{NP}$ 클래스 (다항시간에 결정적으로 검증 가능한 결정 문제)가 되는 것을 확인할 수 있습니다 (즉, $\text{NP}\subseteq \text{IP}$.)

IP 시스템의 유효성을 $\delta_c, \delta_s\le 1/3$ 기준으로 정의한 이유는 무엇일까요? 이는 사실 몇가지 연구 결과와 관련이 있습니다. 완전성 오류 $\delta_c=0$ 인 경우, 즉 모든 honest prover가 항상 증명을 성공하는 IP 시스템을 완벽한 완전성을 가진다고 합니다.

이 때, 완전성 오류 $\delta_c\le 1/3$ 인 모든 IP 시스템은 완벽한 완전성 ($\delta_c=0$)을 가진 시스템으로 변환될 수 있습니다! (단, 검증자의 시간복잡도와 증명 길이가 다항시간 만큼 늘어납니다. [FGM+89]) 건전성 오류 $\delta_s\le 1/3$의 기준은 관례적인 것이나, 이 또한 간단히 증명을 $k$번 반복하는 것으로 오류를 $\delta_s^k$로 줄일 수 있습니다.

참고로 안심하세요, 앞으로 저희가 살펴볼 IP 시스템들은 대부분 $\delta_c=0$이며 $\delta_s\propto 1/|\mathbb F|$ 로 아주 작습니다.

앞서 정의한 IP를 결정 문제 뿐만아니라, 임의의 함수 $y=f(x)$에 대해서 증명자가 입력 $x$에 대한 함숫값 $y$를 증명하도록 정의를 확장할 수 있습니다. 이는 언어를 $\mathcal L_f=\{(x,y) : y=f(x)\}$ 와 같이 정의함으로써 가능합니다. (증명자가 주장하는 $y$에 대해 $y=f(x) \iff (x,y)\in L_F$ 임에 주목하세요!)

논증 시스템 (Argument Systems)

정의 3.2 (논증 시스템). 함수 $f$의 논증 시스템 (argument system)이란 $f$의 상호작용 증명 (IP) 중 건전성 조건이 다항시간 증명자 $\mathcal P'$에 대해서 성립하는 증명 시스템이다.

증명자를 다항시간으로 제한한 건전성을 계산적 건전성(computational soundness)이라고 부릅니다. 이처럼 논증 시스템이 다항시간을 가정하는 이유는, 현실에서 유용한 암호학 기초 이론들을 이용하기 위함입니다.

예를 들어 암호학에서 많이 사용되는 이산로그 문제같은 one-way function, 암호학적 해시함수, MAC 등은 다항시간이라는 가정 하에서만 안전합니다.

Schwartz-Zippel Lemma

다변수 다항식

이 장에서 저희는 변수가 $m$개인 다변수(polynomial in m variables) 다항식을 다룰 것 입니다. 예를 들어, $g(x_1,x_2)=6x_1+7x_1^3x_2$ 는 2변수 다항식입니다.

이 때 $g$의 전체 차수 $d$는 변수와 관계없이 가장 차수가 높은 항의 차수로 정의합니다. (해당 예시에서는 $7x_1^3x_2$의 차수가 4로 최대이므로 $g$는 전체 차수 4입니다.)

Lemma

보조정리 3.3 (Schwartz-Zippel Lemma). 임의의 체 $\mathbb F$ 위에서 전체 차수가 최대 $d$이고 영이 아닌 $m$-변수 다항식 $g: \mathbb F^m\to\mathbb F$ 를 고려하자. 모든 유한한 $S\subseteq \mathbb F$에 대해, 다음 부등식이 성립한다:

$$\Pr_{x \leftarrow S^m}[g(x) = 0] \le \frac{d}{|S|}.$$

여기서 $x \leftarrow S^m$ 은 $S^m$에서 uniform random하게 선택된 $x$를 의미하며, $|S|$는 집합 $S$의 크기를 나타냅니다. $S=\mathbb F$일 때를 생각하면, 전체 차수가 $d$ 이하인 다변수 다항식은 최대 $d / |\mathbb F|$ 비율의 점에서만 0이 된다는 것을 알 수 있습니다. 저희는 지난 블로그 Reed-Solomon 핑거프린팅 파트에서, Schwartz-Zippel Lemma의 일변수 함수 케이스를 살펴본 바 있습니다.

해당 보조정리는 많은 증명 시스템에서 유용하게 쓰이며, 정리 자체의 증명은 귀납법을 이용해서 깔끔하게 가능합니다.

Multilinear Extensions

앞서 라그랑주 보간법에서 저희는 주어진 길이 $n$벡터를 확장시켜 각 점을 지나는 다항식을 만들었습니다. 이번에는 주어진 $f: \{0,1\}^v\to\mathbb F$ ($v$-차원 boolean hypercube -> 체 $\mathbb F$로 가는 함수)에 대해, 정의역을 $\mathbb F^v$으로 확장시키는 Multilinear Extension에 대해 알아보겠습니다.

정의 3.4. 다변수 다항식 $g$는 각 변수에 대한 차수가 최대 1일때 multilinear 하다고 한다.

정리 3.5. 모든 함수 $f: \{0,1\}^v\to\mathbb F$ 는 체 $\mathbb F$ 위에서 유일한 multilinear extension (MLE) $\tilde f$ 를 가진다. (즉, $\tilde f: \mathbb F^v\to\mathbb F$ 는 모든 $x\in\{0,1\}^v$ 에 대해 $\tilde f(x)=f(x)$ 를 만족하는 multilinear 다항식이다.)

Proof. (존재성) 라그랑주 보간법에서 했던 증명 방식과 마찬가지로 조건을 만족하는 함수 $\tilde f$를 만들어 보겠습니다:

$$\tilde{f}(x_1, \ldots, x_v) = \sum_{w \in \{0,1\}^v} f(w) \cdot \chi_w(x_1, \ldots, x_v), \tag{3.1}$$

이 때 고정된 $w=(w_1,\cdots,w_v)\in\{0,1\}^v$에 대해,

$$\chi_w(x_1, \ldots, x_v) := \prod_{i=1}^{v} \big( x_i w_i + (1 - x_i)(1 - w_i) \big). \tag{3.2}$$

해당 $\chi_w$를 multilinear 라그랑주 기저 다항식이라고 부릅니다. $\chi_w$는 각 변수에 대해 차수가 최대 1인 다변수 다항식임에 주목하세요.

임의의 벡터 $w \in \{0,1\}^v$에 대하여, $\chi_w$는 $\chi_w(w) = 1$이고 다른 모든 벡터 $y \in \{0,1\}^v$에 대해서는 $\chi_w(y) = 0$가 성립함을 관찰해봅시다.

만약 $w_i \ne y_i$라면 $w_i = 1$이고 $y_i = 0$이거나, $w_i = 0$이고 $y_i = 1$ 이므로 어느 경우든, 식 (3.2)의 오른쪽에 있는 $i$번째 항, 즉 $(x_i w_i + (1 - x_i)(1 - w_i))$는 $0$이 됩니다. 따라서 식 (3.2)의 오른쪽 전체 곱은 $0$이 됩니다. 반대로 모든 $i$에 대해 $w_i=y_i$가 성립한다면, 식 (3.2)의 값은 $1$이 됩니다. 원리는 2장에서 살펴본 라그랑주 기저 다항식과 유사합니다.

따라서, 식 (3.1)의 함수에 임의의 $y\in\{0,1\}^v$를 대입하면 합에서 $w\neq y$인 항들은 모두 0이 되어 사라지고 $w=y$인 항, 즉 $f(w)\ (=f(y))$ 만 남게 됩니다. 이는 저희가 원했던 성질입니다. 또한, 각 기저 다항식이 multilinear하고 $\tilde f$는 이들의 선형 결합이므로 $\tilde f$ 또한 multilinear 다항식입니다.

(유일성) 존재성을 보였으므로 유일성을 보이기 위해서 위 성질을 만족하는 다른 $\tilde f'$이 존재한다고 가정하겠습니다. 이 때 $h=\tilde f-\tilde f'$로 정의하면, $h$는 multilinear하고 $h(x)=0\ \forall x\in\{0,1\}^v$ 를 만족합니다. 이러한 $h=0$ 임을 보이면 유일성 증명이 끝납니다. 이는 $v$에 대한 귀납법으로 가능한데, induction step만 간단히 설명하겠습니다. $h$의 multilinearity에 의해 다음이 성립합니다:

$$h(x_1,\cdots,x_v)=a(x_1,\cdots,x_{v-1})\cdot x_v+b(x_1,\cdots,x_{v-1}).$$

$x_v=0$을 고정하면 $b(x)=0\ \forall x\in\{0,1\}^{v-1}$이므로 induction hypothesis에 의해 $b=0$이 됩니다. 이제 $x_v=1$을 고정하면 마찬가지로 $a=0$이 되어 $h(x_1,\cdots,x_v)=0$이 성립하고, 따라서 증명이 끝이 납니다. $\ \square$

함숫값 구하기

마지막으로 multilinear extension $\tilde f(r)$의 함숫값을 구하는 효율적인 알고리즘에 대해 알아보겠습니다.

먼저 $n=2^v$라고 하고 임의의 $r=(r_1,\cdots,r_v)\in\mathbb F^{\log n}$ 에 대해 $\tilde f(r)$ 값을 계산하는 것이 목표입니다. 식 (3.1)과 (3.2)의 정의에 입각하여 함숫값을 구하면 시간 복잡도 $O(n\log n)\ (=O(2^v\cdot v))$ 와 공간 복잡도 $O(\log n)\ (=O(v))$ 만에 간단히 계산할 수 있습니다.

$\chi_w(r)$ 을 자세히 살펴보겠습니다.

$$\chi_w(r_1, \ldots, r_v) = \prod_{i=1}^{v} \big( r_i w_i + (1 - r_i)(1 - w_i) \big),$$

$$r_i w_i + (1 - r_i)(1 - w_i)=\begin{cases} 1-r_i & w_i=0 \\ r_i & w_i=1 \end{cases}$$

이 때 우리는 $w$를 $\{0,1\}^v$의 모든 원소에 대해 계산하므로, $\chi_w$ 의 $i$번째 항에 대해 나올 수 있는 두 경우의 값을 저장해 두는 memoization을 사용할 수 있습니다.

즉, 위 그림과 같이 가능한 모든 $\chi_w$의 함숫값을 한 번에 계산할 수 있고 시간 복잡도와 공간 복잡도 모두 $O(n)$ 이 소요됩니다!