Comparison Between XL and Gröbner Basis Algorithms

DOI10.1007/978-3-540-30539-2_24zbMath1094.94024OpenAlexW68643468MaRDI QIDQ5465822

Makoto Sugita, Jean-Charles Faugère, Gwénolé Ars, Mitsuru Kawazoe, Hiroshi Imai

Publication date: 12 August 2005

Published in: Advances in Cryptology - ASIACRYPT 2004 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-30539-2_24

zbMATH Keywords

Gröbner basisXL algorithmAlgebraic attacksMultivariate polynomial equationsSemi-regular SequencesSolving Systems

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Cryptography (94A60) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)

Related Items (23)

Boolean ring cryptographic equation solving ⋮ Evaluation of Solving Time for Multivariate Quadratic Equation System Using XL Algorithm Over Small Finite Fields on GPU ⋮ On the security of biquadratic \(C^\ast\) public-key cryptosystems and its generalizations ⋮ An algorithm for solving over-determined multivariate quadratic systems over finite fields ⋮ An estimator for the hardness of the MQ problem ⋮ Cryptanalysis of the TRMS Signature Scheme of PKC’05 ⋮ On the relation between the MXL family of algorithms and Gröbner basis algorithms ⋮ Worst-case subexponential attacks on PRGs of constant degree or constant locality ⋮ An improvement of algorithms to solve under-defined systems of multivariate quadratic equations ⋮ On the computation of rational solutions of underdetermined systems over a finite field ⋮ Revisiting the Security Proof of QUAD Stream Cipher: Some Corrections and Tighter Bounds ⋮ Square-Vinegar Signature Scheme ⋮ On the termination of the general XL algorithm and ordinary multinomials ⋮ Polynomial Equivalence Problems: Algorithmic and Theoretical Aspects ⋮ QUAD: A Practical Stream Cipher with Provable Security ⋮ Kipnis-Shamir Attack on HFE Revisited ⋮ On the Number of Linearly Independent Equations Generated by XL ⋮ Simplified pairing computation and security implications ⋮ QUAD: A multivariate stream cipher with provable security ⋮ Square, a New Multivariate Encryption Scheme ⋮ An algebraic attack on rank metric code-based cryptosystems ⋮ Breaking an Identity-Based Encryption Scheme Based on DHIES ⋮ Specific S-Box Criteria in Algebraic Attacks on Block Ciphers with Several Known Plaintexts

Uses Software

• FGb

This page was built for publication: Comparison Between XL and Gröbner Basis Algorithms