Sum-Check Protocol

본 글에서는 상호작용 증명(IP)의 예시, Sum-Check 프로토콜에 대해 알아보겠습니다.

Settings

유한체 $\mathbb F$ 위에서 정의된 $v$-변수 다항식 $g(x_1,\dots, x_v)$ 를 생각해보겠습니다. 이 때 Sum-check 프로토콜은 증명자가 다음 함숫값들의 합을 검증자에게 증명하는 것입니다:

$$S := \sum_{b_1 \in \{0,1\}} \sum_{b_2 \in \{0,1\}} \cdots \sum_{b_v \in \{0,1\}} g(b_1, \ldots, b_v).$$

해당 $S$ 값을 계산하는 데에는 $O(2^v\cdot T)$ 시간이 소요됩니다 ($g$의 함숫값을 구하는데 걸리는 시간을 $T$라 하겠습니다.) 그러나 Sum-check 프로토콜을 이용하면, 해당 $S$ 값을 $O(v+T)$ 정도 시간으로 검증 가능합니다!

Protocol

Sum-check 프로토콜은 다음과 같이 이루어집니다:

1

증명자 $\mathcal P$가 검증자 $\mathcal V$에게 $C_1$ (증명하고자 하는 $S$) 값을 전송합니다.

2

First round

$\mathcal P$가 $\mathcal V$에게 일변수 다항식

$$g_1(X_1)=\sum_{(x_2, \ldots, x_v) \in \{0,1\}^{v-1}} g(X_1, x_2, \ldots, x_v)$$

을 보냅니다.

$\mathcal V$는 $g_1(X_1)$이 차수가 최대 $\deg_1(g)$ (= 다항식 $g$의 변수 $x_1$에 대한 차수) 인 일변수 다항식이며

$$C_1=g_1(0)+g_1(1)$$

이 성립하는지 확인합니다. 그렇지 않을경우 reject 합니다.

이 때, $g_1(X_1)$ 가 정의에 따라 계산되었다는 사실 또한 $\mathcal P$의 주장이기에 이를 검증해야 합니다. 우리는 이를, $x_1=r_1$ 으로 고정한 뒤 $(v-1)$-변수 다항식 $g(r_1,x_2,\ldots,x_v)$ 에 대해 재귀적으로 Sum-check 프로토콜을 돌리는 방식으로 해결합니다.

3

$\mathcal V$ 가 랜덤한 값 $r_1\in\mathbb F$ 를 골라 $\mathcal P$에게 전송합니다.

4

j-th round (1 < j < v)

$\mathcal P$가 $\mathcal V$에게 일변수 다항식

$$g_j(X_j)=\sum_{(x_{j+1}, \ldots, x_v) \in \{0,1\}^{v-j}} g(r_1, \ldots, r_{j-1}, X_j, x_{j+1}, \ldots, x_v)$$

를 보냅니다. 마찬가지로 $\mathcal V$는 $g_j(X_j)$이 차수가 최대 $\deg_j(g)$ 인 일변수 다항식이며

$$g_{j-1}(r_{j-1})=g_j(0)+g_j(1)$$

이 성립하는지 확인합니다. 그렇지 않을경우 reject 합니다.

5

$\mathcal V$ 가 랜덤한 값 $r_j\in\mathbb F$ 를 골라 $\mathcal P$에게 전송합니다.

6

v-th round

$\mathcal P$가 $\mathcal V$에게 일변수 다항식

$$g_v(X_v)=g(r_1, \ldots, r_{v-1}, X_v)$$

를 보냅니다. $\mathcal V$는 $g_v(X_v)$이 차수가 최대 $\deg_v(g)$ 인 일변수 다항식이며

$$g_{v-1}(r_{v-1})=g_v(0)+g_v(1)$$

이 성립하는지 확인합니다. 그렇지 않을경우 reject 합니다.

7

$\mathcal V$ 가 랜덤한 값 $r_v\in\mathbb F$ 를 골라, $g$에 한번의 오라클로 $g(r_1,\ldots,r_v)$ 값을 구합니다. 그리고 $g_v(r_v)=g(r_1,\ldots,r_v)$ 가 성립하는지 확인하고 아닐경우 reject 합니다.

8

만약 $\mathcal V$가 한번도 reject 하지 않았다면, 프로토콜을 종료하고 accept 합니다.

