Polynomials, Randomness and Proof systems

본 글에서는 다항식과 확률론적 알고리즘을 이용함으로써 가능한 효율적인 증명 시스템들에 대하여 알아보겠습니다.

가정

앨리스와 밥이 아주 먼 거리에서, $n$개의 문자열로 이루어진 pdf 파일을 각각 가지고 있다고 가정해보겠습니다. 앨리스가 가진 문자열을 $a=(a_0, \cdots, a_{n-1})$, 밥의 문자열을 $b=(b_0, \cdots, b_{n-1})$ 이라고 하겠습니다. 두 명이 서로의 pdf 파일이 동일한지 확인하려면 어떻게 해야할까요?

---

가장 쉬운 방법은 문자열 전체를 전송하여 비교하는 것이겠죠, 즉 모든 $i=0,\cdots, n-1$에 대하여 $a_i=b_i$를 확인하는 것입니다. 이 경우 크기가 매우 큰 $n$ 문자열을 모두 전송하기 때문에 비효율적입니다.

그러나 다항식과 조금의 오류 확률을 받아들이면, 훨씬 작은 크기의 문자열만으로 비교가 가능해집니다.

Reed-Solomon Fingerprinting

길이 $n$ 벡터 $a=(a_0, \cdots, a_{n-1})\in \mathbb F_p^n$ 에 대하여, 다항식 $p_a(x)$를 다음과 같이 정의하겠습니다. 이렇게 만들어진 $p_a(x)$를 벡터 $a$의 Reed-Solomon 인코딩이라고 부릅니다. 이 때, $\mathbb F_p$는 $p$를 법으로 하는 유한체입니다.

$$p_a(x) = \sum^{n - 1}_{i = 0} a_i x^i =a_0+a_1x+\cdots+a_{n-1}x^{n-1}$$

이 후 $r \leftarrow \mathbb F_p$를 랜덤하게 추출한 뒤, 해당 $r$에서의 $p_a(x)$의 함숫값 $p_a(r)$을 Reed-Solomon 핑거프린팅이라 부릅니다. 해당 $p_a(r)$ 값은 $\mathbb F_p$의 원소이므로 정수 하나일 뿐입니다.

앨리스는 밥에게 자신이 고른 $r$과 $r$에 대한 Reed-Solomon 코드 값 $(r, p_a(r))$를 전송합니다. 밥은 앨리스가 보낸 $r$을 기반으로 자신의 코드 $p_b(r)$을 계산해 $p_a(r)=p_b(r)$인지 확인합니다. 밥은 두 값이 같으면 $\text{EQUAL}$, 아니면 $\text{NOT-EQUAL}$을 출력합니다.

분석

지난 포스트에서 저희는 증명 시스템이 완전성(Completeness)와 건전성(Soundness)를 만족시켜야 한다고 했습니다. 이를 확인해보겠습니다.

• 완전성: 참인 주장에 대해서 올바른 증명이 있어야 합니다. $a=b$이면 두 다항식 $p_a(x)=p_b(x)$가 같기 때문에 둘의 R-S 코드 $p_a(r)=p_b(r)$ 또한 일치합니다. 따라서 $r$이 어떤 값이든 상관없이 밥은 $\text{EQUAL}$을 출력합니다.

• 건전성: 거짓인 주장은 올바른 증명을 가져서는 안됩니다. $a\neq b$일 때, 둘의 R-S 코드가 달라 밥이 $\text{NOT-EQUAL}$을 출력할 확률은 최소 $1-(n-1)/p$ 이 됩니다 (설명은 후술). 따라서 $p\geq n^2$으로 잡는다면 최소 $1-1/n$ 확률로 건전성이 성립합니다.

그렇다면 밥이 $\text{NOT-EQUAL}$을 출력할 확률이 왜 $1-(n-1)/p$인지 알아보겠습니다. 이를 위해 다항식에 관한 한가지 정리를 사용해야 합니다.

정리 2.1. 임의의 체 $\mathbb F$ 에 대해, $\mathbb F$ 위에서 차수가 최대 $n$이고 영이 아닌 다항식은 최대 $n$개의 근을 가진다.

