|Title||Operating 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|
|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 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.
|Keywords||sparse solver, Gröbner basis, XL ,MQ, asymptotic analysis, F4, F5 |