Completeness & Soundness

명제 4.1. Sum-check 프로토콜은 완전성 오류 $\delta_c=0$ 이고 건전성 오류 $\delta_s\leq vd/|\mathbb F|$ 인 IP 시스템이다. ($d=\max_{1\leq j\leq v}\deg_j(g)$)

Proof. 먼저 완전성은 자명합니다. $j$-번째 라운드까지 증명자가 올바른 $g_j(X_j)$를 보냈다면, $g_j(X_j)$는 차수가 최대 $\deg_j(g)$ 이고 $g_{j-1}(r_{j-1})=g_j(0)+g_j(1)$ 는 정의에 따라 성립합니다.

이제 건전성 오류 $\delta_s\leq vd/|\mathbb F|$ 를 증명해보겠습니다. 이를 위해 $C_1\neq S$에 대해서 위 프로토콜이 accept할 최대 확률을 계산하면 됩니다. 이 경우 적어도 하나의 라운드 $j$에서 $\mathcal P$가 전송한 $g_j(X_j)$ 가 실제 다항식

$$s_j(X_j)=\sum_{(x_{j+1}, \ldots, x_v) \in \{0,1\}^{v-j}} g(r_1, \ldots, r_{j-1}, X_j, x_{j+1}, \ldots, x_v)$$

와 다르면서 ($g_j\neq s_j$), 랜덤한 $r_j\in\mathbb F$에 대해 $g_j(r_j)=s_j(r_j)$ 가 성립해야합니다. 두 다항식의 차수는 최대 $d$이므로, Schwartz-Zippel Lemma에 의해 그 확률은 최대 $d/|\mathbb F|$ 입니다. 따라서 Union bound에 의해:

$$\Pr \left [\cup_{1\leq j\leq v}\ (g_j\neq s_j \land g_j(r_j)=s_j(r_j)) \right ] \leq \sum_{1\leq j\leq v} \Pr \left [g_j\neq s_j \land g_j(r_j)=s_j(r_j) \right ] \leq \frac{vd}{|\mathbb F|}.$$

Costs

Communication	Rounds	$\mathcal{V}$ time	$\mathcal{P}$ time
$O(\sum_{i=1}^{v} \deg_i(g))$ field elements	$v$	$O(v + \sum_{i=1}^{v} \deg_i(g)) + T$	$O(\sum_{i=1}^{v} \deg_i(g) \cdot 2^{v - i} \cdot T)$

표 4.1. Sum-check 프로토콜의 costs.

각 라운드에서 $\mathcal P$ 가 $\mathcal V$ 에게 전송하는 다항식 $g_j(X_j)$는 계수 표현으로 $1+\deg_i (g)$ 개 field elements 입니다. 더 나아가 라그랑주 보간법을 활용하면 다항식을 계수 표현이 아니라 함숫값 $1+\deg_i (g)$ 개로도 나타낼 수 있습니다. 따라서 총 $v$ 라운드에 대해 $\sum_{i=1}^{v} (1+\deg_i(g))=v+\sum_{i=1}^{v} \deg_i(g)$ 개 원소가 커뮤니케이션에 사용됩니다.

$\mathcal V$의 시간복잡도는 각 라운드에서 $g_i(r_i)$ 값을 계산할 때 $1+\deg_i (g)$ 번 연산이 필요하고, 최종 라운드 $v$에서 $g$에 오라클할때 $T$의 시간이 소요되므로 총 $O(v + \sum_{i=1}^{v} \deg_i(g)) + T$ 입니다.

$\mathcal P$의 시간복잡도는 각 라운드에서 다항식 $g_j(X_j)$ 를 계산하는 것이 전부인데, 이는 위에서 살펴보았듯 라그랑주 보간법을 사용하여 $i=0,1,\ldots,\deg_j(g)$ 일 때 함숫값 $g_j(i)$를 계산함으로써 가능합니다:

$$g_j(i)=\sum_{(x_{j+1}, \ldots, x_v) \in \{0,1\}^{v-j}} g(r_1, \ldots, r_{j-1}, i, x_{j+1}, \ldots, x_v).$$

따라서 $\mathcal P$의 시간복잡도는 $O(\sum_{i=1}^{v} \deg_i(g) \cdot 2^{v-i} \cdot T)$ 입니다.

