Security Considerations for McEliece-like Cryptosystems Based on Linearized Reed-Solomon Codes in the Sum-Rank Metric

Abstract

In the advent of more and more powerful quantum computers, it is crucial to develop cryptosystems that remain secure against adversaries with access to quantum-computing resources. McEliece proposed a public-key cryptosystem based on algebraic codes and hence initiated the field of code-based cryptography in his seminal work [5] in 1978. Since then, code-based schemes have been and still are believed to be strong candidates for post-quantum cryptography due to their longtime resistance to cryptanalysis. The main idea is to choose a generator matrix of a secret code and to disguise its structure by applying isometric transformations such that an adversary cannot derive the known efficient decoder from the mere knowledge of the scrambled matrix. Messages are then transmitted as codewords affected by randomly chosen errors of reasonable weight.

Instances of the McEliece cryptosystem based on a variety of code families in the Hamming and the rank metric were proposed over time. As the sum-rank metric was established and found to generalize both Hamming and rank metric in recent years, the question whether a McEliece-like cryptosystem based on sum-rank-metric codes can ensure secure communication arises naturally. Generic decoding of sum-rank-metric codes was addressed in [8] and linearized Reed-Solomon (LRS) codes being the sum-rank analogs of Reed-Solomon (RS) and Gabidulin codes were introduced in [3]. The next step is the investigation and cryptanalysis of McEliece-like cryptosystems using LRS codes. We show that, similar to RS and Gabidulin codes, these codes are vulnerable to a polynomial-time key-recovery attack as long as only isometric transformations are used to disguise the secret generator matrix.