Details:
Title  Operating degrees for XL vs. $F_4/F_5$ for generic $mathcalMQ$ with number of equations linear in that of variables.  Author(s)  ChenMou Cheng, BoYin Yang, Jenny YuanChun Yeh  Type  Book, Chapter in Book, Conference Proceeding  Abstract  We 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 JeanCharles Faugère’s F4/F5 algorithms.
Although F4/F5 has been the de facto standard in the cryptographic community, it was proposed (YangChen, 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 PostQuantum Cryptography workshop in 2008, Johannes Buchmann listed several key research questions to all postquantum cryptographers present. One problem in Q based cryptography, he noted, is “if the difference between the operating degrees of XL(withSparseSolver) 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 largefield, “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 sparsematrix solver.  Keywords  sparse solver, Gröbner basis, XL ,MQ, asymptotic analysis, F4, F5  ISBN  9783642420009/pbk 
URL 
http://link.springer.com/chapter/10.1007%2F9783642420016_3 
Language  English  Pages  1933  Publisher  Berlin: Springer  Year  2013  Edition  0  Translation 
No  Refereed 
No 