앞으로의 예시에서 어떤 함수 $g$의 multilinear extension $\tilde g$ 에 sum-check를 적용시키는 경우가 많은데, 이 경우 모든 라운드 $i$에 대해 $\deg_i(g)=O(1)$ 이므로 전체 시간복잡도는 다음과 같이 정리됩니다.

Communication	Rounds	$\mathcal{V}$ time	$\mathcal{P}$ time
$O(v)$ field elements	$v$	$O(v + T)$	$O(2^{v} \cdot T)\quad$

표 4.2. 모든 $i$에 대해 $\deg_i(g)=O(1)$ 인 경우 Sum-check 프로토콜의 costs.

Application 1: #SAT

변수 $x_1,\dots,x_n$의 Boolean formula 란 각 leaf node가 변수 $x_i$나 그 negation을 라벨로 가지며, 각 internal node 는 두 자식 노드의 AND나 OR 을 취한 결과를 가지는 binary tree 입니다. 이 때 트리의 각 노드를 gate라고 부르며, 트리의 root는 해당 formula의 출력값입니다.

이 때 (Boolean) formula에서 이진 트리 조건을 없애고, 각 노드의 결과값을 재사용할 수 있게 한 것 (각 노드의 in-degree (fan-in)는 2이나 out-degree (fan-out)에 제한이 없음) 이 (Boolean) circuit 입니다.

#SAT problem

사진 4.1. 4개 변수에 대한 크기가 8인 Boolean formula.

