A New LDPC-based McEliece Cryptosystem

Pedro de Melo Branco

Key information

Authors:

Pedro de Melo Branco (Pedro de Melo Branco)

Supervisors:

Paulo Alexandre Carreira Mateus (Paulo Alexandre Carreira Mateus)

Published in

12/15/2017

Abstract

The McEliece cryptosystem was first presented by Robert McEliece and it is one of the oldest public-key cryptosystem that remains unbreakable. Its simplicity and its efficiency makes it a very interesting candidate for the post-quantum era since it is conjectured to be secure against a quantum computer. In this thesis, we analyze the McEliece cryptosystem. We will go throughout its pros and cons and its foundations. Also, we present some basic concepts of coding theory in order to fully understand the McEliece cryptosystem. Also, we propose an efficient McEliece-based cryptosystem to handle large messages and that can be easily implemented in hardware. To achieve that, we will use LDPC codes in the McEliece cryptosystem taking advantage of their capacity to handle large blocks of messages. The cryptosystem proposed is conjectured to be robust to quantum attacks since it relies its security of the McEliece cryptosystem. Moreover, we prove that this cryptosystem is at least as hard to break as the McEliece. We were capable of reducing significantly the key size of the cryptosystem, one of its major problems and the principal reason why it is not used in the real world. We also analyze its efficiency and propose an IND-CCA2 secure variant under some hard assumptions.