Paper 2023/619
Fast Enumeration Algorithm for Multivariate Polynomials over General Finite Fields
Abstract
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$.
Metadata
 Available format(s)
 Category
 Attacks and cryptanalysis
 Publication info
 Preprint.
 Keywords
 multivariate polynomialfinite fieldsenumeration algorithmexhaustive searchMQ problemMPKC
 Contact author(s)

furuehiroki261 @ g ecc utokyo ac jp
takagi @ g ecc utokyo ac jp  History
 20230501: approved
 20230501: received
 See all versions
 Short URL
 https://ia.cr/2023/619
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/619, 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{https://eprint.iacr.org/2023/619}}, url = {https://eprint.iacr.org/2023/619} }