On the Hardness of the Decoding and the Minimum Distance Problems for Rank Codes

No abstract is available for this paper.

• Publication year

  2016

• Venue

  IEEE Transactions on Information Theory

• Publication date

  2016-12-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/TIT.2016.2616127
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A Heuristic Quasi-Polynomial Algorithm for Discrete Logarithm in Finite Fields of Small Characteristic

  2014cited by this paper
• RankSign: An Efficient Signature Algorithm Based on the Rank Metric

  2014cited by this paper
• On the Complexity of the Rank Syndrome Decoding Problem

  2013cited by this paper
• MDPC-McEliece: New McEliece variants from Moderate Density Parity-Check codes

  2013cited by this paper
• List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound

  2013cited by this paper
• A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic

  2013cited by this paper
• Low Rank Parity Check codes and their application to cryptography

  2013cited by this paper
• Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction

  2012cited by this paper
• List decoding subspace codes from insertions and deletions

  2012cited by this paper
• Decoding Random Binary Linear Codes in 2n/20: How 1+1=0 Improves Information Set Decoding

  2012cited by this paper
• Algebraic List-Decoding of Subspace Codes

  2012cited by this paper
• Full Cryptanalysis of the Chen Identification Protocol

  2011cited by this paper
• On Linear Network Coding

  2010cited by this paper
• On Ideal Lattices and Learning with Errors over Rings

  2010cited by this paper
• A Deterministic Reduction for the Gap Minimum Distance Problem

  2009cited by this paper
• Reducing Key Length of the McEliece Cryptosystem

  2009cited by this paper
• Error and erasure correcting algorithms for rank codes

  2008cited by this paper
• Coding for Errors and Erasures in Random Network Coding

  2007cited by this paper
• Properties of codes in rank metric

  2006cited by this paper
• Efficient Zero-Knowledge Authentication Based on a Linear Algebra Problem MinRank

  2001cited by this paper
• Hardness of approximating the minimum distance of a linear code

  2000cited by this paper
• Hardness of approximating the minimum distance of a linear code

  1999cited by this paper
• NTRU: A Ring-Based Public Key Cryptosystem

  1998cited by this paper
• Space-Time Codes for High Data Rate Wireless Communications : Performance criterion and Code Construction

  1998cited by this paper
• Algorithmic complexity in coding theory and the minimum distance problem

  1997cited by this paper
• Introduction to Coding Theory

  1993cited by this paper
• The hardness of approximate optima in lattices, codes, and systems of linear equations

  1993cited by this paper
• A Catalog of Complexity Classes

  1991cited by this paper
• Ideals over a Non-Commutative Ring and thier Applications in Cryptology

  1991cited by this paper
• The difference between consecutive primes

  1985cited by this paper
• Introduction to Coding Theory

  1982cited by this paper
• On the inherent intractability of certain coding problems (Corresp.)

  1978cited by this paper
• Bilinear Forms over a Finite Field, with Applications to Coding Theory

  1978cited by this paper
• A THEOREM ON MATRICES OVER A SFIELD AND ITS APPLICATIONS

  1951cited by this paper
• On a special class of polynomials

  1933cited by this paper
• Theory of Error-correcting Codes

  year unknowncited by this paper

• Extended Gabidulin-Kronecker Product Codes and Their Application to Cryptosystems

  2026cites this paper
• Information set decoding for ring-linear codes

  2025cites this paper
• A Zero-Knowledge Proof for the Syndrome Decoding Problem in the Lee Metric

  2025cites this paper
• Blockwise Rank Decoding Problem and LRPC Codes: Cryptosystems With Smaller Sizes

  2025cites this paper
• Hybrid Subsupport Guessing: A New Hybrid Technique for the Rank Decoding Problem

  2025cites this paper
• A Code-based Group Signature Scheme from the Schnorr-Lyubashevsky Framework

  2025cites this paper
• PERK: compact signature scheme based on a new variant of the permuted kernel problem

  2024cites this paper
• Cryptanalysis of the SHMW signature scheme

  2024cites this paper
• Characterization of the Complexity of Computing the Capacity of Colored Gaussian Noise Channels

  2024cites this paper
• A new McEliece-type cryptosystem using Gabidulin-Kronecker product codes

  2024cites this paper
