Coding Theory Cartoon

Coding Theory Cartoon

Johan S. R. Nielsen No Comments

Grigory and Leonardo created this great cartoon explaining the principles and importance of coding theory – illustrated by a cross-galactic love story!

The video was made as their contribution to the DTU Compute PhD Bazaar.

Enjoy:

SIAM/AG 2019

Johan S. R. Nielsen No Comments

Johan and Grigory participated in the conference SIAM Applied Algebraic Geometry 2019. The conference had many talks on computer algebra, coding theory and cryptography. Johan gave a talk entitled “Decoding of Gabidulin codes and friends using row reduction of skew polynomial matrices”.

Research visit by Sven Puchinger

Johan S. R. Nielsen No Comments

The Algebra group was visited late January 2019 by Sven Puchinger who is a postdoc at TU München. Sven has visited us before, and is also a former colleague of Johan at Ulm University in 2013-2014. Sven has numerous research papers jointly written with Johan and Peter.

During the visit, we mostly discussed Twisted Reed-Solomon codes: these are optimal codes (MDS) which are constructed by slightly “twisting” a Reed-Solomon code by carefully adding a monomial to the evaluation polynomials. We proposed the codes in an ISIT paper in 2017, and in 2018 we derived more properties and proposed them for quantum-computer-resilient cryptography. After Sven’s visit, we now have new observations which we will write down in an upcoming paper.

Sven also gave a very nice talk entitled “On Decoding and Applications of Interleaved Gabidulin Codes”.

Leonardo Landi, PhD at Algebra Group at DTU

New PhD Student: Leonardo Landi

Johan S. R. Nielsen No Comments

Our new PhD student Leonardo Landi started 1st January 2019! Leonardo holds a Master’s degree from the University of Parma, Italy. His PhD project has the tentative title “Curves and Error-Correction”: the aim is to get a better insight in the structure of algebraic geometry codes constructed using towers of function fields.

Research project in the media

Johan S. R. Nielsen No Comments

Our research project “Correcting on a Curve”, funded by DFF-FNU, has received attention in the media, more specifically the web-based business newspaper Finans.dk:

Danske forskere vil udvikle verdens hurtigste fejlrettende koder

(The full article is unfortunately behind a paywall)

Our project is also featured by DFF’s web page for funded projects:

https://dff.dk/cases/forskere-skal-udvikle-verdens-hurtigste-fejlrettende-koder-til-digital-kommunikation

Paper on record-breaking decoding accepted

Johan S. R. Nielsen No Comments

The paper “Improved Power Decoding of Interleaved One-Point Hermitian Codes” was accepted for publication in the journal Designs, Codes and Cryptography, and should appear soon!

Visit by Prof. Mark Giesbrecht

Johan S. R. Nielsen No Comments

During the first week of September 2018, Professor Mark Giesbrecht visited Johan. Mark is Director of the David R. Cheriton School of Computer Science at the University of Waterloo. His research is in symbolic mathematical computation, both developing the algorithmic and complexity theoretical tools as well as building computer algebra software. He was named ACM Distinguished Scientist in 2013 and received an NSERC Synergy Award in 2003 for work with MapleSoft on Maple.

During his visit, Mark and Johan worked together on computing reduced forms of matrices over Ore polynomial rings, with a focus on \(\mathbb Q[x][\partial; d/dx]\). Ore polynomials are a type of non-commutative polynomials which has applications in such diverse fields as partial differential equations, control theory, and coding theory. Matrices over such polynomials arise e.g. when studying systems of equations in these applications, and reducing the matrices can be used to find small representations of the systems which can reduce later, computationally hard steps. The work is together with Arne Storjohann also at University of Waterloo with whom Johan has worked on this issue earlier.

During his visit, Mark also gave a talk entitled “Algorithms and statistics for additive polynomials”

Abstract:

The additive or linearized polynomials were introduced by Ore in 1933 as an analogy over finite fields to his theory of difference and difference equations over function fields. The additive polynomials over a finite field \(\mathbb{F}_q\), where \(q=p^e\) for some prime \(p\),
are those of the form

$$f = f_0 x + f_1 x^p + f_2 x^{p^2} + … + f_m x^{p^m} \in \mathbb{F}_q[x]$$

They form a non-commutative left-euclidean principal ideal domain under the usual addition and functional composition, and possess a rich structure in both their decomposition structures and root geometries. Additive polynomials have been employed in number theory and algebraic geometry, and applied to constructing error-correcting codes and cryptographic protocols. In this talk we will present fast algorithms for decomposing and factoring additive polynomials, and also for counting the number of decompositions with particular degree sequences.

Algebraically, we show how to reduce the problem of decomposing additive polynomials to decomposing a related associative algebra, the eigenring. We give computationally efficient versions of the Jordan-Holder and Krull-Schmidt theorems in this context to describe all possible factorization. Geometrically, we show how to compute a representation of the Frobenius operator on the space of roots, and how its Jordan form can be used to count the number of decompositions. We also describe an inverse theory, from which we can construct and count the number of additive polynomials with specified factorization patterns.

