Public Key Cryptography based on Coding Theory
Raphael Overbeck · Technischen Universität Darmstadt · 2008
In this thesis we view the statistical decoding algorithm, which tries to solve the general decoding problem as well as the variants of the McEliece cryptosystem based on Gabidulin codes. The first part of the thesis is dedicated to the general concept of public key cryptography on the basis of coding theory and the security of the underlying problems. Thus after presenting the basic principles, we study the proposal of statistical decoding (which can be seen as a variant of iterative decoding). For a given code, the statistical decoding algorithm precomputes many low weight check vectors and is afterwards able to correct a certain fraction of erroneous codewords in constant time. This can be a great advantage if there are many erroneous messages to decode. Unfortunately, in the original paper an analysis of the precomputation phase is not included and in experiments given bounds for the space complexity of the statistical decoding algorithm turned out to be too optimistic. We give a robust space complexity analysis of the proposed algorithm and deduce new theoretical bounds. In experiments, these new bounds proof to be more accurate than the previous ones, corroborating some simplifying assumptions in our analysis. Further, we analyze the time complexity of the precomputation phase and draw the conclusion that it is much higher than estimated. A main flaw of the initial algorithm is the fact that most of the information obtained during the precomputation phase is discarded. We improve the statistical decoding algorithm by taking more information out of the precomputation. This results in an algorithm with better success probability as the initial one. Nevertheless, even this improved algorithm turns out to be slower than a single run of the Canteaut and Chabaud algorithm. We thus conclude that for the McEliece PKC the parameter sets currently proposed remain secure. However, following our approach, further improvement of the statistical algorithm seems to be possible, especially if one could achieve a significant speed-up of the precomputation. Further, the presented methods could be combined with the iterative decoding approach. Therefore, the question if there are better attacks on the McEliece cryptosystem than the existing ones remains open. The second part of the thesis is dedicated to Gabidulin codes and their application to cryptography like in the GPT proposal from EuroCrypt'91 and its variants. Gabidulin codes use \textnormal{rank distance} instead of hamming distance and thus can be used to correct pattern errors in communication channels. We present a new error correction algorithm for Gabidulin codes, which can be extended to interleaved Gabidulin codes. We show that this extension allows to correct errors in rank metric up to the amount of redundancy in a large number of cases, which is far beyond the initial error correction bound. Consequently our result is analogous to the one of Bleichenbacher, Kiayias and Yung for GRS codes. The question whether Gabidulin codes can be used for cryptographic applications was strongly discussed in the last years, but remained unsolved. The GTP proposal by Gabidulin, Paramonov and Tretjakov is promising, as the general decoding problem in rank metric is more difficult than in hamming metric. Thus, this variant offers more resistance to general decoding attacks than the McEliece scheme while having a much smaller public key size. However, the GPT cryptosystem was attacked by Gibson in '95 and '96, who showed how to recover the secret key for initial parameter sets. We gather up the sequently proposed strategies to prevent an attacker from recovering the secret key, which are highly interesting as most of them are applicable to all code based cryptosystems and can (but do not necessarily) lead to secure public key cryptosystems. Further, we analyze the effectiveness of these strategies in the case of GPT under two different aspects: The security of the ciphertexts and the security of the secret keys. First, we show how to take profit of our new error correction algorithm for Gabidulin codes, to attack ciphertexts of cryptosystems using Gabidulin codes in polynomial time. In a second part, we show how to identify the structure of the underlying Gabidulin code in the public key and develop a polynomial time key recovery attack.