Research Topic: Rank-Metric Codes
Rank-metric codes are sets of matrices whose distance is measured by the rank of their difference. Among others, they can be used for error correction in channels that add an error of low rank to an input matrix. In particular, applications include network coding, code-based cryptography, distributed data storage, low-rank matrix recovery, space-time coding for MIMO systems, and digital image watermarking. Aims of research on rank-metric codes are, for instance, more efficient decoding, construction of new codes with interesting properties, as well as improving applications of the codes in various ways.
Related Publications
| [J] | (preprint) Hannes Bartz, Sven Puchinger Fast Decoding of Interleaved Linearized Reed–Solomon Codes and Variants [arxiv] submitted to IEEE Transactions on Information Theory, 2022 |
| [J] | (preprint) Hannes Bartz, Lukas Holzbaur, Hedongliang Liu, Sven Puchinger, Julian Renner, Antonia Wachter-Zeh Rank-Metric Codes and Their Applications submitted to Foundations and Trends in Communications and Information Theory, 2021 |
| [J] | (preprint) Sven Puchinger, Julian Renner, Johan Rosenkilde Generic Decoding in the Sum-Rank Metric [arxiv] in revision for IEEE Transactions on Information Theory, 2020 |
| [J] | Lukas Holzbaur, Sven Puchinger, Eitan Yaakobi, Antonia Wachter-Zeh Partial MDS Codes with Regeneration [link] [arxiv] IEEE Transactions on Information Theory, vol. 67, no. 10, pp. 6425-6441, October 2021 |
| [J] | Hannes Bartz, Thomas Jerkovits, Sven Puchinger, Johan Rosenkilde Fast Decoding of Codes in the Rank, Subspace, and Sum-Rank Metric [link] [arxiv] IEEE Transactions on Information Theory, vol. 67, no. 8, pp. 5026-5050, August 2021 |
| [J] | Julian Renner, Sven Puchinger, Antonia Wachter-Zeh LIGA: A Cryptosystem Based on the Hardness of Rank-Metric List and Interleaved Decoding [link] [arxiv] Designs, Codes and Cryptography, vol. 89, pp. 1279–1319, 2021 |
| [J] | Julian Renner, Alessandro Neri, Sven Puchinger Low-Rank Parity-Check Codes over Galois Rings [link] [arxiv] Designs, Codes and Cryptography, vol. 89, pp. 351-386, 2021 |
| [J] | Alessandro Neri, Sven Puchinger, Anna-Lena Horlemann-Trautmann Equivalence and Characterizations of Linear Rank-Metric Codes Based on Invariants [link] [arxiv] Linear Algebra and Its Applications, vol. 603, pp. 418-469, 2020 |
| [J] | Sven Puchinger, Antonia Wachter-Zeh Fast Operations on Linearized Polynomials and their Applications in Coding Theory [link] [arxiv] Journal of Symbolic Computation, vol. 89, pp. 194-215, 2018 |
| [J] | Sven Puchinger, Johan Rosenkilde, Wenhui Li, Vladimir Sidorenko Row Reduction Applied to Decoding of Rank-Metric and Subspace Codes [link] [arxiv] Designs, Codes and Cryptography, vol. 82(1-2), pp. 389-409, 2017 |
| [J] | Sven Puchinger, Sven Müelich, David Mödinger, Johan Rosenkilde, Martin Bossert Decoding interleaved Gabidulin codes using Alekhnovich's algorithm [link] [arxiv] Electronic Notes in Discrete Mathematics, 57:175-180, 2017 |
| [J] | Sven Müelich, Sven Puchinger, Martin Bossert Low-Rank Matrix Recovery using Gabidulin Codes in Characteristic Zero [link] [arxiv] Electronic Notes in Discrete Mathematics, 57:161-166, 2017 |
| [C] | (preprint) Cornelia Ott, Sven Puchinger, Martin Bossert Bounds and Genericity of Sum-Rank-Metric Codes [arxiv] submitted to International Symposium Problems of Redundancy in Information and Control Systems (REDUNDANCY), 2021 |
| [C] | Lukas Holzbaur, Sven Puchinger, Eitan Yaakobi, Antonia Wachter-Zeh Correctable Erasure Patterns in Product Topologies [arxiv] IEEE International Symposium on Information Theory (ISIT), 2021 |
| [C] | Sven Puchinger, Julian Renner, Antonia Wachter-Zeh, Jens Zumbrägel Efficient Decoding of Gabidulin Codes over Galois Rings [arxiv] IEEE International Symposium on Information Theory (ISIT), 2021 |
| [C] | Sven Puchinger, Johan Rosenkilde Bounds on List Decoding of Linearized Reed-Solomon Codes [arxiv] IEEE International Symposium on Information Theory (ISIT), 2021 |
| [C] | Hannes Bartz, Sven Puchinger Decoding of Interleaved Linearized Reed-Solomon Codes with Applications to Network Coding [arxiv] IEEE International Symposium on Information Theory (ISIT), 2021 |
| [C] | Julian Renner, Sven Puchinger, Antonia Wachter-Zeh Decoding High-Order Interleaved Rank-Metric Codes [arxiv] IEEE International Symposium on Information Theory (ISIT), 2021 |
| [C] | Sven Puchinger, Julian Renner, Johan Rosenkilde Generic Decoding in the Sum-Rank Metric [link] [arxiv] IEEE International Symposium on Information Theory (ISIT), 2020 |
| [C] | Julian Renner, Sven Puchinger, Antonia Wachter-Zeh, Camilla Hollanti, Ragnar Freij-Hollanti Low-Rank Parity-Check Codes over the Ring of Integers Modulo a Prime Powers [link] [arxiv] IEEE International Symposium on Information Theory (ISIT), 2020 |
| [C] | Julian Renner, Thomas Jerkovits, Hannes Bartz, Sven Puchinger, Pierre Loidreau, Antonia Wachter-Zeh Randomized Decoding of Gabidulin Codes Beyond the Unique Decoding Radius [link] [arxiv] International Conference on Post-Quantum Cryptography (PQCrypto), 2020 |
| [C] | Julian Renner, Sven Puchinger, Antonia Wachter-Zeh Interleaving Loidreau's Rank-Metric Cryptosystem [link] [arxiv] International Symposium on Problems of Redundancy in Information and Control Systems (REDUNDANCY), 2019 |
| [C] | Hannes Bartz, Thomas Jerkovits, Sven Puchinger, Johan Rosenkilde Fast Root Finding for Interpolation-Based Decoding of Interleaved Gabidulin Codes [link] IEEE Information Theory Workshop (ITW), 2019 |
| [C] | Alessandro Neri, Sven Puchinger, Anna-Lena Horlemann-Trautmann Invariants and Inequivalence of Linear Rank-Metric Codes [link] [arxiv] IEEE International Symposium on Information Theory (ISIT), 2019 |
| [C] | Sven Puchinger, Julian Renner, Antonia Wachter-Zeh Twisted Gabidulin Codes in the GPT Cryptosystem [arxiv] International Workshop on Algebraic and Combinatorial Coding Theory (ACCT), 2018 |
| [C] | Antonia Wachter-Zeh, Sven Puchinger, Julian Renner Repairing the Faure-Loidreau Public-Key Cryptosystem [link] [arxiv] IEEE International Symposium on Information Theory (ISIT), 2018 |
| [C] | Sven Puchinger, Johan Rosenkilde, John Sheekey Further Generalisations of Twisted Gabidulin Codes [arxiv] International Workshop on Coding and Cryptography (WCC), 2017 |
| [C] | Sven Puchinger, Sven Müelich, Martin Bossert On the Success Probability of Decoding (Partial) Unit Memory Codes [link] [arxiv] International Workshop on Optimal Codes and Related Topics, 2017 |
| [C] | Sven Puchinger, Sebastian Stern, Martin Bossert, Robert F.H. Fischer Space-Time Codes Based on Rank-Metric Codes and Their Decoding [link] [arxiv] IEEE International Symposium on Wireless Communication Systems (ISWCS), 2016 |
| [C] | Sven Puchinger, Antonia Wachter-Zeh Sub-Quadratic Decoding of Gabidulin Codes [link] [arxiv] IEEE International Symposium on Information Theory (ISIT), 2016 |
| [C] | Sven Müelich, Sven Puchinger, David Mödinger, Martin Bossert An Alternative Decoding Method for Gabidulin Codes in Characteristic Zero [link] [arxiv] IEEE International Symposium on Information Theory (ISIT), 2016 |
| [C] | Wenhui Li, Johan S.R. Nielsen, Sven Puchinger, Vladimir Sidorenko Solving Shift Register Problems over Skew Polynomial Rings using Module Minimisation [link] [arxiv] International Workshop on Coding and Cryptography (WCC), 2015 |
| [C] | Sven Puchinger, Michael Cyran, Robert F.H. Fischer, Martin Bossert, Johannes B. Huber Error Correction for Differential Linear Network Coding in Slowly Varying Networks [link] [arxiv] International ITG Conference on Systems, Communications and Coding (SCC), 2015 |
(overlap with other topics, click here for all publications)
Interleaved codes are direct sums of codes of the same length. By assuming that errors occur in certain patterns, it is often possible to correct more errors than half the minimum distance. In the Hamming metric the assumed model is that errors occur in the same positions of the constituent codewords. Such error patterns occur, for instance, in file disagreement location, burst errors in data-storage applications, decoding outer codes of concatenated codes, certain ALOHA-like random-access schemes, decoding non-interleaved codes beyond half-the-minimum distance by power decoding, error-decoding of certain locally repairable and partial MDS codes, and code-based cryptography. In the rank metric, the constituent codewords are corrupted by low-rank matrices whose row (or column) spaces are similar. Such errors occur in network coding when lifting interleaved rank-metric codes and are used in code-based cryptosystems to reduce key sizes. Research goals for interleaved codes with various constituent codes are decoding more errors, faster decoding, as well as applications of the codes.
The family of Algebraic Geometry (AG) codes contains some of the best-known algebraic codes, including Reed-Solomon (RS) codes, which are MDS (i.e., attain the maximal possible minimum distance for a given length and dimension). The codes and their subfield subcodes have found various applications, including satellite communication, CDs, DVDs, BluRays, RAID systems, SSDs, QR codes, code-based cryptography, and distributed storage systems. Research topics range from construction of new AG or AG-like codes with good minimum distances or other interesting properties, decoding more errors, efficient en- and decoding, to applications of the codes.
Partial Unit Memory (PUM) codes are convolutional codes that are constructed from block codes. This construction results in a good algebraic structure of the convolutional codes and thus good distance properties. For decoding, usually a combination of decoders of the underlying block codes and a Viterbi decoder is used. The codes can be constructed in the Hamming metric, and also from rank-metric codes, in which case the PUM code is considered in the sum-rank metric. PUM codes have applications in straming scenarios, multi-shot network coding, and data storage. Research goals are new constructions and decoding of PUM codes, as well as analyzing the codes in applications. 
Computer algebra studies algorithms for computations with mathematical objects, typically using exact computation (in contrast to floating point arithmetic). In coding theory, encoding and decoding of codes are algorithms that are often based on computations with polynomials, matrices, and polynomial matrices over finite fields or other fields that allow exact computation (such as number fields). In order to efficiently en- and decode codes, it is essential to know efficient algorithms to perform these kinds of computations. Current decoding-related research areas in computer algebra are, for instance, operations with multi-variate polynomials (algebraic-geometry codes) and the non-commutative skew or linearized polynomials (rank-metric codes).
Public-key cryptosystems are an essential part of many data transmission systems and protocols. Currently-used systems based on number-theoretic problems are however threatened by the possibility that large-scale quantum computers might be built in near future - Shor's algorithm is able to solve these seemingly hard problems in polynomial time on such a computer. Hence, there is a need for post-quantum secure cryptosystems. Code-based cryptosystems, in particular the McEliece cryptosystem and its variants, are public-key cryptosystems based on error-correcting codes, and the oldest ones of the few discussed post-quantum systems. Important aims of research are the reduction of key and ciphertext sizes, efficient decryption, security analysis of existing schemes, and finding suitable code-based signature schemes.
Physical Unclonable Functions (PUFs) are hardware primitives that utilize manufacturing variations to generate random but reproducible sequences. Unclonable refers to the hardness of manufacturing two PUFs with a similar output. The output sequences can be used for key generation in cryptographic applications. They can also be reproduced by the same PUF on demand, making (expensive) secure non-volatile key storage obsolete. This reproduction process, however, is noisy due to measurement uncertainty, aging, and temperature or voltage variations, and hence, error-correcting codes must be used to increase the regeneration reliability. Stronger error correction may allow the extraction and regeneration of longer random sequences from the same hardware. Research areas include the study of, and code design for, various atypical channel models occuring in the regeneration process. Moreover, efficient and secure implementations of decoders are necessary for the practicality of the proposed coding schemes. 
Coding is an important ingredient of any machine-readable data storage system due to write, read and other types of errors, as well as failures of parts of the system. Research in this area include analyzing media-specific error models and coding constraints, as well as proposing coding solutions for various storage media allowing to increase the amount of stored data or reliability. Among many others, this includes flash memories, which are used in commercial products like USB sticks or SSDs, and also potential future storage media like synthesized DNA. Another aspect of research are distributed data storage systems, where failures occur in the system and coding solutions aim not only at increasing the reliability of the system, but also at minimizing the cost (e.g., amount of transmitted data) for reparing the failed part of the system.
Network coding is a method to increase the throughput and eavesdropping resilience of data transmission through a network. The idea is to combine packets at intermediate nodes instead of only forwarding them, e.g., using linear combinations of packets (which are vectors in this case). Coding theory can be applied to network coding in various ways. For instance, it can be used to increase the reliability of the system in case of errors or erasures within the network. It can also be used to construct the functions that combine packets at the nodes such that the transmitted packets can be reconstructed at the destination nodes.