Operating degrees for XL vs. F₄/F₅ for GenericMQ with number of equations linear in that of variables

We discuss the complexity of MQ, or solving multivariate systems of m equations in n variables over the finite field Fq of q elements. MQ is an important hard problem in cryptography. In particular, the complexity to solve overdeterminedMQ 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 inMQ-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: 1. 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. 2. 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.