Paper 2023/619

Fast Enumeration Algorithm for Multivariate Polynomials over General Finite Fields

Hiroki Furue, The University of Tokyo
Tsuyoshi Takagi, The University of Tokyo

The enumeration of all outputs of a given multivariate polynomial is a fundamental mathematical problem and is incorporated in some algebraic attacks on multivariate public key cryptosystems. For a degree-$d$ polynomial in $n$ variables over the finite field with $q$ elements, solving the enumeration problem classically requires $O\left(\tbinom{n+d}{d} \cdot q^n\right)$ operations. At CHES 2010, Bouillaguet et al. proposed a fast enumeration algorithm over the binary field $\mathbb{F}_2$. Their proposed algorithm covers all the inputs of a given polynomial following the order of Gray codes and is completed by $O(d\cdot2^n)$ bit operations. However, to the best of our knowledge, a result achieving the equivalent efficiency in general finite fields is yet to be proposed. In this study, we propose a novel algorithm that enumerates all the outputs of a degree-$d$ polynomial in $n$ variables over $\mathbb{F}_q$ with a prime number $q$ by $O(d\cdot q^n)$ operations. The proposed algorithm is constructed by using a lexicographic order instead of Gray codes to cover all the inputs. This result can be seen as an extension of the result of Bouillaguet et al. to general finite fields and is almost optimal in terms of time complexity. We can naturally apply the proposed algorithm to the case where $q$ is a prime power. Notably, our enumeration algorithm differs from the algorithm by Bouillaguet et al. even in the case of $q=2$.

Available format(s)
Attacks and cryptanalysis
Publication info
multivariate polynomialfinite fieldsenumeration algorithmexhaustive searchMQ problemMPKC
Contact author(s)
furue-hiroki261 @ g ecc u-tokyo ac jp
takagi @ g ecc u-tokyo ac jp
2023-05-01: approved
2023-05-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Hiroki Furue and Tsuyoshi Takagi},
      title = {Fast Enumeration Algorithm for Multivariate Polynomials over General Finite Fields},
      howpublished = {Cryptology ePrint Archive, Paper 2023/619},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.