Séminaire de Cryptographie

Accueil     Présentation     Archives

Hannes Bartz

Algebraic Decoding of Folded Gabidulin Codes

Folded Gabidulin codes were proposed by Mahdavifar and Vardy in 2012. Beside the code construction an interpolation-based decoding scheme that can correct rank errors beyond the unique decoding radius for low code rates was presented. In this talk we present an efficient interpolation-based decoding algorithm for folded Gabidulin codes that can correct rank errors beyond half the minimum rank distance for any code rate 0 ? R ? 1. The algorithm serves as a list decoder or as a probabilistic unique decoder and improves upon existing schemes, especially for high code rates. A probabilistic unique decoder with adjustable decoding radius is presented that outputs a unique solution with high probability. An upper bound on the average list size of folded Gabidulin codes and on the decoding failure probability of the decoder is presented. We show how to modify the decoding algorithm by Mahdavifahr and Vardy to use it as a probabilistic unique decoder for low-rate codes.