# GKR & Sum-check Protocol - how are the random numbers split across different variables?

I am reading about GKR protocol from Justin Thaler's book - Proofs, Arguments & Zero Knowledge

Section 4.6.5 - Page 64 - Description of GKR Protocol

$$S_0$$ is the number of gates in layer 0.

$$k_0 = \log(S_0)$$

$$V$$ picks a random $$r_0 \in F^{k_0}$$ and lets $$m_0 = \tilde D(r_0)$$. The remainder of the protocol is devoted to confirming that $$m_0 = \tilde W_0(r_0)$$

Now $$k_0$$ is the maximum number of bits in the gate label/gate number - $$\tilde W_0$$ is $$k_0$$-variate Polynomial.

So now when $$r_0$$ is picked, how does $$P$$ split it in order to evaluate $$W_0$$ - i.e. if say $$k_0 = 4$$, then $$r_0$$ would need to be decomposed into 4 values so that you can pass those as $$x_1, x_2, x_3, x_4$$. Or am I mistaken here? So how is this decomposition done - on what boundaries? Or is the technique different?

Likewise, in the Sum-check protocol in section 4.3, Counting Triangles.

Now though the book represents $$f_A$$ as taking 2 params $$f_A(X,Y)$$ as per this answer, this is only notational & based on the dimensions of the adjacency matrix, $$f_A$$ is actually $$f_A(x_1, x_2, x_3, ...)$$

So on Page 45, when 3 random values are picked & $$r_1, r_2, r_3$$, $$\tilde f_A(r_3,r_3),\tilde f_A(r_1,r_3)$$ evaluated, how is each of $$r_1, r_2, r_3$$ decomposed into individual $$x_1, x_2 ...$$ etc?

$$W$$ is a function from $$\{0,1\}^{k_0}$$ to $$\mathbb{F}$$, but both $$\tilde{W}$$ and $$\tilde{D}$$ are functions from $$\mathbb{F}^{k_0}$$ to $$\mathbb{F}$$. The text says that $$r_0$$ belongs to $$\mathbb{F}^{k_0}$$, thus, it is in the domain of both $$\tilde{W}$$ and $$\tilde{D}$$, therefore, the evaluation $$\tilde{D}(r_0)$$ is already well-defined and no decomposition or extra technique is needed.

You would need a "decomposition" or some sort of "extension" if $$r_0$$ were an element of $$\mathbb{F}$$ instead of a $$k_0$$-dimensional vector of elements of this field.

As for the functions $$f_A$$ and $$\tilde{f_A}$$, you have to interpret $$X$$ and $$Y$$ as vectors as well.

Notice that saying that a function $$F$$ has as input two elements (vectors) of $$\{0,1\}^k$$ or that it has as input $$2k$$ elements of $$\{0,1\}$$ is basically the same.

• $F$ is a function takes input from $\lbrace 0, 1 \rbrace^{k_0}$. However, $\tilde F$ is an extension. It takes any value from $\mathbb F$, right? i.e. it's no longer limited to $\lbrace 0, 1 \rbrace^{k_0}$ - you are picking $r_1$ from $\mathbb F$ & not from $\lbrace 0, 1 \rbrace^{k_0}$. So after picking $r_1$, don't you have to decompose it into a vector? Or am I wrong? Commented Apr 21 at 2:49
• If $k_0 = 3$, then $\tilde W$ is 3-variate polynomial. When you pick $r_0$, how to get $x_1,x_2,x_3$ to pass to $\tilde W?$ Likewise for $\tilde{f_A}$, when you pick $r_1, r_2,r_3$, you need to do decompose $r_1$ into multiple elements to form the vector $X$ & likewise for $r_2, r_3$ & $Y$ & $Z$ respectively, right? Commented Apr 21 at 2:55
• The reason it's called a low degree extension is because the domain of the MLE is much bigger than $\lbrace 0,1\rbrace^{k_0}$ - i.e. though the map is from $\lbrace 0,1\rbrace^{k_0}$, the MLE's domain is $\mathbb F^v$ - i.e. each of the $v$ variables can take any value from $\mathbb F$ Commented Apr 21 at 3:05
• No, $\tilde{F}$ does not take a value from $\mathbb{F}$. It is a multivariate polynomial over $\mathbb{F}$, this means it takes $k_0$ variables from $\mathbb{F}$, in other words, its input is a vector from $\mathbb{F}^{k_0}$, that is why in page 64 it is written $r_0 \in \mathbb{F}^{k_0}$, instead of $r_0 \in \mathbb{F}$ Commented Apr 21 at 10:29
• So you mean, when it says pick $r_0$, it means, pick $k_0$ random numbers $\in F$. And likewise in Counting Triangles, when it says pick Random $r_1, r_2, r_3$, it means pick $3*v$ random numbers? Commented Apr 21 at 10:53