Code-Based Digital Signature Schemes: Construction, Cryptanalysis and Theoretical Foundations

In recent decades, numerous code-based digital signature schemes following the hash&sign paradigm have been proposed, often turning out to be insecure and demonstrating that the cryptographic community still seems far from a satisfactory solution in this area. The first major question we pose in this thesis is whether it is possible to construct, in this regard, a signature scheme that enjoys a solid security reduction and is also efficient. We discuss a proposal that combines some new ideas, but we anticipate that it suffered a severe attack two years ago, making it unusable. The second question we pose is the possibility to say something about the security of other schemes. According to this, we leave the constructive side and explore the cryptanalytic one, analyzing HWQCS. We break its security assumptions and violate the EUF-CMA security. Other than by following the hash&sign paradigm, an alternative approach to obtain digital signatures is to rely on interactive protocols, making them non-interactive using the Fiat-Shamir transform. Recently, numerous optimizations to the basic paradigm have been introduced, including the well-known fixed-weight optimization. Although this technique is widely used, its underlying security assumptions are still not well understood, and the formal security of these schemes has not yet been proven. With the intention of laying a first brick in this direction, we prove that the underlying interactive protocol still enjoys knowledge soundness. These are the main questions targeted by this thesis, forming the fil rouge that guides the narrative. In the process of addressing them, several secondary questions will naturally arise, which will be described and explored throughout the discussion.