Generic Decoding in the Cover Metric

Sebastian Bitzer; Julian Renner; Antonia Wachter-Zeh; Violetta Weger

doi:10.1109/ITW55543.2023.10160246

Generic Decoding in the Cover Metric

Sebastian Bitzer, Julian Renner, Antonia Wachter-Zeh, Violetta Weger

Associate Professorship of Coding and Cryptography

Technical University of Munich

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

Properties of random codes endowed with the cover metric are considered. We prove the NP-hardness of the decoding problem and then provide a generic decoder, following the information set decoding idea from Prange's algorithm in the Hamming metric. Despite the cover metric lying between the Hamming and the rank metric, the complexity analysis of the algorithm reveals a significant difference between the metrics.

Original language	English
Title of host publication	2023 IEEE Information Theory Workshop, ITW 2023
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	243-247
Number of pages	5
ISBN (Electronic)	9798350301496
DOIs	https://doi.org/10.1109/ITW55543.2023.10160246
State	Published - 2023
Event	2023 IEEE Information Theory Workshop, ITW 2023 - Saint-Malo, France Duration: 23 Apr 2023 → 28 Apr 2023

Publication series

Name	2023 IEEE Information Theory Workshop, ITW 2023

Conference

Conference	2023 IEEE Information Theory Workshop, ITW 2023
Country/Territory	France
City	Saint-Malo
Period	23/04/23 → 28/04/23

Access to Document

10.1109/ITW55543.2023.10160246

Cite this

@inproceedings{902218ecdbc942e7915e7e32593713d7,

title = "Generic Decoding in the Cover Metric",

abstract = "Properties of random codes endowed with the cover metric are considered. We prove the NP-hardness of the decoding problem and then provide a generic decoder, following the information set decoding idea from Prange's algorithm in the Hamming metric. Despite the cover metric lying between the Hamming and the rank metric, the complexity analysis of the algorithm reveals a significant difference between the metrics.",

author = "Sebastian Bitzer and Julian Renner and Antonia Wachter-Zeh and Violetta Weger",

note = "Publisher Copyright: {\textcopyright} 2023 IEEE.; 2023 IEEE Information Theory Workshop, ITW 2023 ; Conference date: 23-04-2023 Through 28-04-2023",

year = "2023",

doi = "10.1109/ITW55543.2023.10160246",

language = "English",

series = "2023 IEEE Information Theory Workshop, ITW 2023",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "243--247",

booktitle = "2023 IEEE Information Theory Workshop, ITW 2023",

}

Bitzer, S, Renner, J, Wachter-Zeh, A & Weger, V 2023, Generic Decoding in the Cover Metric. in 2023 IEEE Information Theory Workshop, ITW 2023. 2023 IEEE Information Theory Workshop, ITW 2023, Institute of Electrical and Electronics Engineers Inc., pp. 243-247, 2023 IEEE Information Theory Workshop, ITW 2023, Saint-Malo, France, 23/04/23. https://doi.org/10.1109/ITW55543.2023.10160246

Generic Decoding in the Cover Metric. / Bitzer, Sebastian; Renner, Julian; Wachter-Zeh, Antonia et al.
2023 IEEE Information Theory Workshop, ITW 2023. Institute of Electrical and Electronics Engineers Inc., 2023. p. 243-247 (2023 IEEE Information Theory Workshop, ITW 2023).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Generic Decoding in the Cover Metric

AU - Bitzer, Sebastian

AU - Renner, Julian

AU - Wachter-Zeh, Antonia

AU - Weger, Violetta

PY - 2023

Y1 - 2023

N2 - Properties of random codes endowed with the cover metric are considered. We prove the NP-hardness of the decoding problem and then provide a generic decoder, following the information set decoding idea from Prange's algorithm in the Hamming metric. Despite the cover metric lying between the Hamming and the rank metric, the complexity analysis of the algorithm reveals a significant difference between the metrics.

AB - Properties of random codes endowed with the cover metric are considered. We prove the NP-hardness of the decoding problem and then provide a generic decoder, following the information set decoding idea from Prange's algorithm in the Hamming metric. Despite the cover metric lying between the Hamming and the rank metric, the complexity analysis of the algorithm reveals a significant difference between the metrics.

UR - http://www.scopus.com/inward/record.url?scp=85165004548&partnerID=8YFLogxK

U2 - 10.1109/ITW55543.2023.10160246

DO - 10.1109/ITW55543.2023.10160246

M3 - Conference contribution

AN - SCOPUS:85165004548

T3 - 2023 IEEE Information Theory Workshop, ITW 2023

SP - 243

EP - 247

BT - 2023 IEEE Information Theory Workshop, ITW 2023

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2023 IEEE Information Theory Workshop, ITW 2023

Y2 - 23 April 2023 through 28 April 2023

ER -

Generic Decoding in the Cover Metric

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this