In this part, we build on Part 2 and 3 to develop a protocol for verifiable blind evaluation of polynomials, which we will define shortly. In Part 5 we'll start to see how such a protocol can be used for constructing SNARKs, so bear with me a little bit longer for the connection to SNARKs.

Suppose, as in Part 2, that Alice has a polynomial $P$ of degree $d$ and Bob has a point $s \in \mathbb{F}_p$ that he chose randomly. We want to construct a protocol that allows Bob to learn $E(P(s))$,i.e., the hiding of $P$ evaluated at $s$, with two additional properties:

• Blindness: Alice will not learn $s$, and Bob will not learn $P$.
• Verifiability: The probability that Alice sends a value not of the form $E(P(s))$ for $P$ of degree $d$ that is known to her, but Bob still accepts, is negligible.

This is what we call verifiable blind evaluation of a polynomial. The protocol in Part 2 gave us the first item but not the second. To get verifiability, we need an extended version of the Knowledge of Coefficient Assumption (KCA) that was presented in Part 3.

The verifiability and blindness properties are useful together because they make Alice decide what polynomial $P$ she will use without seeing $s$.[1]This, in a sense, commits Alice to an "answer polynomial" without seeing the "challenge point" $s$. This intuition will become clearer in the next parts of the series.

An Extended KCA

The KCA as we defined it in Part 3 essentially said something like this: If Bob gives Alice some $\alpha$-pair $(a,b = \alpha \cdot a)$ and then Alice generates another $\alpha$-pair $(a',b')$, then she knows $c$ such that $a'=c \cdot a$. In other words, Alice knows the relation between $a'$ and $a$.

Now, suppose that instead of one, Bob sends Alice several $\alpha$-pair $(a_1, b_1),...,(a_d, b_d)$ (for the same $\alpha$); and that again, after receiving these pairs, Alice is challenged to generate some other $\alpha$-pair $(a^{'}, b^{'})$. Recall that the main point is that Alice must do so although she does not know $\alpha$.

As we saw in Part 3, a natural way for Alice to generate such an $\alpha$-pair, would be to take one of the pairs $(a_i,b_i)$ she received from Bob, and multiply both elements by some $c \in \mathbb{F}^*_p$; if $(a_i,b_i)$ was an $\alpha$-pair, then $(c \cdot a_i,c \cdot b_i)$ will be one too. But can Alice generate $\alpha$-pairs in more ways now that she's received multiple $\alpha$-pairs? Perhaps using several of the received $\alpha$-pairs simultaneously to get a new one?

The answer is yes: For example, Alice can choose two values $c_1,c_2 \in \mathbb{F}_p$ and compute the pair $(a',b') =$ $(c_1 \cdot a_1 + c_2 \cdot a_2,$ $c_1 \cdot b_1 + c_2 \cdot b_2)$. An easy computation shows that, as long as $a'$ is non-zero, this is also an $\alpha$-pair:

$b' = c_1 \cdot b_1 + c_2 \cdot b_2 = c_1 \alpha \cdot a_1 + c_2 \alpha \cdot a_2 = \alpha (c_1 \cdot a_1 + c_2 \cdot a_2) = \alpha \cdot a'$.

More generally, Alice can take any linear combination of the given $d$ pairs - that is choose any $c_1,\ldots,c_d \in \mathbb{F}_p$ and define $(a',b')=(\sum_{i=1}^d c_i a_i, \sum_{i=1}^d c_ib_i)$.

Note that if Alice uses this strategy to generate her $\alpha$-pair, she will know some linear relation between $a^{'}$ and $a_1,...,a_d$; that is, she knows $c_1,...,c_d$ such that $a^{'} = \sum_{i=1}^d c_i \cdot a_i$.

The extended KCA states, essentially, that this is the only way Alice can generate an $\alpha$-pair; that is, whenever she succeeds, she will know such a linear relation between $a^{'}$ and $a_1,...,a_d$. More formally, suppose that $G$ is a group of size $p$ with generator $g$, written additively as in Part 3. The $d$-power Knowledge of Coefficient Assumption ($d$-KCA) [2] in $G$ is as follows:

d-KCA: Suppose Bob chooses random $\alpha \in \mathbb{F}_p^*$ and $s \in \mathbb{F}_p$, and sends to Alice the $\alpha$-pairs $(g,\alpha \cdot g)$, $(s \cdot g,\alpha s \cdot g)$,$\ldots$, $(s^d \cdot g,\alpha s^d \cdot g)$. Suppose that Alice then outputs another $\alpha$-pair $(a',b')$. Then, except with negligible probability, Alice knows $c_0,\ldots,c_d \in \mathbb{F}_p$ such that $\sum_{i=0}^d c_i s^i \cdot g = a'$.

Note that in the $d$-KCA Bob does not send an arbitrary set of $\alpha$-pairs, but one with a certain "polynomial structure". This will be useful in the protocol below.

The Verifiable Blind Evaluation Protocol

Assume that our hiding homomorphism (HH) is the mapping $E(x) = x \cdot g$ for a generator $g$ of $G$ as above. For simplicity, we present the protocol for this particular $E$

• Bob chooses a random $\alpha \in \mathbb{F}_p^*$, and sends to Alice the hidings $g$, $s \cdot g$,$\ldots$, $s^d \cdot g$ (of $1$,$s$,$\ldots$,$s^d$) and also the hidings $\alpha \cdot g$, $\alpha s \cdot g$,$\ldots$, $\alpha s^d \cdot g$ (of $\alpha$,$\alpha s$,$\ldots$,$\alpha s^d$).
• Alice computes $a = P(s) \cdot g$ and $b = \alpha P(s) \cdot g$ using the elements sent in the first step, and sends both to Bob.
• Bob checks that $b = \alpha \cdot a$, and accepts if and only if this equality holds.

First, note that given the coefficients of $P$, $P(s) \cdot g$ is a linear combination of $g$, $s \cdot g$,$\ldots$,$s^d \cdot g$; and $\alpha P(s)\cdot g$ is a linear combination of $\alpha \cdot g$, $\alpha s \cdot g$,$\ldots$, $\alpha s^d \cdot g$. Thus, similarly to the protocol of Part 2, Alice can indeed compute these values from Bob's messages for a polynomial $P$ that she knows.

Second, by the d-KCA if Alice sends $a$, $b$ such that $b= \alpha \cdot a$ then almost surely she knows $c_0,\ldots,c_d \in \mathbb{F}_p$ such that $a=\sum_{i=0}^d c_i s^i \cdot g$. In that case, $a = P(s) \cdot g$ for the polynomial $P(X) = \sum_{i=0}^d c_i \cdot X^i$ known to Alice. In other words, the probability that Bob accepts in Step 3 while at the same time Alice does not know such a $P$ is negligible.

To summarize, using the $d$-KCA we've developed a protocol for verifiable blind evaluation of polynomials. In the next posts, we will see how this building block comes to play in SNARK constructions.

[1] In the fully formal proof, things are somewhat more subtle, as Alice does see some information about $s$ before deciding on her $P$-for example, the hiding of $s,...,s^d$.

[2]The d-KCA was introduced in a paper of Jens Groth.