An algebraic approach to the rank support learning problem
From MaRDI portal
Publication:2118561
Abstract: Rank-metric code-based cryptography relies on the hardness of decoding a random linear code in the rank metric. The Rank Support Learning problem (RSL) is a variant where an attacker has access to N decoding instances whose errors have the same support and wants to solve one of them. This problem is for instance used in the Durandal signature scheme. In this paper, we propose an algebraic attack on RSL which clearly outperforms the previous attacks to solve this problem. We build upon Bardet et al., Asiacrypt 2020, where similar techniques are used to solve MinRank and RD. However, our analysis is simpler and overall our attack relies on very elementary assumptions compared to standard Gr{"o}bner bases attacks. In particular, our results show that key recovery attacks on Durandal are more efficient than was previously thought.
Recommendations
- Durandal: a rank metric based signature scheme
- An algebraic attack on rank metric code-based cryptosystems
- Cryptanalysis of the rank preserving signature
- Ranksign: an efficient signature algorithm based on the rank metric
- Improvements of algebraic attacks for solving the rank decoding and MinRank problems
Cites work
- A digital signature scheme based on random error-correcting codes
- An algebraic attack on rank metric code-based cryptosystems
- An efficient attack on all concrete KKS proposals
- Cryptanalysis of MinRank
- Durandal: a rank metric based signature scheme
- scientific article; zbMATH DE number 1186948 (Why is no real title available?)
- scientific article; zbMATH DE number 177612 (Why is no real title available?)
- Hybrid approach for solving multivariate systems over finite fields
- Identity-based encryption from codes with rank metric
- Improvements of algebraic attacks for solving the rank decoding and MinRank problems
- 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
- Progress in Cryptology – Mycrypt 2005
- Solving sparse linear equations over finite fields
- The computational complexity of some problems of linear algebra
- Two attacks on rank metric code-based schemes: RankSign and an IBE scheme
Cited in
(12)- An algebraic attack on rank metric code-based cryptosystems
- Durandal: a rank metric based signature scheme
- Statistical zero-knowledge and analysis of rank-metric zero-knowledge proofs of knowledge
- Compact post-quantum signatures from proofs of knowledge leveraging structure for the \textsf{PKP, SD} and \textsf{RSD} problems
- Revisiting algebraic attacks on MinRank and on the rank decoding problem
- Improving support-minors rank attacks: applications to G\textit{e}MSS and Rainbow
- LRPC codes with multiple syndromes: near ideal-size KEMs without ideals
- Analysis of the security of the PSSI problem and cryptanalysis of the Durandal signature scheme
- Cryptanalysis of Rank-Metric Schemes Based on Distorted Gabidulin Codes
- Injective rank metric trapdoor functions with homogeneous errors
- The blockwise rank syndrome learning problem and its applications to cryptography
- A minrank-based encryption scheme à la Alekhnovich-Regev
This page was built for publication: An algebraic approach to the rank support learning problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118561)
