Code-based cryptography is not widely deployed in practice. Mostly due to its important drawback: huge key sizes. In this thesis, we propose two different approaches to address this issue. The first one uses algebraic codes, presenting a way to construct Goppa codes that admit compact representation. These are the p-adic Goppa codes. We show how to construct these codes to instantiate public-key encryption schemes, how to extend this approach to a signature scheme and, finally, how to generalize the approach to codes defined over characteristic greater or equal to two. In summary, we managed to produce very compact keys based on the reputable family of Goppa codes. Although efficient, p-adic Goppa codes have a non-desirable property: strong algebraic structure. This leads to our second approach, using LDPC codes of increased density, or simply MDPC codes. These are graph-based codes, which are free of algebraic structure. It is quite reasonable to assume that MPDC codes are only distinguishable by finding their dual low-weight codewords. This is an important advantage not only in comparison to all previous compact-keys McEliece-like variants but also regarding the classical McEliece based on binary Goppa codes. Here, compact keys are obtained by using a quasi-cyclic structure.
Two Approaches for Achieving Efficient Code-Based Cryptosystems