Applied Algebra Group at the University of Zürich


Twisted Codes and Their Applications in Cryptography

Dr. Sven Puchinger's talk
Date: 24.10.18   Time: 16.00 - 17.00   Room: Y27H12

Inspired by a recent rank-metric code construction by Sheekey, called twisted Gabidulin codes, we present a new code class in Hamming metric: Twisted Reed-Solomon codes. The class contains many maximum distance separable codes that are inequivalent to Reed-Solomon codes. We study the duals and Schur squares of the new codes and propose a list decoder that is efficient for some parameters. As an application, we show that there is a subclass of twisted Reed-Solomon codes resisting several known structural attacks on the McEliece code-based cryptosystem. Furthermore, we propose a generalization of Sheekey's twisted Gabidulin codes in the rank metric, using similar methods as for twisted Reed-Solomon codes. The new code class contains many maximum rank distance codes that are inequivalent to both Gabidulin codes and the original twisted Gabidulin codes. We show that Overbeck's attack on the rank-metric-analog of the McEliece system, the GPT cryptosystem, is not feasible for a large subfamily of twisted Gabidulin codes.