Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Designs, Codes and Cryptography
Published in: Designs, Codes and Cryptography 1-2/2017

02-08-2016

Row reduction applied to decoding of rank-metric and subspace codes

Authors: Sven Puchinger, Johan Rosenkilde né Nielsen, Wenhui Li, Vladimir Sidorenko

Published in: Designs, Codes and Cryptography | Issue 1-2/2017

Login to get access

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We show that decoding of \(\ell \)-Interleaved Gabidulin codes, as well as list-\(\ell \) decoding of Mahdavifar–Vardy (MV) codes can be performed by row reducing skew polynomial matrices. Inspired by row reduction of \(\mathbb {F}[x]\) matrices, we develop a general and flexible approach of transforming matrices over skew polynomial rings into a certain reduced form. We apply this to solve generalised shift register problems over skew polynomial rings which occur in decoding \(\ell \)-Interleaved Gabidulin codes. We obtain an algorithm with complexity \(O(\ell \mu ^2)\) where \(\mu \) measures the size of the input problem and is proportional to the code length n in the case of decoding. Further, we show how to perform the interpolation step of list-\(\ell \)-decoding MV codes in complexity \(O(\ell n^2)\), where n is the number of interpolation constraints.
previous article Security proof of the canonical form of self-synchronizing stream ciphers
next article Energy bounds for codes and designs in Hamming spaces
Footnotes
1
We opted for using the term “row reduction” rather than “module minimisation”, as we used in [24], since the former is more common in the literature.
 
2
\(\mathcal{{R}}\) is also right Euclidean, a right PID and right Noetherian, but we will only need its left module structure.
 
3
Skew fields are sometimes known as “division rings”.
 
4
There is a precise notion of “row reduced” [20, p. 384] for \(\mathbb {F}[x]\) matrices. Weak Popov form implies being row reduced, but we will not formally define row reduced in this paper.
 
5
In [28], the claimed complexity of their root-finding is \(O(\ell ^{O(1)} k)\). However, we have to point out that the complexity analysis of that algorithm has severe issues which are outside the scope of this paper to amend. There are two problems: (1) It is not proven that the recursive calls will not produce many spurious “pseudo-roots” which are sifted away only at the leaf of the recursions; and (2) the cost analysis ignores the cost of computing the shifts \(Q(X, Y^q + \gamma Y)\). Issue 1 is necessary to resolve for assuring polynomial complexity. For the original \(\mathbb {F}[x]\)-algorithm this is proved as [42, Proposition 6.4], and an analogous proof might carry over. Issue 2 is critical since these shifts dominate the complexity: assuming the algorithm makes a total of \(O(\ell k)\) recursive calls to itself, then \(O(\ell k)\) shifts need to be computed, each of which costs \(O(\ell \deg _x Q) \subset O(\ell n)\). If Issue 1 is resolved the algorithm should then have complexity \(O(\ell ^2 k n)\).
 
6
This is a realistic shift register problem arising in decoding of an Interleaved Gabidulin code with \(n=s=100\), \(k_1 = 58\), \(k_2 = 31\).
 
7
In the conference version of this paper [24], we erroneously claimed a too strong statement concerning this. However, one can relate the complexity of Algorithm 4 to the number of non-zero monomials of \(g_i\), as long as all but the leading monomial have low degree; however the precise statement becomes cumbersome and is not very relevant for this paper.
 
