Paper 2026/197

Derivative-Based Evaluation of Multivariate Polynomials over Product Hamming Balls

Abstract

Efficient evaluation of multivariate polynomials over finite spaces is an important problem in algebraic cryptanalysis, particularly in exhaustive-search attacks on multivariate public-key cryptosystems. Existing fast exhaustive-search techniques, including those of Bouillaguet et al. (CHES 2010), Dinur (EUROCRYPT 2021), and Furue and Takagi (PQCrypto 2023), mainly target the complete space $\mathbb F_q^n$, whereas many cryptanalytic applications require evaluation only over structured subsets. Recently, Liu et al. proposed a memory-efficient algorithm for evaluating degree-$d$ polynomials over product Hamming balls \[ B(\textbf{\textit{n}},\textbf{\textit{w}})=B(n_s,w_s)\times\cdots\times B(n_1,w_1)\subseteq\mathbb F_2^n, \] where $\sum_{i=1}^{s}n_i=n$ and $B(n_i,w_i) \subseteq \mathbb F_2^{n_i} $ denotes the set of vectors of length $n_i$ and having at most $w_i$ nonzero coordinates. In this work, we extend this structured-subset paradigm by developing a unified derivative-based framework, comprising initialization and evaluation phases, first over prime fields $\mathbb F_q$ and subsequently over arbitrary finite fields $\mathbb F_{q^\rho}$ through basis expansion. We derive two initialization methods with time complexities $\mathcal O(nrM)$ and $\mathcal O(rM^2)$, where $M\leq\min\{\binom{n+d}{d},q^n\}$ and $r=\min\{d,q-1\}$. After initialization, evaluation over $B(\textbf{\textit{n}},\textbf{\textit{w}})$ requires $\mathcal O(d|B(\textbf{\textit{n}},\textbf{\textit{w}})|)$ arithmetic operations, apart from a linear setup cost. The corresponding overall memory bounds are $\mathcal O((M+r^2)\log q+n\log(nq))$ and $\mathcal O(((d+1)M+r^2)\log q+n\log(nq))$, respectively, and are independent of the number of evaluated points.