Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleOperating degrees for XL vs. $F_4/F_5$ for generic $mathcalMQ$ with number of equations linear in that of variables.
Author(s) Chen-Mou Cheng, Bo-Yin Yang, Jenny Yuan-Chun Yeh
TypeBook, Chapter in Book, Conference Proceeding
AbstractWe discuss the complexity of Q, or solving multivariate systems of m equations in n variables over the finite field 𝔽q of q elements. Q is an important hard problem in cryptography. In particular, the complexity to solve overdetermined Q systems with randomly chosen coefficients when m = cn is related to the provable security of a number of cryptosystems.

In this context there are two basic approaches. One is to use XL (“eXtended Linearization”) with the solving step tailored to sparse linear algebra; the other is of the many variations of Jean-Charles Faugère’s F4/F5 algorithms.

Although F4/F5 has been the de facto standard in the cryptographic community, it was proposed (Yang-Chen, 2004) that XL with Sparse Solver may be superior in some cases, particularly the generic overdetermined case with m/n = c + o(1).

At the Steering Committee Meeting of the Post-Quantum Cryptography workshop in 2008, Johannes Buchmann listed several key research questions to all post-quantum cryptographers present. One problem in Q -based cryptography, he noted, is “if the difference between the operating degrees of XL(-with-Sparse-Solver) and F4/F5 approaches can be accurately bounded for random systems.”

We answer in the affirmative when m/n = c + o(1), using Saddle Point analysis:


For instances with randomly drawn coefficients, the degrees of operation of XL and F4/F5 has the most pronounced differential in the large-field, “barely overdetermined” (m − n = c) cases, where the discrepancy is ∝n‾√.


In most other types of random systems with m/n = c + o(1), the expected difference in the operating degrees of XL and F4/F5 is constant which can be evaluated mathematically via asymptotic analysis.

Our conclusions are partially backed up using tests with Maple, MAGMA, and an XL implementation featuring Block Wiedemann as the sparse-matrix solver.
Keywordssparse solver, Gröbner basis, XL ,MQ, asymptotic analysis, F4, F5
URL http://link.springer.com/chapter/10.1007%2F978-3-642-42001-6_3
PublisherBerlin: Springer
Translation No
Refereed No