Practical Lattice-based Digital Signature Schemes

James Howe, Thomas Pöppelmann, Maire O'Neill, Elizabeth O'Sullivan, Tim Güneysu

ACM Transaction on Embedded Computing, Volume 14 Issue 3, Article No. 41, May 2015


Digital signatures are an important primitive for building secure systems and are used in most real world security protocols. However, almost all popular signature schemes are either based on the factoring assumption (RSA) or the hardness of the discrete logarithm problem (DSA/ECDSA). In the case of classical cryptanalytic advances or progress on the development of quantum computers the hardness of these closely related problems might be seriously weakened. A potential alternative approach is the construction of signature schemes based on the hardness of certain lattices problems which are assumed to be intractable by quantum computers. Due to significant research advancements in recent years, lattice-based schemes have now become practical and appear to be a very viable alternative to number-theoretic cryptography. In this paper we focus on recent developments and the current state-of-the-art in lattice-based digital signatures and provide a comprehensive survey discussing signature schemes with respect to practicality. Additionally, we discuss future research areas that are essential for the continued development of lattice-based cryptography.

An extended abstract of this work was presented at the NIST Workshop on Cybersecurity in a Post-Quantum World 2015.

[NIST Workshop] [Extended Abstract] [Presentation NIST ] [PDF]