The AND Reduction

Here, we handle the prover's AND constraints. To check whether some fixed AND constraints hold over committed prover data $w$, we need to do a number of cryptographic steps. Technically, the job of the AND reduction is to reduce the satisfaction of the prover's AND constraints to certain further claims, pertaining to evaluations of the oblong-multilinearizations of the prover's constraint arrays. This is exactly the type of claim ingested by the shift reduction.

We explain our steps in the following pages.

• The Rijndael Field. Here, we explain the Rijndael field, a small, 8-bit field used in AES (for example). We also discuss how this field interacts with $\mathbb{F}_{2^{128}}$, our ambient field.
• The Univariate Skip. The univariate skip is an efficient protocol for zerochecking polynomials over tiny fields, originally due to Gruen [Gru24, § 5.1]. We use a variant of that idea, adapted to our 64-bit setting, that also incorporates ideas of Dao and Thaler [DT24a]. Here, we record the overall structure of our univariate skip variant, and prove its soundness.
• The Rijndael Zerocheck. This page is dedicated to our prover implementation of the univariate skip. Our prover works in the Rijndael field "where possible". The interplay between these small and large fields is subtle, and incorporates ideas from Dao and Thaler [DT24b] and Hu et al. [Hu+25].