12
Jan
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 ReedSolomon codes were introduced by the same authors at last year’s ISIT. They are a family of “mutilated” ReedSolomon 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 ReedSolomon 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 publickey cryptography! The classical McEliece Cryptosystem is a methodology for turning any family of codes, for which one knows a good decoding algorithm, into a publickey 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 drawbacks:
 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, ReedSolomon 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 ReedSolomon 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 ReedSolomon vulnerable do not apply to Twisted ReedSolomon codes. That’s usually as good as it gets in crypto, and only time will tell whether Twisted ReedSolomon codes end up being broken.
22
Dec
Johan Rosenkilde with coauthors Sven Puchinger and Irene Bouw of Ulm University just submitted the paper
“Improved Power Decoding of Interleaved OnePoint 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 ReedSolomon 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 subquadratic complexity in the code length.
The paper draws its techniques from three previous papers:
 “Improved Power Decoding of OnePoint 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
13
Nov
The Algebra group was visited 30th October till 10th November by PhD student David Lucas from University of GrenobleAlpes in France. David Lucas is looking at noncryptographic 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.
3
Oct
The paper “TwoPoint 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 recordbreaking errorcorrecting 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.
8
Feb
The Algebra group at DTU just submitted 3 papers to the prestigious conference International Symposium in Symbolic and Algebraic Computation 2017.
The papers were:
 Fast computation of the roots of polynomials over the ring of power series, Vincent Neiger, Johan Rosenkilde, Éric Schost.

Popov Form Computation for Matrices of Ore Polynomials, Mohamed Khochtali, Johan Rosenkilde, Arne Storjohann.

Computing canonical bases of modules of univariate relations, Thi Xuan Vu, Vincent Neiger
The papers are now undergoing review, and we will get news about acceptance or not by midApril.
25
Jan
The Algebra group at DTU has just submitted 2 papers to the prestigious International Symposium in Information Theory 2017 conference, held in June this year. The papers are:
The papers are now undergoing review, and we will get news about acceptance or not by the end of March.
26
Aug
Johan coorganised and participated in Sage Days 75 on Algorithmic Coding Theory, taking place 2226 August 2016 at Inria in Saclay, France. The workshop was attended by 3540 SageMath enthusiasts, many of who made their first contributions to SageMath at the workshop.
The workshop served as the Grande Finale of the ACTIS project which Johan was part of. The project employed David Lucas as fulltime software developer for two years for improving the Coding Theory support in SageMath.
12
Aug
812 August 2016, Johan participated in a seminar “Coding Theory in the time of Big Data” at the beautiful Schloss Dagstuhl. As is common at Dagstuhl, the seminar had only few talks, leaving ample time for discussion and collaboration on the seminar’s topic. Johan worked mostly on finding new good rankmetric codes and on private information retrieval schemes. He also gave a short talk on Coding Theory in SageMath and the upcoming SageDays 75 on Coding Theory.
22
Jul
Johan presented 22nd July the paper “Algorithms for Simultaneous Padé Approximations”, coauthored with Arne Storjohann at the conference ISSAC 2016, held at Wilfred Laurier University, Waterloo, Canada.
18
Jul
Johan participated in MICA 2016 in Waterloo, Canada, a workshop on computer algebra held in honor of Erich Kaltofen. Erich has many contributions to computer algebra, for example in fast linear algebra, polynomial multiplication, polynomial factorization, and sparse interpolation. These and other topics were covered during the conference.