Paper 2026/197

Efficient Evaluation of Multivariate Polynomials over Structured Subsets of $\mathbb F_q^n$

Abstract

Efficient evaluation of a multivariate polynomial of degree $d$ over a finite space is a central primitive in algebraic cryptanalysis, particularly in exhaustive search attacks against multivariate public-key cryptosystems (MPKCs). For the Boolean space $\mathbb F_2^n$, Bouillaguet et al. introduced the fast exhaustive search (FES) algorithm at CHES 2010. This line of work was further developed by Dinur at EUROCRYPT 2021 and Bouillaguet at TOMS 2024. Extending beyond the Boolean setting, Furue and Takagi proposed an algorithm at PQCrypto 2023 that generalizes FES to the finite-field space $\mathbb F_q^n$, where $q$ is a prime number, achieving time complexity $\mathcal O\big(d\cdot q^n\big)$ with an initialization cost of $\binom{n+d}{d}^2$ and memory complexity $\mathcal{O}\big(\log(q\cdot n)\cdot n \cdot \binom{n+d}{d}\big)$. However, all these algorithms operate over the full space $\mathbb F_q^n$, which limits their applicability in many cryptanalytic scenarios where polynomial evaluation is required only over specific subsets of $\mathbb F_q^n$, such as those arising in the Syndrome Decoding Problem. Recently, Liu et al. proposed a memory-efficient algorithm for evaluating polynomials over the structured subset $P_{n_s}^{w_s} \times \cdots \times P_{n_1}^{w_1} \subseteq \mathbb F_2^n$, where $\sum_{i=1}^{s} n_i = n$ and $P_{n_i}^{w_i} \subseteq \mathbb F_2^{n_i}$ denotes the set of vectors of length $n_i$ with Hamming weight at most $w_i$. In this work, we extend the structured-subset evaluation paradigm from the Boolean setting to arbitrary finite fields $\mathbb F_q$. Building on the abstraction of evaluation rules and evaluation orders introduced by Liu et al., and combining it with higher-order derivative techniques over finite fields, we develop a unified theoretical framework for evaluating multivariate polynomials over the structured subset $S$ of $ \mathbb{F}_q^n$. We derive two methods for the initialization phase: a coefficient-based approach using the coefficients of the polynomial and a derivative-based approach exploiting its higher-order derivatives. The former achieves time complexity $\mathcal{O}\!\big(d \cdot \binom{2n+d}{d}\big)$ with memory requirement $\mathcal{O}\!\big(\log q \cdot \binom{n+d}{d} + \log q \cdot d^2\big)$, while the latter runs in time $\mathcal{O}\!\big(\binom{n+d}{d}^2\big)$ and requires $\mathcal{O}\!\big(\log q \cdot \binom{n+d}{d}\big)$ memory. Depending on the values of $n$ and $d$, the appropriate method is selected for initialization. After initialization, a degree-$d$ polynomial can be evaluated over a structured subset $S$ of $ \mathbb{F}_q^n$ with time complexity $\mathcal{O}\!\big(d \cdot |S|\big)$.