(정리 2.1은 다항식의 인수 정리를 이용해 쉽게 증명할 수 있습니다. 자세한 증명은 이곳을 참고하세요. 또한 해당 정리를 다변수 함수에 대해 확장시킨 것이 나중에 배울 Schwartz-Zippel Lemma입니다.)

$a\neq b$이면 $a_i\neq b_i$인 $i$가 적어도 하나 존재하므로, 다항식 $d(x)=p_a(x)-p_b(x)=\sum_{i=0}^{n-1} (a_i-b_i)x^i$ 는 영이 아니며 차수가 최대 $n-1$인 다항식입니다. 정리 2.1에 의해, $d(x)=0$을 만족하는 $x\in \mathbb F_p$는 최대 $n-1$개 존재합니다. 따라서 임의의 $r\leftarrow \mathbb F_p$에 대해 $d(r)\neq 0$일 확률은 최소 $1-(n-1)/p$ 입니다. $d(r)\neq 0$은 곧 $p_a(r)\neq p_b(r)$을 의미하므로 밥이 $\text{NOT-EQUAL}$을 출력할 확률은 최소 $1-(n-1)/p$이 됩니다.

효율성

기존에 문자열 전체를 전송하면 길이 $n$ 문자열을 사용했던 반면, R-S 핑커프린팅을 사용하면 $(r, p_a(r))$의 한 쌍만 보내면 되기 때문에 $\log p=O(\log n)$ 비트 ($p\cong n^2$로 설정) 문자열 하나만 전송해서 비교가 가능해집니다. 건전성에서 $1/n$의 오류 확률이 존재한다는 단점이 있으나 이는 $n$이 커짐에 따라 줄어드며, 증명 자체가 $n$에서 $\log n$ 수준으로 굉장히 단축된 것을 확인할 수 있습니다.

Freivalds' Algorithm

Reed-Solomon 코드의 방법론을 이용하는 확률론적 증명 시스템을 한가지 더 살펴보겠습니다. 우리에게 입력으로 두 개의 $n\times n$ 행렬 $A$와 $B$가 주어졌다고 가정해보겠습니다 ($A,B\in \mathbb F_p^{n\times n}$). 이 때 두 행렬의 곱 $AB$를 계산하는 것은 얼마의 시간복잡도가 필요할까요? 알고리즘을 공부하신 분들이라면 잘 아실 겁니다. 나이브하게 작성하면 $O(n^3)$, 분할정복을 사용한 슈트라센 알고리즘은 $O(n^{2.807})$ 이며 최근 연구결과는 $O(n^{2.372})$ 까지도 증명을 했다고 합니다. (참고 자료)

하지만, 두 행렬의 곱 $C=AB$가 올바르게 계산되었는지 더 빠르게 검증하는 것이 가능할까요? 가장 쉬운 방법은 검증자가 직접 행렬의 곱을 수행해 결과값을 비교하는 것이지만, 이 경우 계산과정과 동일한 시간이 걸리기 때문에 유의미하게 쓰이기 어렵습니다. 그러나 확률론적 알고리즘을 이용해 조금의 오류 확률을 허용하면, 이를 $O(n^2)$ 시간만으로 검증할 수 있습니다!

알고리즘

임의의 $r \leftarrow \mathbb F_p$를 고른 뒤 $\textbf x=(1, r, r^2, \cdots, r^{n-1})$ 열벡터를 생성합니다. 이후 $\textbf y=C\textbf x$와 $\textbf z=AB\textbf x=A(B\textbf x)$ 를 계산하여 $\textbf y=\textbf z$ 이면 $\text{YES}$, 아닐 경우 $\text{NO}$ 를 출력합니다.

위 알고리즘의 시간 복잡도를 계산해보면, 벡터 $\textbf x$를 생성하는데 $O(n)$, $n\times n$ 행렬과 길이 $n$ 벡터를 곱하여 벡터 $\bf y$와 $\bf z$를 계산하는데 $O(n^2)$이 걸리므로 전체 시간 복잡도는 $O(n^2)$ 입니다.