Some of this is joint work with Joachim von zur Gathen (Bonn) and Konstantin Ziegler (Landshut).

Paper on computing reduced form of polynomial matrices presented

Johan S. R. Nielsen No Comments

The paper “Computing Popov and Hermite forms of rectangular polynomial matrices” was accepted at the prestigious ISSAC conference  earlier this year, and was recently presented at the conference in New York.

The paper is a collaboration between Johan Rosenkilde from the group,  former postdoc Vincent Neiger,  and former Master’s thesis student Grigory Solomatov. Parts of the results were obtained by Grigory during his Master’s thesis!

The paper concerns the computation of something similar to Gaussian elimination but for matrices with entries which are polynomials (univariate).  These kind of computations were recently improved by Vincent for square matrices, but it was still open how to generalise these results to cover rectangular matrices. There are good reasons why this generalisation is not completely straightforward, and in fact most of Grigory’s thesis work was about shooting down all the obvious ways one could think of doing this.

In the end, we found a very elegant randomized algorithm, which is fast in many cases, and a more sophisticated algorithm which works well in almost all cases. The issue is not completely settled, though, and there are still a spectrum of input for which we believe a slightly faster algorithm should exist. That’s for future work!

The full paper can be found here. 

isit 2018

Optimal codes used for post-quantum cryptography

Johan S. R. Nielsen No Comments

Group members Peter Beelen and Johan Rosenkilde with coauthor Sven Puchinger of Ulm University just submitted the paper

   “Structural Properties of Twisted Reed–Solomon Codes with Applications to Cryptography”

to the conference ISIT 2018 (International Symposium in Information Theory).

Twisted Reed-Solomon codes were introduced by the same authors at last year’s ISIT. They are a family of “mutilated” Reed-Solomon codes, many of which are optimal with respect to minimum distance, i.e. they are MDS codes. In this new paper we greatly expand the family of codes by mutilating Reed-Solomon codes multiple times. The new codes are not much more difficult to analyse and we examine several interesting properties of them.

These properties together lead us to conclude that some of the codes might be useful for public-key cryptography! The classical McEliece Cryptosystem is a methodology for turning any family of codes, for which one knows a good decoding algorithm, into a public-key cryptographic cipher. Moreover, if the cipher is secure against attackers using normal computers, then it is also secure against quantum computers! That very clever but it has two draw-backs:

  1. If the attacker can guess the precise parameters of the code one used to make the cipher, then he can break it. This has to date been used to break the cipher for nearly all suggested families of codes! In particular, Reed-Solomon codes are easily breakable.

  2. The public key of the cryptographic cipher can be large, especially if the family of codes does not allow a high decoding capability.

Since many Twisted Reed-Solomon codes are MDS, they have excellent decoding capability and the resulting keys are therefore much smaller than competing suggestions for McEliece, e.g. binary Goppa codes — we give examples with more than a factor 7 reduction! Arguing that the codes are unbreakable is a much more dicey business, however: here we have made some headway by showing that all the properties which makes Reed-Solomon vulnerable do not apply to Twisted Reed-Solomon codes. That’s usually as good as it gets in crypto, and only time will tell whether Twisted Reed-Solomon codes end up being broken.

Paper on record-breaking decoding

Johan S. R. Nielsen No Comments

Johan Rosenkilde with coauthors Sven Puchinger and Irene Bouw of Ulm University just submitted the paper

    “Improved Power Decoding of Interleaved One-Point Hermitian Codes”

to the journal Designs, Codes and Cryptography

Hermitian codes are the prime example of Algebraic Geometry codes, and they have the potential to supersede the widely used Reed-Solomon codes in many applications due to their longer length at comparable decoding capability. “Interleaving” is a technique where a code over a small alphabet is used to build one over a large alphabet; this is especially useful in settings where bursts of errors are common, such as scratches on a CD.

The paper presents a new decoding algorithm for these “Interleaved Hermitian codes”: the new algorithm is able to correct more errors than any previous algorithm for these codes. Further, we demonstrate that this makes Interleaved Hermitian codes the best known codes in terms of decoding capability for a wide range of parameters, where one wishes relatively short codes over large alphabets. The paper also details how to implement the algorithm efficiently, achieving the rare sub-quadratic complexity in the code length.

The paper draws its techniques from three previous papers:

  • “Improved Power Decoding of One-Point Hermitian Codes”, by the same authors, WCC 2017.
  • “Decoding of Interleaved Reed–Solomon Codes Using Improved Power Decoding”, by Sven Puchinger and Johan Rosenkilde, ISIT 2017.
  • “Power Decoding Reed–Solomon Codes Up to the Johnson Radius” by Johan Rosenkilde, submitted to Advances in Mathematics of Communications.

All four papers can be found on Johan’s web page