In this part, we build on Part II and III to develop a protocol for verifiable blind evaluation of polynomials, which we will define shortly. In Part V 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 II, that Alice has a polynomial :math:`P` of degree :math:`d` and Bob has a point :math:`sinmathbb{F}_p` that he chose randomly. We want to construct a protocol that allows Bob to learn :math:`E(P(s))`, i.e. the hiding of :math:`P` evaluated at :math:`s`, with two additional properties:
- Blindness: Alice will not learn :math:`s` (and Bob will not learn :math:`P`).
- Verifiability: The probability that Alice sends a value not of the form :math:`E(P(s))` for :math:`P` of degree :math:`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 II 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 III.
The verifiability and blindness properties are useful together because they make Alice decide what polynomial :math:`P` she will use without seeing :math:`s`. [1] This, in a sense, commits Alice to an “answer polynomial” without seeing the “challenge point” :math:`s`. This intuition will become more clear in the next parts of the series.
An Extended KCA
The KCA as we defined it in Part III essentially said something like this: If Bob gives Alice some :math:`alpha`-pair :math:`(a,b = alphacdot a)` and then Alice generates another :math:`alpha`-pair :math:`(a’,b’)`, then she knows :math:`c` such that :math:`a’=ccdot a`. In other words, Alice knows the relation between :math:`a’` and :math:`a`.
Now, suppose that instead of one, Bob sends Alice several :math:`alpha`-pairs :math:`(a_1,b_1),ldots,(a_d,b_d)` (for the same :math:`alpha`); and that again, after receiving these pairs, Alice is challenged to generate some other :math:`alpha`-pair :math:`(a’,b’)`. Recall that the main point is that Alice must do so although she does not know :math:`alpha`.
As we saw in Part III, a natural way for Alice to generate such an :math:`alpha`-pair, would be to take one of the pairs :math:`(a_i,b_i)` she received from Bob, and multiply both elements by some :math:`cinmathbb{F}^*_p`; if :math:`(a_i,b_i)` was an :math:`alpha`-pair, then :math:`(ccdot a_i,ccdot b_i)` will be one too. But can Alice generate :math:`alpha`-pairs in more ways now that she’s received multiple :math:`alpha`-pairs? Perhaps using several of the received :math:`alpha`-pairs simultaneously to get a new one?
The answer is yes: For example, Alice can choose two values :math:`c_1,c_2in mathbb{F}_p` and compute the pair :math:`(a’,b’)=(c_1cdot a_1 + c_2cdot a_2, c_1cdot b_1 + c_2cdot b_2)`. An easy computation shows that, as long as :math:`a’` is non-zero, this is also an :math:`alpha`-pair:
:math:`b’ = c_1cdot b_1 + c_2 cdot b_2 = c_1 alpha cdot a_1 + c_2alphacdot a_2 = alpha (c_1cdot a_1 + c_2cdot a_2) = alphacdot a’.`
More generally, Alice can take any linear combination of the given :math:`d` pairs – that is choose any :math:`c_1,ldots,c_dinmathbb{F}_p` and define :math:`(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 :math:`alpha`-pair she will know some linear relation between :math:`a’` and :math:`a_1,ldots,a_d`; that is, she knows :math:`c_1,ldots,c_d` such that :math:`a’=sum_{i=1}^d c_icdot a_i`.
The extended KCA states, essentially, that this is the only way Alice can generate an :math:`alpha`-pair; that is, whenever she succeeds, she will know such a linear relation between :math:`a’` and :math:`a_1,ldots,a_d`. More formally, suppose that :math:`G` is a group of size :math:`p` with generator :math:`g` written additively as in Part III. The d-power Knowledge of Coefficient Assumption (d-KCA) [2] in :math:`G` is as follows:
d-KCA: Suppose Bob chooses random :math:`alphainmathbb{F}_p^*` and :math:`sinmathbb{F}_p`, and sends to Alice the :math:`alpha`-pairs :math:`(g,alphacdot g), (scdot g,alpha scdot g),ldots,(s^dcdot g,alpha s^dcdot g)`. Suppose that Alice then outputs another :math:`alpha`-pair :math:`(a’,b’)`. Then, except with negligible probability, Alice knows :math:`c_0,ldots,c_dinmathbb{F}_p` such that :math:`sum_{i=0}^d c_i s^icdot g = a’`.
Note that in the d-KCA Bob does not send an arbitrary set of :math:`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 HH is the mapping :math:`E(x)=xcdot g` for a generator :math:`g` of :math:`G` as above.
For simplicity, we present the protocol for this particular :math:`E`:
- Bob chooses a random :math:`alphainmathbb{F}_p^*`, and sends to Alice the hidings :math:`g,scdot g,ldots,s^dcdot g` (of :math:`1,s,ldots,s^d`) and also the hidings :math:`alphacdot g,alpha s cdot g,ldots,alpha s^dcdot g` (of :math:`alpha,alpha s,ldots,alpha s^d`).
- Alice computes :math:`a=P(s)cdot g` and :math:`b=alpha P(s)cdot g` using the elements sent in the first step, and sends both to Bob.
- Bob checks that :math:`b=alpha cdot a`, and accepts if and only if this equality holds.
First, note that given the coefficients of :math:`P`, :math:`P(s)cdot g` is a linear combination of :math:`g,scdot g,ldots,s^dcdot g`; and :math:`alpha P(s)cdot g` is a linear combination of :math:`alphacdot g,alpha s cdot g,ldots,alpha s^dcdot g`. Thus, similarly to the protocol of Part II, Alice can indeed compute these values from Bob’s messages for a polynomial :math:`P` that she knows.
Second, by the d-KCA if Alice sends :math:`a`, :math:`b` such that :math:`b=alpha cdot a` then almost surely she knows :math:`c_0,ldots,c_dinmathbb{F}_p` such that :math:`a=sum_{i=0}^d c_is^icdot g`. In that case, :math:`a=P(s)cdot g` for the polynomial :math:`P(X)=sum_{i=0}^d c_icdot 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 :math:`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 :math:`s` before deciding on her :math:`P` – for example, the hidings of :math:`s,ldots,s^d`. |
| [2] | The d-KCA was introduced in a paper of Jens Groth. |