크기 $S=\text{poly}(n)$ 인 Boolean formula $\phi$에 대해, $\phi(x): \{0,1\}^n\to \{0,1\}$ 를 n개의 boolean 변수 값을 입력으로 받아 formula의 출력값을 반환하는 함수로 정의하겠습니다. $\text{\#SAT}$ 문제란 $\phi(x)=1$이 되도록 하는 입력 $x$의 개수를 찾는 문제입니다. 현재까지 알려진 $\text{\#SAT}$ 문제를 해결하는 가장 효율적인 알고리즘은 $n$에 대한 지수 시간을 필요로 합니다. 그러나, 해당 문제를 검증하는 IP는 Sum-check 프로토콜을 적용하여 효율적으로 수행할 수 있습니다.

Protocol

우리가 계산하고자 하는 값은 다음과 같이 정의할 수 있습니다:

$$\#(\text{SAT})=\sum_{x \in \{0,1\}^n} \phi(x).$$

먼저, 다음과 같은 과정을 거쳐 boolean formula $\phi$를 arithmetic circuit $\psi$로 전환시킵니다: (Arithmetic circuit이란 연산이 finite field $\mathbb F$ 위의 덧셈과 곱셈으로 이루어진 circuit을 말합니다.) $\phi$의 모든 AND 게이트를 곱셈 게이트로 변환하고 ($\text{AND}(y,z)\mapsto y\cdot z$), 모든 OR 게이트는 다음 연산을 수행하는 3개의 게이트로 변환합니다 ($\text{OR}(y,z)\mapsto y+z-y\cdot z$). 변수의 negation은 $\bar y\mapsto 1-y$ 게이트로 변환합니다.

이렇게 만든 $\psi$는 모든 $x\in\{0,1\}^n$에 대해 $\psi(x)=\phi(x)$ 를 만족하며, circuit의 크기는 최대 $3S$ 입니다. 뿐만아니라 모든 게이트가 arithmetic하므로 해당 $\psi(x)$를 변수 $x_1,\ldots,x_n$에 대한 $n$-변수 다항식 $g$로 표현할 수 있습니다. 여전히, $\sum_{x \in \{0,1\}^n} \phi(x)=\sum_{x \in \{0,1\}^n} g(x)$ 가 성립하므로 다항식 $g$에 대해 sum-check 프로토콜을 수행하면 끝이 납니다.

Costs

한가지 주목할 부분은, $\sum_{i=1}^n\deg_i(g)\leq S$ 라는 것입니다. (이는 귀납법으로 증명할 수 있습니다. 자세한 증명은 연습문제로 해보시길 바랍니다.) 또한 임의의 $g(r)$ ($r\in\mathbb F^n$)을 계산하는 시간 $T$는, circuit $\psi$의 각 게이트를 따라 결과값을 계산하면 되므로 $O(S)$ 입니다. 위 결과들을 앞서 정리한 sum-check의 cost에 적용시키면, 건전성 오류 $\delta_s\leq S/|\mathbb F|$이며 총 cost는 다음과 같습니다:

Communication	Rounds	$\mathcal{V}$ time	$\mathcal{P}$ time
$O(S)$ field elements	$n$	$O(S)$	$O(2^{n} \cdot S^2)\quad$

표 4.3. 변수 $n$개, 크기 $S$의 Boolean formula $\phi$에 대한 #SAT 프로토콜의 costs

Application 2: Counting Triangles in Graphs

$n$개의 정점에서 정의된 (undirected) 그래프 $G=(V,E)$ 와 그 인접행렬 $A\in\{0,1\}^{n\times n}$ 를 고려하겠습니다. Counting triangles 문제는 $(i,j),(j,k),(k,i)$가 edge로 연결된 세 쌍 $i,j,k\in V$의 개수를 세는 것입니다. 해당 문제 또한 Sum-check를 적용하여 검증할 수 있습니다.

Protocol

먼저, 인접행렬 $A$를 행렬이 아니라 index $(i,j)\in\{0,1\}^{\log n}\times\{0,1\}^{\log n}$ 를 input으로 받아 $A_{ij}\ (\in\{0,1\})$ 를 출력하는 함수 $f_A(i,j)$ 로 생각해보겠습니다. 그러면 우리가 구하고자 하는 값 $\Delta$는 다음과 같이 계산할 수 있습니다 (중복 제거를 위해 $1/6$이 곱해짐에 유의하세요):

$$\Delta = \frac{1}{6} \sum_{x,y,z \in \{0,1\}^{\log n}} f_A(x,y) \cdot f_A(y,z) \cdot f_A(x,z).$$

이제 $f_A$의 multilinear extension $\tilde f_A$에 대해, $(3\log n)$-변수 다항식 $g$를 다음과 같이 정의합니다:

$$g(X,Y,Z) = \tilde{f}_A(X,Y) \cdot \tilde{f}_A(Y,Z) \cdot \tilde{f}_A(X,Z).$$

이렇게 하면 $6\Delta = \sum_{x,y,z \in \{0,1\}^{\log n}} g(x,y,z)$ 이므로 $6\Delta$ 값을 $g$에 대한 Sum-check 프로토콜으로 검증할 수 있습니다. 해당 프로토콜의 cost를 살펴보면, 라운드는 총 $3\log n$ 개이고 $\mathcal P$는 $O(2^{3\log n})=O(n^3)$ 개 점에서 $g$를 계산하면 됩니다. $g$는 $(2\log n)$-변수 MLE 다항식 3개의 곱이므로, MLE 함숫값 구하기 테크닉을 이용하면 $O(n^2)$에 구할 수 있습니다. 따라서 $\mathcal V$는 $O(n^2)$, $\mathcal P$는 $O(n^3\cdot n^2)=O(n^5)$ 시간복잡도가 걸립니다.

Improvement

이 때 $\Delta$를 다음과 같이 인접행렬을 이용하여 계산할 수도 있습니다:

$$\Delta = \frac{1}{6}\sum_{i,j \in \{1, \ldots, n\}} (A^2)_{ij} \cdot A_{ij}.$$

마찬가지로 $f_{A^2}, f_A$를 구한뒤 $g(X,Y) = \tilde{f}_{A^2}(X,Y) \cdot \tilde{f}_A(X,Y)$ 에 대해 Sum-check 프로토콜을 적용하면 됩니다. 이 경우 커뮤니케이션과 $\mathcal V$의 cost는 동일하나, 이후 살펴볼 MatMult의 Method 3를 이용하면 $\mathcal P$를 $O(n^2)$ 까지 줄일 수 있습니다!

Application 3: Super-Efficient MatMult

MatMult 문제는 주어진 두 $n\times n$ 행렬 $A,B$에 대해 둘의 곱 $C=AB$를 증명하는 것입니다. 우리는 2장에서 MatMult 문제를 효율적으로 증명하는 Freivalds' Algorithm을 살펴본 바 있습니다. 그러나 해당 알고리즘은 검증을 위해 곱셈 결과 행렬 $C\in\mathbb F^{n\times n}$ 전체를 전송했습니다. 이번 단원에서는 Sum-check 프로토콜을 활용하여 커뮤니케이션 cost를 $O(\log n)$으로 줄여보겠습니다.

Protocol

앞서 살펴봤듯이 행렬 $A,B,C$를 다음과 같은 $f_A,f_B,f_C: \{0,1\}^{\log n}\times\{0,1\}^{\log n}\to \mathbb F$ 함수로 해석할 수 있습니다:

$$f_A(i_1, \ldots, i_{\log n}, j_1, \ldots, j_{\log n}) = A_{ij}.$$

이제 $\tilde f_A,\tilde f_B,\tilde f_C$ 를 각 함수 $f_A,f_B,f_C$ 의 MLE라고 하겠습니다. 행렬 곱의 정의에 의해, 다음이 성립합니다:

$$\tilde{f}_C(x,y) = \sum_{b \in \{0,1\}^{\log n}} \tilde{f}_A(x,b) \cdot \tilde{f}_B(b,y).$$

이제 임의의 $r_1,r_2\in\mathbb F^{\log n}$ 에 대해 $\tilde{f}_C(r_1,r_2)$ 값을 확인함으로써 위 식이 제대로 계산되었는지 검증할 수 있습니다. (Schwartz-Zippel Lemma에 의해 이 방법은 sound합니다.) 따라서 $r_1,r_2$를 고정한 뒤 $(\log n)$-변수 다항식 $g(z):=\tilde f_A(r_1,z)\cdot \tilde f_B(z,r_2)$에 대해 Sum-check 프로토콜을 적용하여 $\tilde f_C(r_1, r_2)$ 값을 검증합니다.

$$\tilde{f}_C(r_1,r_2) = \sum_{z \in \{0,1\}^{\log n}} g(z).$$

Costs

먼저 $g$는 각 변수의 차수가 최대 2인 $(\log n)$-변수 다항식이므로, 라운드는 총 $\log n$ 번이 필요하고, 총 커뮤니케이션은 $O(\log n)$ field elements가 들게됩니다.

$\mathcal V$의 시간복잡도: 검증자 $\mathcal V$가 할 일은 sum-check 프로토콜의 마지막에 $g(r_3)=\tilde f_A(r_1,r_3)\cdot \tilde f_B(r_3,r_2)$ 값을 계산하는 것입니다. 이 때 각 함숫값 $\tilde f_A(r_1,r_3)$ 와 $\tilde f_B(r_3,r_2)$ 을 계산하는 것은 지난 3장 MLE의 함숫값 구하기를 이용해 $O(n^2)$ 으로 가능합니다.

$\mathcal P$의 시간복잡도: 매 $k$ 라운드마다 $\mathcal P$는 다항식

$$g_k(X_k)= \sum_{b_{k+1} \in \{0,1\}} \cdots \sum_{b_{\log n} \in \{0,1\}} g(s_{1}, \ldots, s_{k-1}, X_i, b_{k+1}, \ldots, b_{\log n})$$

를 검증자 $\mathcal V$ 에게 보내야합니다 ($s_1,\dots,s_{k-1}\leftarrow \mathbb F$는 고정). 이 때 $g(z)=\tilde f_A(r_1,z)\cdot \tilde f_B(z,r_2)$ 는 multilinear한 두 다항식의 곱이므로 각 변수의 최대 차수가 2이고, 따라서 $g_k(X_k)$는 최대 2차 다항식입니다. 그러므로 다항식 전체를 보내는 대신, 세 개의 함숫값 $g_k(0),g_k(1),g_k(2)$만 전송해도 검증자는 2차 다항식을 복구할 수 있습니다. 따라서, $\mathcal P$는

$$(s_{1}, \ldots, s_{k-1}, \{0,1,2\}, b_{k+1}, \ldots, b_{\log n}) : (b_{k+1}, \ldots, b_{\log n}) \in \{0,1\}^{\log n - k}$$

꼴의 모든 점에서 $g$의 함숫값을 구해서 더하기만 하면 됩니다. 이러한 점의 개수는 $3\cdot 2^{\log n-k}=3n/2^k$ 개 입니다. 이제 모든 라운드에서 해당 함숫값을 계산하는 3가지 알고리즘을 비교분석 해보겠습니다.

Method 1, $O(n^3)$

각 라운드 $k$에 대해 나이브하게 모든 $3n/2^k$ 점에서 $g$를 계산해봅시다. 앞에서 $g$ 함숫값을 구하는데 $O(n^2)$이 드는것을 확인했으므로 전체 시간복잡도는 다음과 같습니다:

$$O(\sum_{k=1}^{\log n}\frac{3n\cdot n^2}{2^k}) =O(n^3).$$

Method 2, $O(n^2\log n)$

두번째 방법에서는 한가지 관찰이 필요합니다. 행렬 $A$의 각 원소 $A_{ij}$는 구하고자 하는 $n/2^k$개 점들 (일반성을 잃지 않고 $X_k=0,1,2$인 경우 중 하나만 고려) 중 단 하나의 점에서만 $g$ 함숫값에 기여합니다. 따라서, 우리는 각 점들에 대해서 반복문을 돌리는 것이 아니라 각 인덱스 $(i,j)\in \{0,1\}^{\log n}\times\{0,1\}^{\log n}$ 에 대해 반복문을 수행할 수 있는것입니다.

그 방법을 조금 더 자세히 알아보겠습니다. 우리는 $g(z)$를 구하기 위해 $\tilde f_A(r_1,z)$ 와 $\tilde f_B(z,r_2)$를 계산했습니다. 이 때 MLE의 정의에 의해,

$$\widetilde{f}_A(r_1, z) = \sum_{i,j \in \{0,1\}^{\log n}} A_{ij} \chi_{(i,j)}(r_1, z)$$

가 성립합니다. MLE 기저 다항식 $\chi$에서 다음을 관찰해보겠습니다. $z=(s_{1}, \ldots, s_{k-1}, 0, b_{k+1}, \ldots, b_{\log n})$ 의 꼴일때, (앞서 $z_k=0,1,2$ 중 $0$을 가정했습니다)

$$\begin{align*} \chi_{(i,j)}(r_1, z) &= \chi_{i}(r_1)\chi_j(z) \\ &= \chi_{i}(r_1) \cdot \chi_{(j_1,\dots, j_{k-1})}(s_{1}, \dots, s_{k-1}) \\ & \qquad \cdot \chi_{j_k}(0) \\ & \qquad \cdot \chi_{(j_{k+1},\dots, j_{\log n})}(b_{k+1}, \dots, b_{\log n}). \end{align*}$$

이 때, $(b_{k+1}, \ldots, b_{\log n}) \in \{0,1\}^{\log n - k}$ 임에 주목하면 마지막 항이

$$\chi_{(j_{k+1},\cdots, j_{\log n})}(b_{k+1}, \cdots, b_{\log n}) =\begin{cases} 1 & \text{if}\ (j_{k+1},\cdots, j_{\log n})=(b_{k+1}, \cdots, b_{\log n}) \\ 0 & \text{otherwise} \end{cases}$$

임을 알 수 있습니다. 따라서 우리는 고정된 $(i,j)$에 대해 $A_{ij}$가 오직 하나의 $z=(s_{1}, \ldots, s_{k-1}, 0, j_{k+1}, \ldots, j_{\log n})$ 의 함숫값에만 기여한다는 것을 확인했습니다. 이제 나머지 과정은 straightforward합니다. $\chi_{i}(r_1)\cdot \chi_{(j_1,\cdots, j_{k-1})}(s_{1}, \cdots, s_{k-1})\cdot \chi_{j_k}(0)$ 항의 가능한 모든 값은 3장 MLE의 함숫값 계산 테크닉을 이용해 $O(n^2)$ 시간으로 pre-compute 해놓을 수 있습니다. 이제 모든 인덱스 $(i,j)$에 대해 iterate하면서 대응되는 하나의 $z$에 대해,

$$\widetilde{f}_A(z) \leftarrow \widetilde{f}_A(z) + A_{ij} \chi_{i,j}(z)$$

로 업데이트 해주면 끝이납니다. 이 과정 또한 $O(n^2)$이 소요되므로, 라운드 $k$에 대해 총 $O(n^2)$ 시간이 걸립니다. 이를 $\log n$개 라운드에 대해 반복하므로, 총 시간복잡도는 $O(n^2\log n)$ 입니다.

Method 3, $O(n^2)$

세번째 방법에서는 각 라운드에서 전 라운드에서 계산한 $\tilde f_A(r_1,z)$ 를 사용하는 메모이제이션 기법을 이용합니다. 우리는 각 라운드 $k=1,2,\dots,\log n$ 에서 $z=(s_{1}, \ldots, s_{k-1}, \{0,1,2\}, b_{k+1}, \ldots, b_{\log n})$ 일 때 함숫값 $\tilde f_A(z)$ 를 모두 계산해야 합니다. 먼저, 모든 $z \in \{0,1\}^{\log n}$ 에 대한 $\tilde f_A(r_1,z)$ 를 계산합니다 (이는 Method 2의 방법으로 $O(n^2)$ 시간에 가능합니다.)

이후 $\tilde f_A(z)$ 가 multilinear 하다는 성질로부터 다음 점화식이 성립함을 관찰합니다:

$$\begin{align*} \tilde f_A(x_1, x_2, \ldots, x_{\log n}) &= x_1 \cdot \tilde f_A(1, x_2, \ldots, x_{\log n}) + (1 - x_1) \cdot \tilde f_A(0, x_2, \ldots, x_{\log n})\\ &\vdots\\ \tilde f_A(s_{1}, \ldots, s_{k-1}, x_k, \ldots, x_{\log n}) &= x_k \cdot \tilde f_A(s_{1}, \ldots, s_{k-1}, 1, x_{k+1}, \ldots, x_{\log n}) \\ &\qquad + (1 - x_k) \cdot \tilde f_A(s_{1}, \ldots, s_{k-1}, 0, x_{k+1}, \ldots, x_{\log n}). \end{align*}$$

위 식을 이용하면, 라운드 $k$ 일 때 $z=(s_{1}, \ldots, s_{k-1}, \{0,1,2\}, b_{k+1}, \ldots, b_{\log n}) : (b_{k+1}, \ldots, b_{\log n}) \in \{0,1\}^{\log n - k}$에 대한 $\tilde f_A(z)$ 를 다음과 같이 계산할 수 있습니다.

$$\begin{align*} \tilde f_A(s_{1}, \ldots, s_{k-1}, \{0,1\}, x_{k+1}, \ldots, x_{\log n}) &= s_{k-1} \cdot \tilde f_A(s_{1}, \ldots, s_{k-2}, 1, \{0,1\}, x_{k+1}, \ldots, x_{\log n}) \\ &\qquad + (1 - s_{k-1}) \cdot \tilde f_A(s_{1}, \ldots, s_{k-2}, 0, \{0,1\}, x_{k+1}, \ldots, x_{\log n}) \\ \\ \tilde f_A(s_{1}, \ldots, s_{k-1}, 2, x_{k+1}, \ldots, x_{\log n}) &= 2 \cdot \tilde f_A(s_{1}, \ldots, s_{k-1}, 1, x_{k+1}, \ldots, x_{\log n}) \\ &\qquad - 1 \cdot \tilde f_A(s_{1}, \ldots, s_{k-1}, 0, x_{k+1}, \ldots, x_{\log n}). \end{align*}$$

따라서 라운드 $k-1$ 까지 $\tilde f_A(z)$ 가 모두 계산되어 있다면 라운드 $k$에서는 $O(2^{\log n-k})=O(n/2^k)$ 시간과 공간복잡도로 $\tilde f_A(z)$ 를 계산할 수 있습니다. 이 과정을 라운드 $k=\log n$ 까지 반복하면 총 시간복잡도는 $O(\sum_{k=1}^{\log n} n/2^k)=O(n)$ 입니다.

종합하면, 초기값을 계산하는데 $O(n^2)$ 이 걸리고 이를 이용해 $O(n)$ 시간으로 나머지 값들을 계산할 수 있으므로 총 시간복잡도는 $O(n^2)$ 입니다.

Communication	Rounds	$\mathcal{V}$ time	$\mathcal{P}$ time
$O(\log n)$ field elements	$\log n$	$O(n^2)$	$T + O(n^2)$

표 4.4. Super-Efficient MatMult 프로토콜의 costs. $T$는 행렬곱 $C=AB$를 계산하는데 걸리는 시간.

Conclusion

다음 글에서는 유용한 IP 시스템인 GKR 프로토콜에 대해 다뤄보겠습니다. 긴 글 읽어주셔서 감사합니다.