Literature
1.
Abramov S.A., Bronstein M.: On solutions of linear functional systems. In: Proceedings of ISSAC, pp. 1–6 (2001).
2.
Alekhnovich M.: Linear Diophantine equations over polynomials and soft decoding of Reed–Solomon codes. IEEE Trans. Inf. Theory 51(7), 2257–2265 (2005).
3.
Augot D., Loidreau P., Robert G.: Rank metric and Gabidulin codes in characteristic zero. In: ISIT (2013).
4.
Baker G., Graves-Morris P.: Padé Approximants, vol. 59. Cambridge University Press, Cambridge (1996).
5.
Beckermann B., Labahn G.: A uniform approach for the fast computation of matrix-type Padé approximants. SIAM J. Matrix Anal. Appl. 15(3), 804–823 (1994).
6.
Beckermann B., Cheng H., Labahn G.: Fraction-free row reduction of matrices of Ore polynomials. J. Symb. Comput. 41(5), 513–543 (2006).
7.
Beelen P., Brander K.: Key equations for list decoding of Reed–Solomon codes and how to solve them. J. Symb. Comput. 45(7), 773–786 (2010).
8.
Boucher D., Ulmer F.: Linear codes using skew polynomials with automorphisms and derivations. Des. Codes Cryptogr. 70(3), 405–431 (2014).
9.
10.
11.
Delsarte P.: Bilinear forms over a finite field, with applications to coding theory. J. Comb. Theory 25(3), 226–241 (1978).
12.
Dieudonné J.: Les déterminants sur un corps non commutatif. Bull. Soc. Math. France 71, 27–45 (1943).
13.
Draxl P.K.: Skew Fields, vol. 81. Cambridge University Press, Cambridge (1983).
14.
Feng G.L., Tzeng K.K.: A generalization of the Berlekamp–Massey algorithm for multisequence shift-register synthesis with applications to decoding cyclic codes. IEEE Trans. Inf. Theory 37(5), 1274–1287 (1991).
15.
Gabidulin E.M.: Theory of codes with maximum rank distance. Problemy Peredachi Informatsii 21(1), 3–16 (1985).
16.
Giorgi P., Jeannerod C., Villard G.: On the complexity of polynomial matrix computations. In: Proceedings of ISSAC, pp. 135–142 (2003).
17.
Guruswami V., Sudan M.: Improved decoding of Reed–Solomon codes and algebraic-geometric codes. IEEE Trans. Inf. Theory 45(6), 1757–1767 (1999).
18.
Guruswami V., Wang C.: Explicit rank-metric codes list-decodable with optimal redundancy. In: Proceedings of RANDOM (2014). arXiv:​1311.​7084.
19.
Guruswami V., Xing C.: List decoding Reed-solomon, algebraic-geometric, and Gabidulin subcodes up to the singleton bound. In: Proceedings of STOC, pp. 843–852. ACM, New York (2013)
20.
Kailath T.: Linear Systems. Prentice-Hall, Upper Saddle River (1980).
21.
Lee K., O’Sullivan M.E.: List decoding of Reed–Solomon codes from a Gröbner basis perspective. J. Symb. Comput. 43(9), 645–658 (2008).
22.
Lenstra A.: Factoring multivariate polynomials over finite fields. J. Comput. Syst. Sci. 30(2), 235–246 (1985).
23.
Li W., Sidorenko V., Silva D.: On transform-domain error and erasure correction by Gabidulin codes. Des. Codes Cryptogr. 73(2), 571–586 (2014).
24.
Li W., Nielsen J.S.R., Puchinger S., Sidorenko V.: Solving shift register problems over skew polynomial rings using module minimisation. In: Proceedings of WCC (2015).
25.
Loidreau P., Overbeck R.: Decoding rank errors beyond the error correcting capability. In: Proceedings of ACCT, pp. 186–190 (2006).
26.
Mahdavifar H.: List decoding of subspace codes and rank-metric codes. Ph.D. thesis, University of California, San Diego (2012).
27.
Mahdavifar H., Vardy A.: Algebraic list-decoding of subspace codes with multiplicities. In: Allerton Conference on Communication, Control, and Computing, pp. 1430–1437 (2011).
28.
Mahdavifar H., Vardy A.: Algebraic list-decoding of subspace codes. IEEE Trans. Inf. Theory 59(12), 7814–7828 (2013).
29.
Middeke J.: A computational view on normal forms of matrices of Ore polynomials. Ph.D. thesis, Research Institute for Symbolic Computation (RISC) (2011).
30.
Müelich S., Puchinger S., Mödinger D., Bossert M.: An alternative decoding method for Gabidulin codes in characteristic zero. In: Proceedings of IEEE ISIT (2016). arXiv:​1601.​05205.
31.
32.
Nielsen J.S.R.: Generalised multi-sequence shift-register synthesis using module minimisation. In: Proceedings of IEEE ISIT, pp. 882–886 (2013).
33.
Nielsen J.S.R.: Power decoding Reed–Solomon codes up to the Johnson radius. In: Proceedings of ACCT (2014).
34.
Nielsen J.S.R., Beelen P.: Sub-quadratic decoding of one-point Hermitian codes. IEEE Trans. Inf. Theory 61(6), 3225–3240 (2015).
35.
Nielsen R.R., Høholdt T.: Decoding Reed–Solomon codes beyond half the minimum distance. In: Coding Theory, Cryptography and Related Areas, pp. 221–236. Springer, Berlin (1998).
36.
Olesh Z., Storjohann A.: The vector rational function reconstruction problem. In: Proceedings of WWCA, pp. 137–149 (2006).
37.
Ore O.: On a special class of polynomials. Trans. Am. Math. Soc. 35(3), 559–584 (1933).
38.
Ore O.: Theory of non-commutative polynomials. Ann. Math. 34(3), 480–508 (1933).
39.
Puchinger S., Wachter-Zeh A.: Fast operations on linearized polynomials and their applications in coding theory. J. Symb. Comput. (2015). arXiv:​1512.​06520.
40.
Puchinger S., Müelich S., Mödinger D., Nielsen J.S.R., Bossert M.: Decoding interleaved Gabidulin codes using Alekhnovich’s algorithm. In: Proceedings of ACCT (2016). arXiv:​1604.​04397.
41.
Roth R.M.: Maximum-rank array codes and their application to crisscross error correction. IEEE Trans. Inf. Theory 37(2), 328–336 (1991).
42.
Roth R., Ruckenstein G.: Efficient decoding of Reed–Solomon codes beyond half the minimum distance. IEEE Trans. Inf. Theory 46(1), 246–257 (2000).
43.
Sidorenko V., Bossert M.: Fast skew-feedback shift-register synthesis. Des. Codes Cryptogr. 70(1–2), 55–67 (2014).
44.
Sidorenko V., Jiang L., Bossert M.: Skew-feedback shift-register synthesis and decoding interleaved Gabidulin codes. IEEE Trans. Inf. Theory 57(2), 621–632 (2011).
45.
Sidorenko V., Schmidt G.: A linear algebraic approach to multisequence shift-register synthesis. Probl. Inf. Transm. 47(2), 149–165 (2011).
46.
Taelman L.: Dieudonné determinants for skew polynomial rings. J. Algebra Appl. 5(1), 89–93 (2006).
47.
Wachter-Zeh A.: Decoding of block and convolutional codes in rank metric. Ph.D. thesis, Universität Ulm (2013).
48.
Xie H., Lin J., Yan Z., Suter B.W.: Linearized polynomial interpolation and its applications. IEEE Trans. Signal Process. 61(1), 206–217 (2013).
49.
Zeh A., Gentner C., Augot D.: An interpolation procedure for list decoding Reed–Solomon codes based on generalized key equations. IEEE Trans. Inf. Theory 57(9), 5946–5959 (2011).
50.
Zhou W., Labahn G.: Efficient algorithms for order basis computation. J. Symb. Comput. 47(7), 793–819 (2012).
Metadata
Title
Row reduction applied to decoding of rank-metric and subspace codes
Authors
Sven Puchinger
Johan Rosenkilde né Nielsen
Wenhui Li
Vladimir Sidorenko
Publication date
02-08-2016
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 1-2/2017
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-016-0257-9

Other articles of this Issue 1-2/2017

Designs, Codes and Cryptography 1-2/2017 Go to the issue

OriginalPaper

Upper bounds on the complexity of algebraic cryptanalysis of ciphers with a low multiplicative complexity

OriginalPaper

Improving algebraic attacks on stream ciphers based on linear feedback shift register over

OriginalPaper

Redefining the transparency order

OriginalPaper

Antiderivative functions over

OriginalPaper

On the direct construction of recursive MDS matrices

OriginalPaper

On some permutation binomials and trinomials over

Premium Partner

    Image Credits