Explaining SNARKs Part III: The Knowledge of Coefficient Test and Assumption

<< Part II

In Part II, we saw how Alice can blindly evaluate the hiding :math:`E(P(s))` of her polynomial :math:`P` of degree :math:`d`, at a point :math:`s` belonging to Bob. We called this “blind” evaluation, because Alice did not learn :math:`s` in the process.

However, there was something missing in that protocol – the fact that Alice is able to compute :math:`E(P(s))` does not guarantee she will indeed send :math:`E(P(s))` to Bob, rather than some completely unrelated value.

Thus, we need a way to “force” Alice to follow the protocol correctly. We will explain in part IV precisely how we achieve this. In this post, we focus on explaining the basic tool needed for that – which we call here the Knowledge of Coefficient (KC) Test.

As before, we denote by :math:`g` a generator of a group :math:`G` of order :math:`|G|=p` where the discrete log is hard. It will be convenient from this post onwards to write our group additively rather than multiplicatively. That is, for :math:`\alpha\in\mathbb{F}_p`, :math:`\alpha\cdot g` denotes the result of summing :math:`\alpha` copies of :math:`g`.

The KC Test

For :math:`\alpha\in\mathbb{F}_p^*` [1], let us call a pair of elements :math:`(a,b)` in :math:`G` an :math:`\alpha`-pair if :math:`a,b \neq 0` and :math:`b=\alpha\cdot a.`

The KC Test proceeds as follows.

1. Bob chooses random :math:`\alpha\in\mathbb{F}_p^*` and :math:`a\in G.` He computes :math:`b=\alpha\cdot a.`
2. He sends to Alice the “challenge” pair :math:`(a,b).` Note that :math:`(a,b)` is an :math:`\alpha`-pair.
3. Alice must now respond with a different pair :math:`(a’,b’)` that is also an :math:`\alpha`-pair.
4. Bob accepts Alice’s response only if :math:`(a’,b’)` is indeed an :math:`\alpha`-pair. (As he knows :math:`\alpha` he can check if :math:`b’=\alpha\cdot a’.)`

Now, let’s think how Alice could successfully respond to the challenge. Let’s assume for a second that she knew :math:`\alpha.` In that case, she could simply choose any :math:`a’` in :math:`G,` and compute :math:`b’=\alpha\cdot a’;` and return :math:`(a’,b’)` as her new :math:`\alpha`-pair.

However, as the only information about :math:`\alpha` she has is :math:`\alpha\cdot a` and :math:`G` has a hard discrete log problem, we expect that Alice cannot find :math:`\alpha.`

So how can she successfully respond to the challenge without knowing :math:`\alpha?`

Here’s the natural way to do it: Alice simply chooses some :math:`\gamma\in\mathbb{F}_p^*,` and responds with :math:`(a’,b’)=(\gamma\cdot a,\gamma\cdot b).`

In this case, we have:

:math:`b’=\gamma \cdot b = \gamma \alpha \cdot a = \alpha (\gamma\cdot a) =\alpha \cdot a’,`

so indeed :math:`(a’,b’)` is an :math:`\alpha`-pair as required.

Note that if Alice responds using this strategy, she knows the ratio between :math:`a` and :math:`a’`. That is, she knows the coefficient :math:`\gamma` such that :math:`a’=\gamma\cdot a.`

The Knowledge of Coefficient Assumption [2] (KCA) states that this is always the case, namely:

KCA: If Alice returns a valid response :math:`(a’,b’)` to Bob’s challenge :math:`(a,b)` with non-negligible probability over Bob’s choices of :math:`a,\alpha`, then she knows :math:`\gamma` such that :math:`a’=\gamma\cdot a.`

The KC Test and Assumption will be important tools in Part IV.

What does “Alice knows” mean exactly

You may wonder how we can phrase the KCA in precise mathematical terms; specifically, how do we formalize the notion that “Alice knows :math:`\gamma`” in a mathematical definition?

This is done roughly as follows: We say that, in addition to Alice, we have another party which we call Alice’s Extractor. Alice’s Extractor has access to Alice’s inner state.

We then formulate the KCA as saying that: whenever Alice successfully responds with an :math:`\alpha`-pair :math:`(a’,b’),` Alice’s Extractor outputs :math:`\gamma` such that :math:`a’=\gamma\cdot a.` [3]

Part IV >>