## 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 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.

Original language | English |
---|---|

Title of host publication | Number Theory and Cryptography |

Subtitle of host publication | Papers in Honor of Johannes Buchmann on the Ocasion of His 60th Birthday |

Editors | Marc Fischlin, Stefan Katzenbeisser |

Pages | 19-33 |

Number of pages | 15 |

DOIs | |

State | Published - 2013 |

Externally published | Yes |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 8260 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

## Keywords

- Asymptotic analysis
- F, F
- Gröbner basis
- MQ
- Sparse solver
- XL

## Fingerprint

Dive into the research topics of 'Operating degrees for XL vs. F_{4}/F

_{5}for GenericMQ with number of equations linear in that of variables'. Together they form a unique fingerprint.