Revisiting algebraic attacks on MinRank and on the rank decoding problem
From MaRDI portal
Abstract: The Rank Decoding problem (RD) is at the core of rank-based cryptography. This problem can also be seen as a structured version of MinRank, which is ubiquitous in multivariate cryptography. Recently, cite{BBBGNRT20,BBCGPSTV20} proposed attacks based on two new algebraic modelings, namely the MaxMinors modeling which is specific to RD and the Support-Minors modeling which applies to MinRank in general. Both improved significantly the complexity of algebraic attacks on these two problems. In the case of RD and contrarily to what was believed up to now, these new attacks were shown to be able to outperform combinatorial attacks and this even for very small field sizes. However, we prove here that the analysis performed in cite{BBCGPSTV20} for one of these attacks which consists in mixing the MaxMinors modeling with the Support-Minors modeling to solve RD is too optimistic and leads to underestimate the overall complexity. This is done by exhibiting linear dependencies between these equations and by considering an version of these modelings which turns out to be instrumental for getting a better understanding of both systems. Moreover, by working over rather than over , we are able to drastically reduce the number of variables in the system and we (i) still keep enough algebraic equations to be able to solve the system, (ii) are able to analyze rigorously the complexity of our approach. This new approach may improve the older MaxMinors approach on RD from cite{BBBGNRT20,BBCGPSTV20} for certain parameters. We also introduce a new hybrid approach on the Support-Minors system whose impact is much more general since it applies to any MinRank problem. This technique improves significantly the complexity of the Support-Minors approach for small to moderate field sizes.
Recommendations
- Improvement of algebraic attacks for solving superdetermined MinRank instances
- An algebraic attack on rank metric code-based cryptosystems
- Improving support-minors rank attacks: applications to G\textit{e}MSS and Rainbow
- Cryptanalysis of MinRank
- On the Hardness of the Decoding and the Minimum Distance Problems for Rank Codes
- Rank Minimization Over Finite Fields: Fundamental Limits and Coding-Theoretic Interpretations
- Progress in Cryptology – Mycrypt 2005
- Combinatorial Rank Attacks Against the Rectangular Simple Matrix Encryption Scheme
- scientific article; zbMATH DE number 2081078
Cites work
- scientific article; zbMATH DE number 1583768 (Why is no real title available?)
- scientific article; zbMATH DE number 1186948 (Why is no real title available?)
- scientific article; zbMATH DE number 177612 (Why is no real title available?)
- scientific article; zbMATH DE number 2081078 (Why is no real title available?)
- scientific article; zbMATH DE number 1759341 (Why is no real title available?)
- scientific article; zbMATH DE number 1418284 (Why is no real title available?)
- A new identification scheme based on syndrome decoding
- An algebraic approach to the rank support learning problem
- An algebraic attack on rank metric code-based cryptosystems
- Asymptotic behaviour of codes in rank metric over finite fields
- Breaking rainbow takes a weekend on a laptop
- Cryptanalysis of MinRank
- Design Principles for HFEv- Based Multivariate Signature Schemes
- Determinantal rings
- Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes
- Durandal: a rank metric based signature scheme
- Efficient key recovery for all HFE signature variants
- Enhancing Code Based Zero-Knowledge Proofs Using Rank Metric
- Full cryptanalysis of the Chen identification protocol
- Ideals, Varieties, and Algorithms
- Identity-based encryption from codes with rank metric
- Improved cryptanalysis of UOV and Rainbow
- Improvements of algebraic attacks for solving the rank decoding and MinRank problems
- Improving support-minors rank attacks: applications to G\textit{e}MSS and Rainbow
- Key recovery attack for ZHFE
- LRPC codes with multiple syndromes: near ideal-size KEMs without ideals
- MR-DSS -- smaller MinRank-based (ring-)signatures
- New Results for Rank-Based Cryptography
- New technique for decoding codes in the rank metric and its cryptography applications
- On the Complexity of the Rank Syndrome Decoding Problem
- On the Hardness of the Decoding and the Minimum Distance Problems for Rank Codes
- On the complexity of ``Superdetermined minrank instances
- On the edge-independence number and edge-covering number for regular graphs
- Progress in Cryptology – Mycrypt 2005
- The computational complexity of some problems of linear algebra
- Theory of codes with maximum rank distance
- Two attacks on rank metric code-based schemes: RankSign and an IBE scheme
Cited in
(9)- Dual support decomposition in the head: shorter signatures from Rank SD and MinRank
- MinRank in the head. Short signatures from zero-knowledge proofs
- Improvements of algebraic attacks for solving the rank decoding and MinRank problems
- Statistical zero-knowledge and analysis of rank-metric zero-knowledge proofs of knowledge
- On the effect of projection on rank attacks in multivariate cryptography
- Blockwise rank decoding problem and LRPC codes: cryptosystems with smaller sizes
- A new approach based on quadratic forms to attack the McEliece cryptosystem
- The blockwise rank syndrome learning problem and its applications to cryptography
- Solving systems of algebraic equations over finite commutative rings and applications
This page was built for publication: Revisiting algebraic attacks on MinRank and on the rank decoding problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6063136)
