Curves, Codes, and Cryptography

Elliptic curves and error-correcting codes are the mathematical objects investigated in this thesis for cryptographic applications. The main focus lies on public-key cryptography but also a code-based hash function is investigated. Public-key cryptography was invented by Diffie and Hellman [DH76] in 1976 with the goal to remove the need for in-person meetings or trusted couriers to exchange secret keys. While symmetric cryptography uses the same key for encryption and decryption, publickey cryptography uses a key pair consisting of a public key used for encryption and a private key used for decryption. In order to generate lots of possible key pairs mathematical one-way functions are used —functions which are easy to compute but hard to invert. In practice a sender can efficiently compute a ciphertext given the public key, but only the holder of the private key can use the hidden information for decryption. Parameters for public-key cryptography need to be chosen in a way that encryption and decryption can be carried out very fast. Simultaneously, those parameters have to guarantee that it is computationally infeasible to retrieve the original message from the ciphertext, or even worse, the private key from the public key. Parameters for cryptography are chosen to provide b-bit security against the best attack known. This means that given the public key and public system parameters it takes at least 2b bit operations to retrieve the original message from a given ciphertext; or in the context of the hash function that it takes at least 2b bit operations to find a collision. The encryption and decryption algorithms in this thesis are mostly text-book versions. Understanding the underlying mathematical problems and structures is a fundamental object of this thesis. This thesis does not investigate protocols trying to provide security against malicious attackers who exploit (partial) knowledge on e.g., ciphertexts or private keys. Those protocols can be added as another layer to strengthen the security of the schemes investigated here.