1
$\begingroup$

This is from this video - https://www.youtube.com/watch?v=9VuZvdxFZQo

Bob has a list of length $10^6$. Bob wants to convince Alice that every number in the list is between 1 & 10. Alice needs to verify it with just 2 queries & 99% certainty.

This is the protocol given by Ben

  • $f$ is polynomial created by interpolating all $10^6$ numbers in the list.

  • $g$ is any polynomial of degree $10^7 - 10^6$ i.e. any polynomial of degree 9 million

  • $C(x) = (x-1)(x-2)...(x-10)$

  • $D(x) = (x-1)(x-2)...(x-10^6)$

  • Alice chooses random $x_0 \in \{1, 2, ..., 10^9\}$

  • Let $f(x_0) = \alpha$ & $g(x_0) = \beta$

  • Alice will believe that all numbers in the list are between 1 & 10, if & only if $C(\alpha) = \beta\cdot D(x_0)$

I don't understand why the last statement is true. He gives the completeness & soundness arguments also which I don't understand.

Here is the completeness argument.

  • Let $P(X)$ be the interpolant of $f$

  • Then $C(P(X))$ vanishes on $x_0 \in \{1, 2, ..., 10^6\}$

He goes on beyond this for the completeness argument but the above is what is I didn't first understand.

Why would $C(P(X))$ vanish on $x_0 \in \{1, 2, ..., 10^6\}$?

$P$ vanishes only if $x_0$ is between 1 & 10. But $x_0$ is a random number picked from a huge domain - so with very high probability $P(x_0) \ne 0$ & we don't know the value of $P(x_0)$ also - it can be anything, right? So why would $C(P(X))$ vanish considering it vanishes only at 10 values from 1 to 10?

Also, I think he says this is with 100% probability & not just very high probability, but that's a secondary thing to figure out.

If you do want to look through the video, then you can jump directly to the beginning of this particular protocol at https://www.youtube.com/watch?v=9VuZvdxFZQo&t=765s

$\endgroup$

1 Answer 1

0
$\begingroup$

Important to remember here is that this is a proof of completeness, which is the property that "Bob honest $\rightarrow$ Alice accepts". The lecturer has made the implicit assumption that Bob is honest, i.e. every element of his list is $\in \{1,...,10\}$ and is proving that this results in Alice's acceptance.

Recall that the "interpolant" of any element $w \in \mathbb{k}^n$ is the unique polynomial $ P \in \mathbb{k}[x]$ with $\text{deg} P \leqslant n$ such that $\forall i \in {1,...n}$, $P(i) = w_i$. Hence if Bob is honest, $P$ restricted to $1,...,10^6$ will take only values in $1,...,10$, hence $C \circ P$ vanishes on this set. I believe you have misquoted the slide slightly since the second line of the completeness proof only requires that this vanishes on the domain of interest, $1,...,10^6$.

Note that for any value of $x_0 > 10^6$, $D(x_0) \neq 0$ (in this example case by the fundamental theorem of algebra, in the most general case by the Schwartz–Zippel lemma), hence the relation $$ C(f(x_0)) = g(x_0)D(x_0) $$ would only ever hold when $g(x_0) = 0$ if $C \circ P$ vanished on the entire domain.

$\endgroup$
4
  • $\begingroup$ I have fixed the misquote you referred to $\endgroup$
    – user93353
    Commented Jul 3, 2023 at 7:17
  • $\begingroup$ Recall that the "interpolant" of any element $w \in \mathbb{k}^n$ is the unique polynomial $P \in \mathbb{k}[x]$ with $\text{deg} P \leqslant n$ such that $\forall i \in {1,...n}$, $P(i) = w_i$. Hence if Bob is honest, $P$ restricted to $1,...,10^6$ will take only values in $1,...,10$ - I don't understand why the first or 2nd line is true - that is my question $\endgroup$
    – user93353
    Commented Jul 3, 2023 at 7:21
  • $\begingroup$ @user93353 The first line is just the definition of interpolant (with indexing set $\{1,...,10^6\}$), taken from page 35 of the zk-STARK paper (eprint.iacr.org/2018/046) - I'm not sure if this particular notion of interpolant was explicitly defined in the lecture you linked, which may be the confusion. The second line follows immediately, since the claim Bob wishes to prove is exactly that all of his 10^6 interpolated points are in the set $\{1,...,10\}$ $\endgroup$
    – arcaynia
    Commented Jul 3, 2023 at 10:54
  • $\begingroup$ I hadn't seen the definition. However, there they have $P(x) = w(x)$ whereas you have $P(x) = w_x$. Anyway, in the context of the video, $P$ is the interpolant of $f$ - i.e. it means $f(x) = P(x)$ - from that, I still don't get why $P$ restricted to $1,...,10^6$ will take only values in $1,...,10$? $\endgroup$
    – user93353
    Commented Jul 3, 2023 at 11:07

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.