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.
Decoding of AG codes boils down to solving a Padé approximation on the algebraic curve. Current techniques throw away many levels of structure, leaving a problem on univariate polynomials. We will seek algorithms that retain these levels, and we will build on the latest developments in computer algebra. We expect improvements for both the simplest as well as more complex AG codes.
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:
- 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.
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.
The Algebra group was visited 30th October till 10th November by PhD student David Lucas from University of Grenoble-Alpes in France. David Lucas is looking at non-cryptographic solutions for security issues with cloud computing, and during the visit worked with Johan Rosenkilde on certificates for linear algebraic computations: a cloud service computes e.g. the determinant of a large matrix for your constrained device, and you wish to be sure (or very confident) that the answer is correct. By letting the cloud server compute a little bit more, clever protocols allows you to prove that the answer is correct without having to recompute it yourself.
The visit was funded by DTU and the IFD Science research project “Correcting the Cloud”, granted to Johan Rosenkilde and David’s superviser Clément Pernet.
In a new preprint Peter Beelen and guest Ph.D. Maria Montanucci describe a new family of maximal curves. Maximal curves are algebraic curves defined over a finite field, having as many rational points as allowed by the famous Hasse-Weil bound. Such curves are of great interest by themselves, but are also the most obvious curves to choose when constructing algebraic-geometry (AG) codes.
Note that the depicted curves don’t have anything to do with the new maximal curves. The new curves are over a finite field and are therefore difficult to meaningfully depict graphically.
The paper “Two-Point Codes for the Generalized GK curve” is accepted for publication in the prestigious IEEE Transactions of Information Theory. The paper investigates a recently discovered family of maximal curves and details how techniques developed by Peter Beelen can be used to find record-breaking error-correcting codes with these curves.
The paper was very much a group effort: all four permanent members of the group as well as guest PhD student Élise Barelli featured as authors. The research started as part of our study group but quickly led to these new results.