분석

마찬가지로 증명 시스템의 완전성과 건전성을 증명해보겠습니다. 이 때 증명자가 주장하는 행렬곱을 $C$, 실제 행렬곱을 $AB$로 설정하겠습니다.

• 완전성: $C=AB$이면 $r$의 값과 상관없이 $\textbf y=\textbf z$이므로 알고리즘은 항상 $\text{YES}$를 출력합니다.

• 건전성: $C\neq AB$일 때 알고리즘은 최소 $1-(n-1)/p$의 확률로 $\text{NO}$를 출력합니다.

먼저 완전성은 자명하게 보여집니다. 이제 건전성을 증명하기 위해, $C\neq AB$일 때 $\textbf y\neq \textbf z$일 최소 확률을 구해보겠습니다.

$C\neq AB$이므로 $C_i\neq (AB)_i$ ($i$번째 행) 인 인덱스 $i$가 존재합니다. 이 $i$에 대하여 $\textbf y_i=(C\textbf x)_i$를 보면,

$$\begin{align*} (C\textbf x)_i&=C_i\cdot(1, r, r^2, \cdots, r^{n-1})\\ &=\sum_{j=0}^{n-1} C_{ij}\cdot r^j =p_{C_i}(r). &&\text{(Reed-Solomon Code of $C_i$)} \end{align*}$$

마찬가지로 $\textbf z_i=(AB\textbf x)_i=p_{(AB)_i}(r)$ 으로 $(AB)_i$ 벡터의 R-S 핑거프린팅 값이 됩니다. 따라서 $\textbf y_i\neq\textbf z_i$ 일 확률은 두 R-S 코드 값이 다를 확률과 같고, 이는 앞에서 보았듯 최소 $1-(n-1)/p$ 가 됩니다. 그러므로 전체 벡터 $\textbf y\neq \textbf z$ 일 확률 또한 최소 $1-(n-1)/p$ 가 되어 증명이 끝납니다.

Univariate Lagrange Interpolation

앞서 Reed-Solomon 인코딩에서 우리는 벡터 $a$를 $n-1$차 다항식의 계수로 해석했습니다 ($p_a(x)=\sum_{i=0}^{n-1} a_ix^i$). 이번에는 라그랑주 보간법(Lagrange Interpolation)이라는 새로운 방법을 이용해 벡터의 각 원소 $a_i$를 $i$에 대한 다항식의 값으로 해석해 보겠습니다. 구체적으로, 벡터 $a$를 다항식 $q_a(x)$로 인코딩할 때, 각각의 인덱스 $i=0,1,\cdots,n-1$에 대하여 $y=q_a(x)$가 점 $(i, a_i)$를 지나도록 설정합니다.

$$\begin{aligned} q_a(0) &= a_0 \\ q_a(1) &= a_1 \\ &\vdots \\ q_a(n-1) &= a_{n-1} \\ \end{aligned}$$

이 과정을 단일변수 라그랑주 보간법(Univariate Lagrange Interpolation)이라고 부릅니다. 우리는 다음 보조정리에서 이러한 다항식 $q_a$가 유일하게 존재함을 보이겠습니다.

보조정리 2.2 (단일변수 라그랑주 보간법). $p$는 $n$ 보다 큰 소수이고 벡터 $a=(a_0,\cdots,a_{n-1})\in \mathbb F_p^n$ 라고 하자. 다음 식을 만족하며 차수가 최대 $n-1$인 단일변수 다항식 $q_a$는 유일하게 존재한다:

$$q_a(i)=a_i\ (\forall i=0,1,\cdots,n-1)$$

존재성을 증명하기 위해, 위 조건을 만족하는 다항식을 직접 구해보겠습니다.

기저 다항식

먼저, 각 인덱스 $i$에 대해 라그랑주 기저 다항식(Lagrange basis polynomials)을 다음과 같이 정의합니다. 이 때, $[n]$은 $\{0, 1, 2, \dots, n-1\}$을 나타냅니다.

$$\delta_i(x)=\prod_{k \in [n] \setminus \{i\}}\frac{x-k}{i-k}$$