• Generic Error SDP and Generic Error CVE

  2023cites this paper
• The Blockwise Rank Syndrome Learning problem and its applications to cryptography

  2023cites this paper
• Characterization of the Complexity of Computing the Capacity of Colored Noise Gaussian Channels

  2023cites this paper
• Injective Rank Metric Trapdoor Functions with Homogeneous Errors

  2023cites this paper
• Generalized low rank parity check codes

  2023cites this paper
• Two new algorithms for error support recovery of low rank parity check codes

  2023cites this paper
• Generalized Low-Rank Parity-Check Codes

  2023cites this paper
• Improved Information Set Decoding Algorithms over Galois Ring in the Lee Metric

  2023cites this paper
• New Design of Blockwise Interleaved Ideal Low-Rank Parity-Check Codes for Fast Post-Quantum Cryptography

  2023cites this paper
• Rank AGS Identification Scheme and Signature Scheme

  2023cites this paper
• LowMS: a new rank metric code-based KEM without ideal structure

  2023cites this paper
• Rank-Metric Codes and Their Applications

  2022cites this paper
• A gapless code-based hash proof system based on RQC and its applications

  2022cites this paper
• RQC Revisited and More Cryptanalysis for Rank-Based Cryptography

  2022cites this paper
• Layered ROLLO-I: Faster rank-metric code-based KEM using ideal LRPC codes

  2022cites this paper
• Generic Decoding in the Sum-Rank Metric

  2022cites this paper
• Post-Quantum Cryptography - Codes

  2022cites this paper
• LRPC codes with multiple syndromes: near ideal-size KEMs without ideals

  2022cites this paper
• Generic Decoding in the Cover Metric

  2022cites this paper
• Revisiting algebraic attacks on MinRank and on the rank decoding problem

  2022cites this paper
• A new post-quantum multivariate polynomial public key encapsulation algorithm

  2022cites this paper
• McEliece-type encryption based on Gabidulin codes with no hidden structure

  2022cites this paper
• Semilinear Transformations in Coding Theory: A New Technique in Code-Based Cryptography

  2021cites this paper
• Low Row Rank Parity Check Codes

  2021cites this paper
• Solving the Rank Decoding Problem Over Finite Principal Ideal Rings

  2021cites this paper
• Expanded Gabidulin Codes and Their Application to Cryptography

  2021cites this paper
• Semilinear transformations in coding theory and their application to cryptography

  2021cites this paper
• Two Public-Key Cryptosystems Based on Expanded Gabidulin Codes

  2021cites this paper
• A Novel Niederreiter-like cryptosystem based on the (u|u + υ)-construction codes

  2021cites this paper
• Two modifications for Loidreau’s code-based cryptosystem

  2021cites this paper
• Quantum-safe cryptography: crossroads of coding theory and cryptography

  2021cites this paper
• New McEliece Cryptosystem Based on Polar-LDPC Concatenated Codes as a Post-quantum Cryptography

  2021cites this paper
• On the rank decoding problem over finite principal ideal rings

  2021cites this paper
• An algebraic approach to the Rank Support Learning problem

  2021cites this paper
• Information Security Theory and Practice: 13th IFIP WG 11.2 International Conference, WISTP 2019, Paris, France, December 11–12, 2019, Proceedings

  2020influential citation
• On the security of the modified Dual-ouroboros PKE using Gabidulin codes

  2020cites this paper
• Algebraic attacks for solving the Rank Decoding and MinRank problems without Gröbner basis

  2020cites this paper
• An improved Durandal signature scheme

  2020cites this paper
• On the hardness of the Lee syndrome decoding problem

  2020cites this paper
• Improvements of Algebraic Attacks for Solving the Rank Decoding and MinRank Problems

  2020cites this paper
• Generic Decoding in the Sum-Rank Metric

  2020cites this paper
• Code-Based Cryptography: 8th International Workshop, CBCrypto 2020, Zagreb, Croatia, May 9–10, 2020, Revised Selected Papers

  2020cites this paper
• MURAVE: A New Rank Code-Based Signature with MUltiple RAnk VErification

  2020cites this paper
• Rank-metric code-based mutual authentication protocol for RFID

  2020cites this paper
• On the Hardness of the Lee Syndrome Decoding Problem

  2020cites this paper
