The Rijndael Field

In this page, we lay some mathematical groundwork, necessary to explain our Rijndael zerocheck.

The Rijndael Field

The Rijndael field [FIPS197, § 4] is a small, 8-bit field used in AES, Grøstl and various other places. It's defined as the quotient ring

$K$ is isomorphic to $\mathbb{F}_{2^8}$. During the univariate skip, our goal will be to perform "as much work as possible" over $K$.

Tensor Basis

We now pick three elements $\rho_0, \rho_1, \rho_2$ of $K$ such that the elements of the tensor

yield an $\mathbb{F}_2$-basis of $K$.

The $K$-elements $\rho_0 \coloneqq X$, $\rho_1 \coloneqq X^2$, and $\rho_2 \coloneqq X^4$ satisfy this property. Indeed, taking all subproducts of $(X, X^2, X^4)$, we get the list $(1, X, X^2, \ldots , X^7)$, which is clearly linearly independent over $\mathbb{F}_2$. The actual tensor $\left( \widetilde{\texttt{eq}}(\rho, v) \right)_{v \in \mathcal{B}_3}$ contains not

but rather

on the other hand, these two lists differ from each other by an invertible $\mathbb{F}_2$-linear transformation from $\mathbb{F}_{2^8}^8 \to \mathbb{F}_{2^8}^8$, so the distinction doesn't affect linear independence.

Embedding

We moreover assume that we have a fixed field embedding from $\iota : K \to \mathbb{F}_{2^{128}}$. Since we have fixed $\mathbb{F}_2$-bases for both fields, $\iota$ can be represented in practice as an $128 \times 8$ $\mathbb{F}_2$-matrix. Embedding looks like taking a subset sum of that matrix's $8$ columns. In practice, it turns out to be more efficient to implement the entire transformation as a single lookup table. In this case, we precompute and store all 256 images in $\mathbb{F}_{2^{128}}$ of the various $K$-elements.

Mathematically, the embedding $\iota$ is not unique; it amounts to choosing a root of the Rijndael polynomial $X^8 + X^4 + X^3 + X + 1$ within $\mathbb{F}_{2^{128}}$. There are 8 choices.

We write $\sigma_0$, $\sigma_1$, and $\sigma_2$ for the images under $\iota$ of $\rho_0$, $\rho_1$ and $\rho_2$. We note that the elements $\left( \widetilde{\texttt{eq}}(\sigma, u) \right)_{u \in \mathcal{B}_3}$ are also linearly independent over $\mathbb{F}_2$. Indeed,

holds for each $u \in \mathcal{B}_3$, since $\iota$ is a field embedding (and "commutes" with the equality indicator). Moreover, $\iota$ takes $\mathbb{F}_2$-linearly independent lists to $\mathbb{F}_2$-linearly independent lists, since it's injective and $\mathbb{F}_2$-linear.

Deterministic Zerocheck

We now explain a zerocheck variant, adapting an idea of Dao and Thaler [DT24a]. We fix an $\ell$-variate $\mathbb{F}_2$-polynomial $t(X_0, \ldots , X_{\ell - 1})$, which is claimed to vanish identically on $\mathcal{B}_\ell$.

In the usual zerocheck, the verifier samples an $\ell$-dimensional fully random challenge $r_x \gets \mathbb{F}_{2^{128}}^\ell$; the parties then run a sumcheck on the claim

By a standard analysis, the soundness analysis of this maneuver is bounded from above by $\frac{\ell}{2^{128}}$.

Instead, we instruct the verifier to sample an $\ell - 3$-dimensional random challenge $\overline{r_x}$, and let

The first three components of $r_x$ are now "deterministic". The parties can now sumcheck

This variant is also sound. In fact, its soundness error is bounded from above by just $\frac{\ell - 3}{2^{128}}$. Indeed, if we write

for the "bit-packing" of $t(X_0, \ldots , X_{\ell - 1})$ over $\left( \widetilde{\texttt{eq}}(\sigma, v) \right)_{v \in \mathcal{B}_3}$, then

Since the $\mathbb{F}_{2^{128}}$-elements $\left( \widetilde{\texttt{eq}}(\sigma, v) \right)_{v \in \mathcal{B}_3}$ are linearly independent over $\mathbb{F}_2$ (see above), if $t(X_0, \ldots , X_{\ell - 1})$ is not identically zero over $\mathcal{B}_\ell$, then $\overline{t}(X_0, \ldots , X_{\ell - 4})$ is likewise not identically zero over $\mathcal{B}_{\ell - 3}$. Here, we use the fact that $t(X_0, \ldots , X_{\ell - 1})$'s restriction to $\mathcal{B}_\ell$ is $\mathbb{F}_2$-valued.

On the other hand, the right-hand sum above is exactly the evaluation of the multilinear extension of $\overline{t}(X_0, \ldots , X_{\ell - 4})$ at $\overline{r_x}$. Since we just argued that $\overline{t}(X_0, \ldots , X_{\ell - 4})$ is not identically zero over $\mathcal{B}_{\ell - 3}$, the usual soundness analysis of the zerocheck imples that, except with probability at most $\frac{\ell - 3}{2^{128}}$ over the verifier's choice of $\overline{r_x}$, the above sum is nonzero.

We will say more later about how the prover can actually exploit the structure of this $r_x$ during its univariate skip.