What’s New

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!

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

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. 

Danmarks Frie Forskningsfond (Independent Research Fund Denmark) each year supports many prestigious research projects. They have just announced that they will support a research project of the algebra group. This grant will enable us to hire a Ph.D. student as well as to visit and invite researchers from all over the world. We are very grateful for the support!

A brief summary of the research project is the following:

Error-correcting codes ensure reliability in e.g. satellite communication, distributed storage and cloud computing. It is vital that the error-correction can be done fast. Excellent error-correcting codes can be constructed using algebraic curves – AG codes – but no fast decoding algorithms are available for these codes. This has limited their theoretical impact and prohibited any practical impact. This project aims to change that.

The project will be carried out by the algebra group at DTU and international collaborators from France and Canada.

From April 15 til May 8, Prof. Masaaki Homma from Kanagawa University visits the algebra group. He will work with Peter Beelen and Mrinmoy Datta on problems related to the intersection of a Hermitian surface and a surface of degree d. The aim is to solve a conjecture posed by a Danish Ph.D. student A.B. Sørensen in 1991. For d=1 and d=2 the conjecture is known to be true, while Peter and Mrinmoy recently made significant progress for d=3, see this previous post. For d>3 nothing is known as yet, but this may change soon!

As announced in a previous post, Peter Beelen and guest Ph.D. Maria Montanucci recently solved a conjecture on the structure of Weierstrass semigroups of points on the Giulietti-Korchmaros maximal curve. These results have now appeared in the journal Finite Fields and Their Applications. Click here to see the article.

Peter Beelen and Mrinmoy Datta have just submitted an article in which a conjecture from 1991 by Sørensen is partially resolved. In this conjecture a formula for the minimum distance of q^2-ary codes constructed from Hermitian surfaces is given. Equivalently, the conjecture gives a formula for the maximal number of GF(q^2)-rational points that a Hermitian surface and a hypersurface of degree d>1 can have. For d=2, the conjecture was solved in 2007 by Edoukou, but since then no progress has been made until now. We show that the conjecture is correct for d=3 as long as q>7. A preprint can be found here.

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.

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

The article Counting Generalized Reed-Solomon Codes by Peter Beelen, David Glynn, Tom Høholdt and Krishna Kaipa has just appeared in the journal Advances in Mathematics of Communication, volume 11, issue 4, pages 777-790, doi: 10.3934/amc.2017057. The work started by a question of the fourth author posed at a conference in India in 2013 and grew out to a nice journal article in the years after. You can see an updated preprint of the article here.