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?


1 Answer 1


$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.

  • $\begingroup$ $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? $\endgroup$
    – user93353
    Commented Apr 21 at 2:49
  • $\begingroup$ 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? $\endgroup$
    – user93353
    Commented Apr 21 at 2:55
  • $\begingroup$ 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$ $\endgroup$
    – user93353
    Commented Apr 21 at 3:05
  • $\begingroup$ 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}$ $\endgroup$ Commented Apr 21 at 10:29
  • $\begingroup$ 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? $\endgroup$
    – user93353
    Commented Apr 21 at 10:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.