Multilinear Polynomials

For our purposes here, we work over the field $\mathbb{F}_2$. We can now moreover write $\mathbb{F}_2[X_0, \ldots , X_{\ell - 1}]$ for the ring of multivariate polynomials over $\mathbb{F}_2$ in $\ell$ indeterminates. A polynomial $t(X_0, \ldots , X_{\ell - 1}) \in \mathbb{F}_2[X_0, \ldots, X_{\ell - 1}]$ is multilinear if each indeterminate appears in it with individual degree at most 1. We write $\mathbb{F}_2[X_0, \ldots, X_{\ell - 1}]^{\preceq 1}$ for the set of multilinears. This thing is $2^\ell$-dimensional over $\mathbb{F}_2$ (a basis is given by the multilinear monomials $1, X_0, X_1, X_0 \cdot X_1, X_2, \ldots , X_0 \cdot \cdots \cdot X_{\ell - 1}$).

Multilinear polynomials and lists of field elements are basically the same thing, as we argue now. We will write $\mathcal{B}_\ell \coloneqq \{0, 1\}^\ell$ for the $\ell$-dimensional discrete unit cube.

The Equality Indicator Polynomial

For each fixed $\ell \geq 0$, the $2 \cdot \ell$-variate equality indicator polynomial $\widetilde{\texttt{eq}}(X_0, \ldots , X_{\ell - 1}, Y_0, \ldots , Y_{\ell - 1})$ is defined to be:

This polynomial is multilinear. Moreover, its restriction to the cube $\mathcal{B}_\ell \times \mathcal{B}_\ell$ yields the equality indicator function, the function that, on each pair of bitstrings $u$ and $u^*$, equals 1 if $u = u^*$ and 0 otherwise.

Multilinear Extensions

Given some multilinear $t(X_0, \ldots , X_{\ell - 1}) \in \mathbb{F}_2[X_0, \ldots, X_{\ell - 1}]^{\preceq 1}$, the evaluation map sends $t(X_0, \ldots , X_{\ell - 1})$ to its evaluations on the cube; that is,

The problem of reversing this mapping is called "multilinear extension". We're going from the list $\left( t_u \right)_{u \in \mathcal{B}_\ell}$ of prescribed values back to the multilinear $t(X_0, \ldots , X_{\ell - 1})$ takes those values.

We argue that $\text{eval}$ is a bijection (multilinear extensions exist and are unique). For dimension-count reasons, it suffices to argue that it's surjective (multilinear extensions exist). Indeed, it's linear over $\mathbb{F}_2$, and both the domain and the codomain are $2^\ell$-dimensional. If it's surjective, it must also be injective (multilinear extensions are unique).

We fix a list $\left( t_u \right)_{u \in \mathcal{B}_\ell}$ of prescribed values. We're going to solve this problem using multilinear Lagrange interpolation. Indeed, the polynomial

gives us what we want. Why? First off, $t(X_0, \ldots , X_{\ell - 1})$ is definitely multilinear, since each of the partial specializations $\widetilde{\texttt{eq}}(u_0, \ldots , u_{\ell - 1}, X_0, \ldots , X_{\ell - 1})$ is. Moreover, let's pick an arbitrary $u^* \in \mathcal{B}_\ell$. Since $\widetilde{\texttt{eq}}(u_0, \ldots , u_{\ell - 1}, u^*_0, \ldots , u^*_{\ell - 1})$ equals 1 if and only if $u = u^*$, the sum $t(u^*)$ winds up with just one nonzero summand, $t_{u^*} \cdot \widetilde{\texttt{eq}}(u^*, u^*) = t_{u^*}$. In other words, $t(u^*) = t_{u^*}$ holds for each $u^* \in \mathcal{B}_\ell$, which is what we wanted to show.

It's worth pointing out that you can show directly that $\text{eval}$ is injective, without relying on dimension-counting or Lagrange interpolation. This proof is fairly interesting too; it's carried out in Thaler [Tha23, Fact 3.5.].

Succinctness

There is one final fact that makes things work. The equality indicator polynomial $\widetilde{\texttt{eq}}(X_0, \ldots , X_{\ell - 1}, Y_0, \ldots , Y_{\ell - 1})$ is succinct, meaning that for each pair of points $r$ and $r'$ in $\mathbb{F}_{2^{128}}^\ell$, the evaluation $\widetilde{\texttt{eq}}(r, r')$ can be computed in $O(\ell)$ time.

To see why this is true, just look at the defining equation of $\widetilde{\texttt{eq}}$. It's a product, with $\ell$ terms; moreover, each term in the product can be computed using just a few operations. Actually, in characteristic 2, things get even nicer: we get the simplification

since $X_i \cdot Y_i + X_i \cdot Y_i = 0$ cancels from each term in the product. Thus, we can get away with just $\ell - 1$ total multiplications.