• NP-Complete Problems for Lee Metric Codes

  2020cites this paper
• Randomized Decoding of Gabidulin Codes Beyond the Unique Decoding Radius

  2019cites this paper
• Durandal: a rank metric based signature scheme

  2019cites this paper
• Interleaving Loidreau’s Rank-Metric Cryptosystem

  2019cites this paper
• Low Rank Parity Check Codes: New Decoding Algorithms and Applications to Cryptography

  2019cites this paper
• A New Gabidulin-Like Code and Its Application in Cryptography

  2019cites this paper
• Two New Module-Code-Based KEMs with Rank Metric

  2019cites this paper
• Cryptanalysis on CCA2-Secured LRPC-Kronecker Cryptosystem

  2019cites this paper
• Preventing Timing Attacks Against RQC Using Constant Time Decoding of Gabidulin Codes

  2019cites this paper
• New rank codes based encryption scheme using partial circulant matrices

  2019cites this paper
• An IND-CCA2 secure post-quantum encryption scheme and a secure cloud storage use case

  2019cites this paper
• Loong: a new IND-CCA-secure code-based KEM

  2019cites this paper
• An Algebraic Attack on Rank Metric Code-Based Cryptosystems

  2019cites this paper
• A modified Dual-Ouroboros public-key encryption using Gabidulin codes

  2019cites this paper
• Strong Designated Verifier Signature Based on the Rank Metric

  2019cites this paper
• New Signature Algorithm Based on Concatenated Rank Codes

  2019cites this paper
• Cryptanalysis of a rank-based signature with short public keys

  2019cites this paper
• A New Encryption Scheme Based on Rank Metric Codes

  2018cites this paper
• Two attacks on rank metric code-based schemes: RankSign and an Identity-Based-Encryption scheme

  2018cites this paper
• An attack on a NIST proposal: RankSign, a code-based signature in rank metric

  2018cites this paper
• A New Technique in Rank Metric Code-Based Encryption

  2018cites this paper
• A New LRPC-Kronecker Product Codes Based Public-Key Cryptography

  2018cites this paper
• McNie2-Gabidulin: An improvement of McNie public key encryption using Gabidulin code

  2018cites this paper
• McNie: A code-based public-key cryptosystem

  2018cites this paper
• Two Attacks on Rank Metric Code-Based Schemes: RankSign and an IBE Scheme

  2018cites this paper
• Code-Based Signature Schemes from Identification Protocols in the Rank Metric

  2018cites this paper
• The Learning with Rank Errors problem and an application to symmetric authentication

  2018cites this paper
• Key Recovery Attack on McNie Based on Low Rank Parity Check Codes and Its Reparation

  2018cites this paper
• Evolution of the McEliece Public Key Encryption Scheme

  2017cites this paper
• The problem with the SURF scheme

  2017cites this paper
• An algebraic approach for the resolution of algorithmic problems raised by cryptography and coding theory

  2017cites this paper
• Algebraic approach for the study of algorithmic problems coming from cryptography and the theory of error correcting codes. (Approche algébrique pour l'étude et la résolution de problèmes algorithmiques issus de la cryptographie et de la théorie des codes )

  2017cites this paper
• Security of cryptographic protocols based on coding theory

  2017cites this paper
• A new signature scheme based on (U|U+V) codes

  2017cites this paper
• A New Rank Metric Codes Based Encryption Scheme

  2017cites this paper
• A code-based blind signature

  2017cites this paper
• A Practical Group Signature Scheme Based on Rank Metric

  2016cites this paper
• Efficient Encryption From Random Quasi-Cyclic Codes

  2016cites this paper
• RankSynd a PRNG Based on Rank Metric

  2016influential citation
• Contributions à la cryptographie post-quantique

  2016cites this paper
• Rank based Cryptography: a credible post-quantum alternative to classical crypto

  2015cites this paper
• RankSign: An Efficient Signature Algorithm Based on the Rank Metric

  2014cites this paper
• Décodage en métrique rang et attaques sur un système de chiffrement à base de codes LRPC

  2014cites this paper
• On the Complexity of the Rank Syndrome Decoding Problem

  2013cites this paper
• RYDE Signature Scheme Algorithm Specifications and Supporting Documentation

  year unknowncites this paper