An efficient lattice-based signature scheme with provably secure instantiation

Akleylek S., Bindel N., Buchmann J., Krämer J., Marson G. A.

8th International Conference on the Theory and Application of Cryptographic Techniques in Africa, AFRICACRYPT 2016, Fes, Fas, 13 - 15 Nisan 2016, cilt.9646, ss.44-60 identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Cilt numarası: 9646
  • Doi Numarası: 10.1007/978-3-319-31517-1_3
  • Basıldığı Şehir: Fes
  • Basıldığı Ülke: Fas
  • Sayfa Sayıları: ss.44-60
  • Anahtar Kelimeler: Ideal lattices, Lattice-based cryptography, Ring learning with errors, Signatures, Tightness
  • Ondokuz Mayıs Üniversitesi Adresli: Evet

Özet

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 (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.