Post-quantum signatures for today

Digital signatures are essential for the security of computer networks such as the Internet. For example, digital signatures are widely used to ensure the authenticity and integrity of updates for operating systems and other software applications. The security of the few practically used signature schemes is threatened by quantum computers. When large quantum computers are built, all currently used signature schemes will become insecure. It is therefore of extreme importance to develop alternative signature schemes that remain secure in the presence of quantum computers and which are able to compete with currently used signature schemes. A very promising candidate for a signature scheme that withstands quantum computer attacks is the Merkle signature scheme invented by Merkle in 1979. However, even combined with the improvements by Szydlo and Coronado, the Merkle signature scheme has certain efficiency drawbacks that keep it from being truly practical. First of all, it has highly unbalanced signature generation times. In the worst case, signature generation takes significantly longer than on average. Secondly, the Merkle--Szydlo--Coronado signature scheme produces very large signatures. It is also unclear if Merkle's signature scheme is suitable for application on resource constrained devices. The generalized Merkle signature scheme (GMSS) presented in this thesis solves the problems mentioned above. It drastically reduces the worst case signature generation time of the Merkle--Szydlo--Coronado signature scheme. The worst case signature generation time of GMSS corresponds to the average case signature generation time of the Merkle--Szydlo--Coronado signature scheme. Further, the worst case signature generation time of GMSS is extremely close to its average case signature generation time and thus, GMSS provides balanced timings for the signature generation. GMSS exploits the improved signature generation times to provide a noticeable reduction of the signature sizes while maintaining timings that are highly competitive to currently used signature schemes. A proof-of-concept implementation shows that GMSS can also be used on resource constrained devices and excellently compares to currently used signature schemes. This thesis also introduces a new construction method for Merkle signatures. This construction is provably secure under weaker security assumptions and yields a signature scheme with a significantly higher security level compared to the original construction.