위와 같이 설정하는 이유는, $\delta_i(x)$는 $x=i$에서 함숫값 $1$을 가지며 다른 모든 $x=0,1,\cdots,n-1$ 에 대해서 $0$이 되기 때문입니다. 또한 $k \neq i$의 조건이 들어가는 이유는 0으로 나누는 것을 막기 위함입니다. 구체적인 예시를 함께 살펴보겠습니다.

$$\begin{align*} \delta_0(X) &= \frac{(X-1)\cdot (X-2)\cdot (X-3)}{(0-1)\cdot (0-2)\cdot (0-3)} = -6^{-1}\cdot (X-1)(X-2)(X-3), \\[1em] \delta_1(X) &= \frac{(X-0)\cdot (X-2)\cdot (X-3)}{(1-0)\cdot (1-2)\cdot (1-3)} = 2^{-1}\cdot X(X-2)(X-3), \\[1em] \delta_2(X) &= \frac{(X-0)\cdot (X-1)\cdot (X-3)}{(2-0)\cdot (2-1)\cdot (2-3)} = -2^{-1}\cdot X(X-1)(X-3), \\[1em] \delta_3(X) &= \frac{(X-0)\cdot (X-1)\cdot (X-2)}{(3-0)\cdot (3-1)\cdot (3-2)} = 6^{-1}\cdot X(X-1)(X-2). \end{align*}$$

위 예시에서 $\delta_0(x)$를 보면 $x=0$일 때는 함숫값이 $1$이고, 나머지 $x=1,2,3$일 때는 함숫값이 $0$임을 확인할 수 있습니다.

라그랑주 다항식

이제 기저 다항식을 이용해 라그랑주 다항식을 만들어 보겠습니다. 다항식 $q_a(x)$를 다음과 같이 정의합니다:

$$q_a(x) = \sum_{j=0}^{n-1} a_{j}\cdot \delta_j(x).$$

$x=i$에서 함숫값을 살펴보면, $\delta_j(i)$는 모든 $j\neq i$에 대해서 0이 되어 사라지므로 $j=i$일 때 값 $a_j$를 제외하고 모두 사라짐을 알 수 있습니다. 따라서 모든 $i=0,\cdots,n-1$에 대하여 $q_a(i)=a_i$ 이고, 이는 보조정리 2.2 의 조건을 만족합니다.

유일성 또한 간단히 보일 수 있습니다. 차수가 최대 $n-1$인 두 다항식은 정리 2.1에 의해 최대 $n-1$개의 교점을 가질 수 있습니다. 만약 차수가 최대 $n-1$이고 보조정리 2.2의 조건을 만족하는 다른 다항식이 존재한다면, 이는 우리가 구한 $q_a(x)$와 $n$개의 교점을 가지므로 모순입니다.

함숫값 구하기

마지막으로 라그랑주 다항식 $q_a(x)$의 함숫값을 구하는 트릭에 대해 알아보겠습니다. 임의의 $r\in\mathbb F_p$ 에 대하여,

$$q_a(r) = \sum_{j=0}^{n-1} a_{j}\cdot \delta_j(r)$$

를 계산하는 것이 목표입니다. $r=0,1,\cdots,n-1$의 함숫값은 알고 있으므로 이들을 제외한 $r$ 값을 가정하겠습니다. 만약 라그랑주 기저 다항식 $\delta_j(x)$을 직접 계산한다면, 각각의 $j$에 대해 $O(n)$의 시간이 걸리므로 총 $O(n^2)$의 시간 복잡도가 필요할 것입니다. 그러나 우리는 $x=r$에서 두 기저 다항식에 대해 다음과 같은 점화식을 세울 수 있습니다: (기저 다항식의 정의에 주목하세요)

$$\delta_i(r) = \delta_{i-1}(r)\cdot (r-(i-1)) \cdot (r-i)^{-1} \cdot i^{-1} \cdot (i-n).$$

이를 활용하면 $q_a(r)$값을 시간 복잡도 $O(n)$만에 계산할 수 있습니다!