nach oben

Designs, Codes and Cryptography

Erschienen in:

02.08.2016

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

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

Erschienen in: Designs, Codes and Cryptography | Ausgabe 1-2/2017

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel Security proof of the canonical form of self-synchronizing stream ciphers

Nächster Artikel Energy bounds for codes and designs in Hamming spaces

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.

\(\mathcal{{R}}\) is also right Euclidean, a right PID and right Noetherian, but we will only need its left module structure.

Skew fields are sometimes known as “division rings”.

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.

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)\).

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\).

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.

Abramov S.A., Bronstein M.: On solutions of linear functional systems. In: Proceedings of ISSAC, pp. 1–6 (2001).

Alekhnovich M.: Linear Diophantine equations over polynomials and soft decoding of Reed–Solomon codes. IEEE Trans. Inf. Theory 51(7), 2257–2265 (2005).

Augot D., Loidreau P., Robert G.: Rank metric and Gabidulin codes in characteristic zero. In: ISIT (2013).

Baker G., Graves-Morris P.: Padé Approximants, vol. 59. Cambridge University Press, Cambridge (1996).

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).

Beckermann B., Cheng H., Labahn G.: Fraction-free row reduction of matrices of Ore polynomials. J. Symb. Comput. 41(5), 513–543 (2006).

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).

Boucher D., Ulmer F.: Linear codes using skew polynomials with automorphisms and derivations. Des. Codes Cryptogr. 70(3), 405–431 (2014).

Cohn H., Heninger N.: Ideal forms of Coppersmith’s theorem and Guruswami–Sudan list decoding (2010). arXiv:1008.1284.

10.

Clark P.L.: Non-commutative algebra. University of Georgia. http://math.uga.edu/~pete/noncommutativealgebra.pdf (2012).

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.

Mulders T., Storjohann A.: On lattice reduction for polynomial matrices. J. Symb. Comput. 35(4), 377–401 (2003).CrossRefMATHMathSciNet

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).

Titel: Row reduction applied to decoding of rank-metric and subspace codes
verfasst von: Sven Puchinger
Johan Rosenkilde né Nielsen
Wenhui Li
Vladimir Sidorenko
Publikationsdatum: 02.08.2016
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 1-2/2017
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-016-0257-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 1-2/2017

Redefining the transparency order

Almost cover-free codes and designs

Hasse–Weil bound for additive cyclic codes

Improved elliptic curve hashing and point representation

Signature codes for noisy multiple access adder channel

On the direct construction of recursive MDS matrices