Paper 2016/030

An Efficient Lattice-Based Signature Scheme with Provably Secure Instantiation

Sedat Akleylek, Nina Bindel, Johannes Buchmann, Juliane Krämer, and Giorgia Azzurra Marson


In view of the expected progress in cryptanalysis it is important to find alternatives for currently used signature schemes such as RSA and ECDSA. The most promising lattice-based signature schemes to replace these schemes are BLISS (CRYPTO 2013) and GLP (CHES 2012). Both come with a security reduction from a lattice problem and have high performance. However, their parameters are not chosen according to their provided security reduction, i.e., the instantiation is not provably secure. In this paper, we present the first lattice-based signature scheme with good performance when provably secure instantiated. To this end, we provide a tight security reduction for the new scheme from the ring learning with errors problem which allows for provably secure and efficient instantiations. We present experimental results obtained from a software implementation of our scheme. They show that our scheme, when provably secure instantiated, performs comparably with BLISS and the GLP scheme.

Note: Warning: In November 2016 Gus Gutoski and Christopher Peikert independently informed us about a flaw in the security reductions presented in the current paper, in report 2015/755, and in report 2016/1026. As far as we can tell, the flaw does not lead to any actual attack against the schemes. Moreover, the (non-tight) reduction proposed by Bai and Galbraith is not affected. Thus, the security of the schemes is not in question. However, the specific instantiations presented in this paper and in report 2015/755 are, currently, not supported by any formal security argument. We are working on a fix and will update the paper as soon as possible.

Available format(s)
Public-key cryptography
Publication info
lattice-based cryptographytightnessideal latticessignaturesring learning with errors
Contact author(s)
nbindel @ cdc informatik tu-darmstadt de
2016-11-17: last of 6 revisions
2016-01-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sedat Akleylek and Nina Bindel and Johannes Buchmann and Juliane Krämer and Giorgia Azzurra Marson},
      title = {An Efficient Lattice-Based Signature Scheme with Provably Secure Instantiation},
      howpublished = {Cryptology ePrint Archive, Paper 2016/030},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.