1970-01-01

(2026-02) Efficient Polynomial Evaluation on Structured Space over Finite Fields

• [[Vaibhav Dixit]]
• [[Santanu Sarkar]]
• [[Fukang Liu]]
• [[Willi Meier]]

2026-02-06

• #cryptography
• #paper

Abstract

Efficient evaluation of multivariate polynomials over finite spaces 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)$ 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 structured spaces $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-space 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 structured spaces $S \subseteq \mathbb F_q^n$. After an initialization phase with cost $\mathcal{O} \big(\binom{n+d}{d}^2 \big)$, our method evaluates a degree-$d$ polynomial over $S$ using $\mathcal O\big(d \cdot |S|\big)$ operations and requires $\mathcal O\big(\log(q)\cdot \binom{n+d}{d}\big)$ memory.