CWI Cryptology Group

Abstract: Compared with classical block codes, efficient list decoding of rank-metric codes seems more difficult. The evidences to support this view include: (i) so far people have not found polynomial time list decoding algorithms of rank-metric codes with decoding radius beyond if ratio of the number of rows over the number of columns is constant, but not very small; (ii) the Johnson bound for rank-metric codes does not exist as opposed to classical codes; (iii) the Gabidulin codes can not be list decoded beyond half of minimum distance. We give an explicit construction of rank-metric codes with constant ratio of the number of rows over the number of columns and our codes can be efficiently list decoded beyond (1-R)/2. Meanwhile, our codes can approach Singleton bound when the ratio is sufficiently small. To our best knowledge, it is the first known rank-metric codes with above properties