Derivative-Based Evaluation of Multivariate Polynomials over Product Hamming Balls

본문 미리보기

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.