About qTESLA
qTESLA is a family of provably-secure post-quantum signature schemes based on the hardness of the decisional Ring Learning With Errors (R-LWE) problem. The scheme is an efficient variant of the Bai-Galbraith signature scheme —which in turn is based on the “Fiat-Shamir with Aborts” framework by Lyubashevsky— adapted to the setting of ideal lattices. Concretely, qTESLA includes the following parameter sets:| (1) qTESLA-p-I: NIST’s security category 1. | |
| (2) qTESLA-p-III: NIST’s security category 3. |
qTESLA was submitted to the NIST PQC standardization process and made it to the second round. In July 2020, it was announced that qTESLA is not advancing to the third round. Highlights
Simplicity.qTESLA is simple and easy to implement, and its design makes possible the realization of compact and portable implementations that achieve high performance. In addition, the use of a simplified Gaussian sampler is limited to key generation.
Security foundation.
The underlying security of qTESLA is based on the hardness of the decisional R-LWE problem, and comes accompanied by a tight security reduction in the (quantum) random oracle model.
Practical security.
By design, qTESLA facilitates secure implementations. In par- ticular, it supports constant-time implementations (i.e., implementations that are secure against timing and cache side-channel attacks since their execution time does not depend on secret values), and is inherently protected against certain simple yet powerful fault attacks.
Scalability and portability.
qTESLA’s simple design makes it straightforward to easily support more than one security level and parameter set with a single, efficient portable implementation.
Specification
The detailed description of the qTESLA specifications can be downloaded below:qTESLA specification (PDF)
The signature scheme is also described in the following preprint that is available in the IACR eprint archive:
qTESLA preprint
Code
The reference implementation of qTESLA can be found on GitHub:qTESLA code (GitHub)
The entire submission package be downloaded below:
qTESLA submission package
Additionally, qTESLA is integrated in the cryptographic libraries BouncyCastle and liboqs. The respective implementations can be found on GitHub:
qTESLA in BouncyCastle qTESLA in liboqs
Moreover, there exists a hardware-software co-design using RISC-V. In particular, this work demonstrates that qTESLA achieves over a 40-100x speedup for key generation, about a 10x speedup for signing, and about a 16x speedup for verification, compared to the baseline RISC-V software-only implementation. (Parameterized Hardware Accelerators for Lattice-Based Cryptography and Their Application to the HW/SW Co-Design of qTESLA. Wen Wang and Shanquan Tian and Bernhard Jungk and Nina Bindel and Patrick Longa and Jakub Szefer. Cryptology ePrint Archive: Report 2020/054)
eprint report 2020/054 HW/SW co-design (GitHub)
Performance
The table below displays the median performance (in thousands of cycles) of the reference implementation of qTESLA on a 3.40 Intel Core i7-6700 (Skylake) processor. Cycle counts are rounded to the nearest 100 cycles.| Scheme | keygen | sign | verify | total (sign+verify) |
| qTESLA-p-I | 2, 358.6 | 2, 299.0 | 814.3 | 3, 113.3 |
| qTESLA-p-III | 13, 151.4 | 5, 212.3 | 2,102.3 | 7, 314.6 |
| Scheme | keygen | sign | verify | total (sign+verify) |
| qTESLA-p-I | 2, 212.4 | 1, 370.4 | 678.4 | 2, 048.8 |
| qTESLA-p-III | 12, 791.0 | 3, 081.9 | 1, 745.3 | 4, 827.2 |
| Scheme | secret key | public key | signature |
| qTESLA-p-I | 5, 224 | 14, 880 | 2, 592 |
| qTESLA-p-III | 12, 392 | 38, 432 | 5, 664 |
Team
The qTESLA team consists of the following researchers from academia and industry (listed in alphabetical order):| Sedat Akleylek | Ondokuz Mayis University, Turkey |
| Erdem Alkim | Ondokuz Mayis University, Turkey and Fraunhofer SIT, Germany |
| Paulo S. L. M. Barreto | University of Washington Tacoma, USA |
| Nina Bindel | University of Waterloo, Canada |
| Johannes Buchmann | Technische Universität Darmstadt, Germany |
| Edward Eaton | ISARA Corporation and University of Waterloo, Canada |
| Gus Gutoski | ISARA Corporation, Canada |
| Juliane Krämer | Technische Universität Darmstadt, Germany |
| Patrick Longa | Microsoft Research, USA |
| Harun Polat | Technische Universität Darmstadt, Germany |
| Jefferson E. Ricardini | LG Electronics, USA |
| Gustavo Zanon | University of São Paulo, Brazil |