The XL-Algorithm and a Conjecture from Commutative Algebra

DOI10.1007/978-3-540-30539-2_23MaRDI QIDQ5465821zbMATH OpenOpenAlexFDO

Authors Claus Diem

Publication date 12 August 2005

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

zbMATH Keywords

algebraic attacksCryptanalysisextended linearizationFröberg's Conjectureoverdetermined systems of polynomial equations

Mathematics Subject Classification ID

Hilbert-Samuel and Hilbert-Kunz functions; Poincaré series (13D40) Symbolic computation and algebraic computation (68W30) Cryptography (94A60)

Recommendations

• scientific article; zbMATH DE number 1962148
• Algorithms for commutative algebras over the rational numbers
• X-maximal congruences and relevant sets for algebras
• scientific article; zbMATH DE number 2051167
• Computational complexity of some problems involving congruences on algebras
• scientific article; zbMATH DE number 1515218
• scientific article; zbMATH DE number 2206382
• On the Computational Complexity of Algebra on Lattices
• Some Algorithmic Problems for Lie Algebras
• Algorithmic problems in associative algebras

Cited in

(20)

• Probabilistic analysis on Macaulay matrices over finite fields and complexity of constructing Gröbner bases
• On the termination of the general XL algorithm and ordinary multinomials
• From 5-pass \(\mathcal {MQ}\)-based identification to \(\mathcal {MQ}\)-based signatures
• Loiss: A Byte-Oriented Stream Cipher
• A geometric view of cryptographic equation solving
• Secure PRNGs from Specialized Polynomial Maps over Any $\mathbb{F}_{q}$
• QUAD: A Practical Stream Cipher with Provable Security
• Kipnis-Shamir Attack on HFE Revisited
• On the Number of Linearly Independent Equations Generated by XL
• Geometric ideas for cryptographic equation solving in even characteristic
• On the relation between the MXL family of algorithms and Gröbner basis algorithms
• On the branch numbers of the tree diagrams in the Inoue algorithm
• Analysis of Multivariate Hash Functions
• Comparison Between XL and Gröbner Basis Algorithms
• An algorithm for solving over-determined multivariate quadratic systems over finite fields
• FUTURE: a lightweight block cipher using an optimal diffusion matrix
• Worst-case subexponential attacks on PRGs of constant degree or constant locality
• Polynomial XL: a variant of the XL algorithm using Macaulay matrices over polynomial rings
• SoK: how (not) to design and implement post-quantum cryptography
• Boolean ring cryptographic equation solving

This page was built for publication: The XL-Algorithm and a Conjecture from Commutative Algebra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5465821)