Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology

DOI10.1145/1837934.1837984zbMath1321.68529OpenAlexW1986124084MaRDI QIDQ2946547

Jean-Charles Faugère, Pierre-Jean Spaenlehauer, Mohab Safey El Din

Publication date: 17 September 2015

Published in: Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1837934.1837984

zbMATH Keywords

determinantal idealsGröbner basesmultivariate cryptographydegree of regularitypolynomial systems solvinggeneralized nonlinear eigenvalue problemmulti-homogeneous ideals

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Cryptography (94A60) Eigenvalues, singular values, and eigenvectors (15A18)

Related Items (26)

Efficient key recovery for all HFE signature variants ⋮ A Rank Attack Against Extension Field Cancellation ⋮ (Short paper) Simple matrix signature scheme ⋮ The Complexity of MinRank ⋮ Cryptanalysis of HFE, multi-HFE and variants for odd and even characteristic ⋮ Practical post-quantum signature schemes from isomorphism problems of trilinear forms ⋮ Solving rank-constrained semidefinite programs in exact arithmetic ⋮ On the complexity of the generalized MinRank problem ⋮ First fall degree and Weil descent ⋮ Refined F5 Algorithms for Ideals of Minors of Square Matrices ⋮ Improving support-minors rank attacks: applications to G\textit{e}MSS and Rainbow ⋮ Improvement of algebraic attacks for solving superdetermined MinRank instances ⋮ Real root finding for determinants of linear matrices ⋮ MinRank in the head. Short signatures from zero-knowledge proofs ⋮ MR-DSS -- smaller MinRank-based (ring-)signatures ⋮ Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree \((1,1)\): algorithms and complexity ⋮ Algebraic relation of three MinRank algebraic modelings ⋮ Improvements of algebraic attacks for solving the rank decoding and MinRank problems ⋮ Sparse FGLM algorithms ⋮ Solving multivariate polynomial systems and an invariant from commutative algebra ⋮ Homotopy techniques for solving sparse column support determinantal polynomial systems ⋮ The product of matrix subspaces ⋮ An algebraic attack on rank metric code-based cryptosystems ⋮ Improved cryptanalysis of UOV and Rainbow ⋮ Multivariate public key cryptosystem from Sidon spaces ⋮ Practical complexities of probabilistic algorithms for solving Boolean polynomial systems

Uses Software

• FGb
• DIFFALG
• AIDA

Cites Work

• Differential algebra for derivations with nontrivial commutation rules
• Generating differential invariants
• Projective-type differential invariants and geometric curve evolutions of KdV-type in flat homogeneous manifolds
• Smooth and algebraic invariants of a group action: Local and global constructions
• Differential invariants of a Lie group action: syzygies on a generating set
• Invariants différentiels d'un pseudogroupe de Lie. I
• Invariants différentiels d'un pseudogroupe de Lie. II
• Higher order contact of submanifolds of homogeneous spaces
• Moving coframes. II: Regularization and theoretical foundations
• Rational invariants of a group action. Construction and rewriting
• Differential invariants of conformal and projective surfaces
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology