On the Complexity of the Rank Syndrome Decoding Problem

DOI10.1109/TIT.2015.2511786MaRDI QIDQ2977019zbMATH OpenOpenAlexFDO

Authors Olivier Ruatta, Julien Schrek, Philippe Gaborit

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.1026

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Decoding (94B35)

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 $xinC$ 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{)}^3{m}^3{q}^{rlfloorfrackmnfloor},O((n-k{)}^3{m}^3{q}^{(r-1)lfloorfrac(k+1)mnfloor}))$ 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 $nge(k+1)(r+1)-1$ the RSD problem can be solved in polynomial time, more generally we prove that if $lceilfrac(r+1)(k+1)-(n+1)rceillek$, the problem can be solved with an average complexity $O(r^3{k}^3{q}^{rlceilfrac(r+1)(k+1)-(n+1)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.

Cited in

(44)

• Polynomial-time key recovery attack on the Faure-Loidreau scheme based on Gabidulin codes
• Improved cryptanalysis of rank metric schemes based on Gabidulin codes
• Extension of Overbeck's attack for Gabidulin-based cryptosystems
• An algebraic attack on rank metric code-based cryptosystems
• A gapless code-based hash proof system based on RQC and its applications
• Decoding supercodes of Gabidulin codes and applications to cryptanalysis
• An algebraic approach to the rank support learning problem
• Efficient key recovery for all HFE signature variants
• New rank codes based encryption scheme using partial circulant matrices
• 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
• A unique ranking of multilevel sequences and its application to source coding (Corresp.)
• Information security in a random network coding network
• A novel Niederreiter-like cryptosystem based on the \((u|u + \upsilon)\)-construction codes
• Randomized decoding of Gabidulin codes beyond the unique decoding radius
• A rank attack against extension field cancellation
• A practical group signature scheme based on rank metric
• Rank-metric codes and their applications
• 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
• Code-Based Signature Schemes from Identification Protocols in the Rank Metric
• Cryptanalysis and repair of a Gabidulin code based cryptosystem from ACISP 2018
• McEliece-type encryption based on Gabidulin codes with no hidden structure
• MinRank in the head. Short signatures from zero-knowledge proofs
• 2F -- a new method for constructing efficient multivariate encryption schemes
• Algebraic relation of three MinRank algebraic modelings
• A new McEliece-type cryptosystem using Gabidulin-Kronecker product codes
• Enhancing Code Based Zero-Knowledge Proofs Using Rank Metric
• Cryptanalysis of Rank-Metric Schemes Based on Distorted Gabidulin Codes
• On the security of REDOG
• Generic error SDP and generic error CVE
• On the rank decoding problem over finite principal ideal rings
• Blockwise rank decoding problem and LRPC codes: cryptosystems with smaller sizes
• Two modifications for Loidreau's code-based cryptosystem
• Injective rank metric trapdoor functions with homogeneous errors
• Information set decoding for ring-linear codes
• Sneaking up the ranks: partial key exposure attacks on rank-based schemes
• Solving systems of algebraic equations over finite commutative rings and applications
• Somewhat homomorphic encryption based on random codes
• Smaller public keys for MinRank-based schemes
• On the generalizations of the rank metric over finite chain rings
• Hybrid subsupport guessing: a new hybrid technique for the rank decoding problem
• Computer algebra tales on Goppa codes and McEliece cryptography
• On the security of the modified dual-Ouroboros PKE using Gabidulin codes

This page was built for publication: On the Complexity of the Rank Syndrome Decoding Problem

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