Motivational Remarks

Recall what our goal is: we start with a huge-field polynomial $t(X_0, \ldots , X_{\ell - 1})$ over $\mathcal{T}_\tau$; we assume that we have committed to it. Our goal is to evaluate not $t$, but rather its $\kappa$-fold refinement $t'(X_0, \ldots , X_{\ell + \kappa - 1})$, a polynomial over $\mathcal{T}_{\tau - \kappa}$. Here, $\kappa \in \{0, \ldots , \tau\}$ is a parameter.

Thus, we fix an evaluation point $(r_0, \ldots, r_{\ell + \kappa - 1}) \in \mathcal{T}_\tau^{\ell + \kappa}$. Our goal is to learn $t'(r_0, \ldots, r_{\ell + \kappa - 1})$. More specifically, our goal is to reduce the problem of learning $t'(r_0, \ldots, r_{\ell + \kappa - 1})$ to that of learning $t(r'_0, \ldots , r'_{\ell - 1})$, for some further point $(r'_0, \ldots , r'_{\ell - 1}) \in \mathcal{T}_\tau^\ell$. In words: we want to reduce the problem of evaluating a refinement of $t$ to the problem of evaluating $t$ itself.

Why This is Hard

Given the ability to evaluate $t(X_0, \ldots , X_{\ell - 1})$, how do we bootstrap that into the ability to evaluate its refinement $t'(X_0, \ldots , X_{\ell + \kappa - 1})$? This seems like a tricky problem, because the latter task involves dealing "individually" with substrings of $t$'s coefficients, in a way that goes beyond what we're allowed to do when we merely evaluate $t$ in a blackbox way. Indeed, evaluating $t(X_0, \ldots , X_{\ell - 1})$ amounts to dotting $t$'s Lagrange coefficient vector $\left( t(v) \right)_{v \in \mathcal{B}_\ell}$ with some tensor $\bigotimes_{i = 0}^{\ell - 1} (1 - r'_i, r'_i)$, a "coarse" operation. What we want to do is dot the refined vector $\left( t'(v) \right)_{v \in \mathcal{B}_{\ell + \kappa}}$ with a longer tensor $\bigotimes_{i = 0}^{\ell + \kappa - 1} (1 - r_i, r_i)$. How do we gain this "refined" sort of access, given only evaluation access to $t$ itself?

As an exercise, you can think about trying to "lift" $t$-evaluation to $t'$-evaluation. The simplest possibility would be if the verifier could, by evaluating $t$ at just a single point—and doing some amount of local work, let's say—thereby evaluate $t'$. To learn its desired thing $t'(r_0, \ldots, r_{\ell + \kappa - 1})$, where should the verifier evaluate $t$? Maybe at the truncated point $(r_\kappa, \ldots , r_{\ell + \kappa - 1})$—would this information, on its own, be enough? As we argue in [DP24], the answer is no; and nor can any single evaluation of $t$ be enough on its own (i.e., without interaction with the prover, and so on).

In this note, we show how $2^\kappa$ evaluations of $t$ at different points—specifically, at a componentwise Galois orbit of $(r_\kappa, \ldots , r_{\ell + \kappa - 1})$—are enough to learn $t'(r_0, \ldots, r_{\ell + \kappa - 1})$. The approach we pursue—namely, ring-switching—gives an alternative to the Galois-theoretic one, which turns out to be more efficient than that one is.

Indeed, while evaluating $t$ at $(r_\kappa, \ldots , r_{\ell + \kappa - 1})$ alone is indeed not enough, it becomes enough if we operate over a larger ring that contains $\mathcal{T}_\tau$ as a subring. In fact, that larger ring is nothing other than the tensor algebra.

Sum Claims

Actually, for technical reasons, we are going to process our evaluation claim $s \stackrel{?}= t'(r_0, \ldots, r_{\ell + \kappa - 1})$ in two steps. First, we will reduce our initial evaluation claim to a sum claim about the underlying polynomial $t(X_0, \ldots , X_{\ell - 1})$. By definition, a sum claim amounts to a claim of the form

where $A(X_0, \ldots, X_{\ell - 1})$ is some other $\ell$-variate multilinear over $\mathcal{T}_\tau$ (in particular, it's a transparent polynomial that the verifier can simply evaluate).

This kind of reduction amounts to progress, since we can always use the sumcheck protocol on claims of that latter sort.

Thus, for now, it's enough to reduce our evaluation claim on $t'$ to a sum claim on $t$. This is actually what we will set out to do in ring-switching.