Operating Degrees for XL vs. F4/F5 for Generic MQ with Number of Equations Linear in That of Variables

Abstract. 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 overdetermined MQ 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 com-munity, 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 work-shop in 2008, Johannes Buchmann listed several key research questions to all post-quantum cryptographers present. One problem in MQ-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