Polynomial Evaluation on Many Inputs with Bounded Hamming Weight over GF(2)

본문 미리보기

We propose a new polynomial evaluation algorithm to evaluate a degree-$d$ Boolean polynomial $f(x_n,\ldots,x_1)$ on all elements in some structured sets $S\subseteq \mathbb F_2^n$. This problem has been well-studied for $S=\mathbb F_2^n$ and there are efficient polynomial evaluation algorithms like standard Mobius transform, memory-efficient Mobius transform (EUROCRYPT 2021, TOMS 2024) and fast exhaustive search (CHES 2010, PQCrypt 2023) for the case $S=\mathbb F_2^n$. In addition, the standard