qTESLA

qTESLA

 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
The table below displays the median performance (in thousands of cycles) of the AVX2 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, 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
The table below displays the public key and signature sizes of the proposed qTESLA instantiations are as follows. Sizes are given in bytes.  
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
You can contact the qTESLA team via info@qtesla.org.      Contact qTESLA team