Non-binary information set decoding and an attack on BCH-McEliece: A tale of two approaches to code-based cryptanalysis

Code-based cryptosystems are a well-established and promising direction in post-quantum cryptography. Their security rests on the presumed difficulty of solving certain fundamental computational problems in the theory of error-correcting codes. This thesis enhances the security analysis of these systems through two different approaches.

First, we adapt and refine an existing algebraic cryptanalytic method to attack a McEliece-like cryptosystem based on permuted BCH codes. We show experimentally that our attack outperforms the best-known generic approaches for certain high-rate codes over non-prime fields.

Second, we investigate Information Set Decoding (ISD) with the aim of advancing the state of the art for non-binary fields. We begin by addressing the open question of whether decoding over an extension field is fundamentally easier than decoding over a prime field of comparable size. Analyzing several techniques aiming at translating the problem to a subfield – including the expansion map, subfield subcodes, and the trace map – we find no evidence of an asymptotic advantage. We then introduce a novel framework for non-binary ISD that decouples the search for error positions from the determination of their values. This framework yields two new algorithms: the fastest known memory-less ISD algorithm and a competitive meet-in-the-middle variant. Finally, we explore the nearest-neighbor paradigm for ISD, proposing a practical algorithm based on error-correcting codes. This algorithm achieves the same asymptotic complexity as the May–Ozerov method while delivering concrete performance improvements for realistic parameters.