research-article

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

Authors:

Philippe Gaborit,

Gilles ZemorAuthors Info & Claims

IEEE Transactions on Information Theory, Volume 62, Issue 12

Pages 7245 - 7252

https://doi.org/10.1109/TIT.2016.2616127

Published: 01 December 2016 Publication History

Abstract

We give a randomized reduction for the Rank Syndrome Decoding problem and Rank Minimum Distance problem for rank codes over extension fields. Our results are based on embedding linear codes in the Hamming space into linear codes over an extension field equipped with the rank metric. We prove that if any of the previous problems for the rank metric is in ZPP = RP \(\cap \)coRP, then we would have NP = ZPP. We also give complexity results for the respective rank metric approximation problems.

Cited By

View all

Franch EGaborit PLi C(2024)Generalized Low-Rank Parity-Check CodesIEEE Transactions on Information Theory10.1109/TIT.2024.340434470:8(5589-5605)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TIT.2024.3404344
Bidoux LBriaud PBros MGaborit P(2024)RQC Revisited and More Cryptanalysis for Rank-Based CryptographyIEEE Transactions on Information Theory10.1109/TIT.2023.333794570:3(2271-2286)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1109/TIT.2023.3337945
Sun ZZhuang JZhou ZFu F(2024)A new McEliece-type cryptosystem using Gabidulin-Kronecker product codesTheoretical Computer Science10.1016/j.tcs.2024.114480994:COnline publication date: 1-May-2024
https://dl.acm.org/doi/10.1016/j.tcs.2024.114480
Show More Cited By

On the Hardness of the Decoding and the Minimum Distance Problems for Rank Codes
1. Mathematics of computing
  1. Information theory

Recommendations

Hardness of approximating the minimum distance of a linear code

We show that the minimum distance d of a linear code is not approximable to within any constant factor in random polynomial time (RP), unless nondeterministic polynomial time (NP) equals RP. We also show that the minimum distance is not approximable to ...
Generalized minimum-distance decoding of Euclidean-space codes and lattices
Part 1

It is shown that multistage generalized minimum-distance (GMD) decoding of Euclidean-space codes and lattices can provide an excellent tradeoff between performance and complexity. We introduce a reliability metric for Gaussian channels that is easily ...
On the hardness of maximum rank aggregation problems

The rank aggregation problem consists in finding a consensus ranking on a set of alternatives, based on the preferences of individual voters. The alternatives are expressed by permutations, whose pairwise distance can be measured in many ways.In this ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

IEEE Transactions on Information Theory Volume 62, Issue 12

December 2016

917 pages

ISSN:0018-9448

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 December 2016

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Franch EGaborit PLi C(2024)Generalized Low-Rank Parity-Check CodesIEEE Transactions on Information Theory10.1109/TIT.2024.340434470:8(5589-5605)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TIT.2024.3404344
Bidoux LBriaud PBros MGaborit P(2024)RQC Revisited and More Cryptanalysis for Rank-Based CryptographyIEEE Transactions on Information Theory10.1109/TIT.2023.333794570:3(2271-2286)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1109/TIT.2023.3337945
Sun ZZhuang JZhou ZFu F(2024)A new McEliece-type cryptosystem using Gabidulin-Kronecker product codesTheoretical Computer Science10.1016/j.tcs.2024.114480994:COnline publication date: 1-May-2024
https://dl.acm.org/doi/10.1016/j.tcs.2024.114480
Bettaieb SBidoux LDyseryn VEsser AGaborit PKulkarni MPalumbi M(2024)PERK: compact signature scheme based on a new variant of the permuted kernel problemDesigns, Codes and Cryptography10.1007/s10623-024-01381-292:8(2131-2157)Online publication date: 27-Mar-2024
https://dl.acm.org/doi/10.1007/s10623-024-01381-2
Guo WFu F(2024)Two modifications for Loidreau’s code-based cryptosystemApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-022-00577-035:5(647-665)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s00200-022-00577-0
Bardet MBriaud PBros MGaborit PTillich J(2023)Revisiting algebraic attacks on MinRank and on the rank decoding problemDesigns, Codes and Cryptography10.1007/s10623-023-01265-x91:11(3671-3707)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1007/s10623-023-01265-x
Song YZhang JHuang XWu W(2023)Blockwise Rank Decoding Problem and LRPC Codes: Cryptosystems with Smaller SizesAdvances in Cryptology – ASIACRYPT 202310.1007/978-981-99-8739-9_10(284-316)Online publication date: 4-Dec-2023
https://dl.acm.org/doi/10.1007/978-981-99-8739-9_10
Manganiello FSlaughter F(2023)Generic Error SDP and Generic Error CVECode-Based Cryptography10.1007/978-3-031-46495-9_7(125-143)Online publication date: 22-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-46495-9_7
Baumeister ABartz HWachter-Zeh A(2023)An Analysis of the RankSign Signature Scheme with Rank MultipliersCode-Based Cryptography10.1007/978-3-031-46495-9_1(1-13)Online publication date: 22-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-46495-9_1
Puchinger SRenner JRosenkilde J(2022)Generic Decoding in the Sum-Rank MetricIEEE Transactions on Information Theory10.1109/TIT.2022.316762968:8(5075-5097)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1109/TIT.2022.3167629
Show More Cited By

Abstract

Cited By

Recommendations

Hardness of approximating the minimum distance of a linear code

Generalized minimum-distance decoding of Euclidean-space codes and lattices

On the hardness of maximum rank aggregation problems

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Share

Share this Publication link

Share on social media

Affiliations