Attacking and Defending Code-based Cryptosystems

Today, cryptographic applications are used in nearly all areas of our lives, including the economy, health, military, and entertainment. Without them, society would change in ways we can hardly imagine. Since the publication of Shor's algorithm in 1994, however, we know that those cryptographic applications based on the problems of factoring and discrete logarithm are threatened by quantum computer attacks. Most current applications belong to this category. Code-based cryptography is conjectured to be secure against quantum computer attacks, and it has several other advantages. Firstly, it exhibits advanced security properties: for example, binary Goppa codes are considered a secure choice for many schemes, and the McEliece encryption scheme has not been broken in over 30 years since its publication (merely an adjustment of the parameters was necessary). Secondly, since code-based cryptosystems are based on linear algebra instead of, for example, arithmetic using floating-point numbers, they are usually very fast and can be implemented on devices with a low computing power and without cryptographic co-processor. Finally, the complexity of attacks against code-based schemes can usually be estimated accurately in the expected number of binary operations instead of relying on the asymptotic O-notation. This allows a precise computation of the security level a scheme provides. The major drawback of most code-based schemes is their large key size. This thesis contributes to two important aspects in the development of cryptographic applications. The first concerns the use of secure cryptographic primitives. While schemes like the McEliece and Niederreiter encryption schemes have been studied for a long time and are considered secure, new schemes or variants of existing ones are constantly being developed. The objectives are to decrease the key size, create schemes with new properties, or to introduce other improvements. In order to assess the security of these schemes, they have to be subjected to all relevant attacks. We contribute to this aspect by introducing a new type of attack, a broadcast attack, and by improving and generalizing existing attacks. Secondly, once a secure primitive has been found, appropriate code parameters have to be selected. This choice needs to reflect several constraints. Most importantly, the parameters have to provide a sufficient security level. Other constraints concern different aspects of efficiency, e.g. encryption or decryption time, required bandwidth, memory size etc. Our contribution is the selection of optimal parameters for the McEliece cryptosystem and the QD-CFS signature scheme by applying Lenstra and Verheul's framework