On the complexity of the Rank Syndrome Decoding problem
Authors:
Preprint
Abstract
In this paper we propose two new generic attacks on the Rank Syndrome Decoding (RSD) problem Let $C$ be a random $[n,k]$ rank code over $GF(q^m)$ and let $y=x+e$ be a received word such that $x \in C$ and the $Rank(e)=r$. The first attack is combinatorial and permits to recover an error $e$ of rank weight $r$ in $min(O((n-k)^3m^3q^{r\lfloor\frac{km}{n}\rfloor}, O((n-k)^3m^3q^{(r-1)\lfloor\frac{(k+1)m}{n}\rfloor}))$ operations on $GF(q)$. This attack dramatically improves on previous attack by introducing the length $n$ of the code in the exponent of the complexity, which was not the case in previous generic attacks. which can be considered The second attack is based on a algebraic attacks: based on the theory of $q$-polynomials introduced by Ore we propose a new algebraic setting for the RSD problem that permits to consider equations and unknowns in the extension field $GF(q^m)$ rather than in $GF(q)$ as it is usually the case. We consider two approaches to solve the problem in this new setting. Linearization technics show that if $n \ge (k+1)(r+1)-1$ the RSD problem can be solved in polynomial time, more generally we prove that if $\lceil \frac{(r+1)(k+1)-(n+1)}{r} \rceil \le k$, the problem can be solved with an average complexity $O(r^3k^3q^{r\lceil \frac{(r+1)(k+1)-(n+1)}{r} \rceil})$. We also consider solving with \grob bases for which which we discuss theoretical complexity, we also consider consider hybrid solving with \grob bases on practical parameters. As an example of application we use our new attacks on all proposed recent cryptosystems which reparation the GPT cryptosystem, we break all examples of published proposed parameters, some parameters are broken in less than 1 s in certain cases.
Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Decoding Random Binary Linear Codes in 2 n/20: How 1 + 1 = 0 Improves Information Set Decoding2012
- Full Cryptanalysis of the Chen Identification Protocol2011
- Designing a Rank Metric Based McEliece CryptosystemLecture Notes in Computer Science, 2010
- Security Bounds for the Design of Code-Based Cryptosystems2009
- Structural Attacks for Public Key Cryptosystems based on Gabidulin CodesJournal of Cryptology, 2007
- A New Public-Key Cryptosystem Based on the Problem of Reconstructing p–PolynomialsLecture Notes in Computer Science, 2006
- Extending Gibson’s Attacks on the GPT Cryptosystem2006
- Ideals over a Non-Commutative Ring and their Application in Cryptology2001
- The Magma Algebra System I: The User LanguageJournal of Symbolic Computation, 1997
- The cryptographic security of the syndrome decoding problem for rank distance codes1996