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.