The lattice-based signature scheme TESLA and variants
On this website research papers and projects about the (ideal-) lattice-based signature schemes TESLA and ring-TESLA are collected.
- The original construction is proposed in “An improved compression technique for signatures based on learning with errors” by Shi Bai and Steven D. Galbraith (CT-RSA 2014).
- Improvements of the Bai-Galbraith-scheme are made in “High-speed signatures from standard lattices” by Özgür Dagdelen, Rachid El Bansarkhani, Florian Göpfert, Tim Güneysu, Tobias Oder, Thomas Pöppelmann, Ana Helena Sanchez, Peter Schwabe (LatinCrypt 2014).
- Further improvements and a tight security reduction was proposed in an earlier version by Erdem Alkim, Nina Bindel, Johannes Buchmann, Özgür Dagdelen, Peter Schwabe. Its ideal-lattice-based version ring-TESLA is prosed in “An efficient lattice-based signature scheme with provably secure instantiation” by Sedat Akleylek, Nina Bindel, Johannes Buchmann, Juliane Krämer, Giorgia Azzurra Marson (AfricaCrypt 2016).
- Moreover, a version of the scheme ring-TESLA called TESLA# by Barreto, Longa, Naehrig, Ricardini, and Zanon included several implementation improvements.
- In November 2016 Gus Gutoski and Christopher Peikert independently informed us about a flaw in the security reductions presented in the papers corresponding to the schemes TESLA (and its ideal-lattice-based version ring-TESLA and TESLA#). The flaw does not lead to any actual attack against the two schemes. Moreover, the (non-tight) reduction proposed by Bai and Galbraith is not affected.
- In May 2017 Erdem Alkim, Nina Bindel, Johannes Buchmann, Özgür Dagdelen, Edward Eaton, Gus Gutoski, Juliane Krämer, and Filip Pawlega presented a new (tight) security reduction in the quantum oracle model in “Revisiting TESLA in the quantum random oracle model” (PQCrypto 2017). However, ring-TESLA and its proposed parameters are still not supported by any formal security argument.
- In their gitHub Shay Gueron and Fabian Schlieker improve the performance of ring-TESLA.
- The signature scheme ring-TESLA (and others) was analyzed with respect to fault attacks: “Lattice-Based Signature Schemes and their Sensitivity to Fault Attacks” by Nina Bindel, Johannes Buchmann, and Juliane Krämer (FDTC 2016).
- The signature scheme ring-TESLA was analyzed with respect to cach side channels: “Bounding the cache-side-channel leakage of lattice-based signature schemes using program semantics” by Nina Bindel, Johannes Buchmann, Juliane Krämer, Heiko Mantel, Johannes Schickel, and Alexandra Weber (FPS 2017)
The signature scheme “qTESLA” assembles the advantages acquired in the prior works. It was submitted to NIST's call for post-quantum submission in November 2017.
The scheme qTESLA is a post-quantum signature scheme based on the hardness of the decisional ring learning with errors (R-LWE) problem. In contrast to other alternatives, qTESLA is a conservative yet efficient signature scheme that has been instantiated according to the provided security reduction. That is, qTESLA instantiations are provably secure in the (quantum) random oracle model. To this end, the scheme comes accompanied by a non-tight reduction in the random oracle model, and a tight reduction in the quantum random oracle model from R-LWE. qTESLA achieves good performance with a competitive memory footprint. Furthermore, design decisions have been made towards enabling simple, easy-to-protect implementations. The submission to NIST can be found here.