On the Gerbicz error check (REMATCH)

This discusses my paper An Efficient Modular Proof Scheme.

We left off (one year ago, no less) with my observation that the Gerbicz error check can be generalized to arbitrary numbers. But the utility of this can be inordinately increased by considering a more difficult problem: We’ve convinced ourselves that $a^b=c$. Can we convince someone else (who thinks that we did the computation wrong, or even thinks that we are actively trying to deceive them) that indeed $a^b=c$?

I at the time somehow assumed, overconfidently yet correctly, that the method I described can lead to such a proof scheme. Let’s take a step back and recall the Pietrzak VDF that Pavel Atnashev uses, when $b=2^n$:

Pietrzak VDF-turned-proof-scheme (Atnashev 2020). A prover wants to convince to a verifier that $a^{2^n}=b$. To do so, the prover tells the verifier $\mu=a^{2^{n/2}}$. Then, the verifier selects $Q$, and askes the prover to convince them that $(a\mu^Q)^{2^{n/2}}=(\mu b^Q)$. (This assumes $n$ is even. We can parity-adjust if $n$ is odd.)

This seemingly incurs much cost for the prover. But like in Gerbicz, if we keep the checkpoints $a^{i2^k}$, then $\alpha$ and $\beta$ in the final $\alpha^{2^k}=\beta$ that the prover needs to convince the verifier can be directly multiplied together given all the $Q$ from the verifier, without recomputing all the exponents. Then the prover just gives the verifier this computed $\alpha$ and $\beta$, and the verifier completes the calculation.

The correctness of this arises from how the verifier selects $Q$, so if some prover can consistently trick the verifier to accept a false solution a whole lot of cryptographic assumptions are broken.

This is pretty tricky to generalize. Let’s again consider the process (from last year):

$$x^{N}\leftarrow x^{\lfloor\frac{N}{2}\rfloor}\leftarrow x^{\lfloor\frac{N}{4}\rfloor}\leftarrow\dots\leftarrow x^{\lfloor\frac{N}{2^l}\rfloor}\leftarrow\dots$$

Defining $u_i=a^{\lfloor\frac{b}{2^i}\rfloor}$ the relation $u_i\leftarrow u_{i+j}$ satisfies $u_i=u_{i+j}^{2^j}a^{\left\lfloor\frac b{2^i}\right\rfloor\bmod 2^j}$.

Left-to-right modular exponentiation proof scheme. Consider the claim that the computation $u_i\leftarrow u_{i+j}$ is correct. The prover can show this by selecting some $k<j$ and showing that both steps $u_i\leftarrow u_{i+k}$ and $u_{i+k}\larr u_{i+j}$ are correct. If $k=j-k$, their form $u_i=u_{i+j}^{2^j}a^{\left\lfloor\frac b{2^i}\right\rfloor\bmod 2^j}$ possesses the same exponent $2^k$, and thus can be merged.

If $j$ is odd, the prover and the verifier can agree to advance to $u_{i+j-1}$, with the verifier calculating $u^\prime_{i+j-1}$ based on the given $u_{i+j}$ on their side as well. Thus we can decompose the proof subject, $0\larr L$, into a lot of much shorter proof subjects of equal length that together are enough to prove $0\larr L$. As they are equally long, we can gather $\prod u^{2^j}$ into $\left(\prod u\right)^{2^j}$, allowing for fast verification.

There are a few remaining things I have yet to talk about, like soundness. On this topic, my presentation slides for the paper might be a better exposition.