May 14-17, 2019 | JW Marriott Parq Vancouver, Canada

The post-quantum signature scheme qTESLA and its integration into the TLS protocol (Q11d)

15 May 2019

The post-quantum signature scheme qTESLA and its integration into the TLS protocol (Q11d)

qTESLA is a simple and highly-efficient signature scheme whose security, based on the Ring-Learning With Errors (R-LWE) problem, is conjectured to thwart quantum computer attacks [1][2]. For example, qTESLA signatures matching NIST’s security level 1 can be generated in approximately 115 microseconds on a 3.4GHz 64-bit Intel Skylake processor (found on typical server-class platforms), and in 888 microseconds on a 2.0GHz 32-bit ARM Cortex-A15 processor (found on typical smartphone-class platforms). Notably, these results correspond to a software implementation entirely written in portable C and consisting of only about 300 lines of code [3]. In comparison with Dilithium –another state-of-the-art lattice-based signature scheme—qTESLA is more than 3 times faster (reference implementation) and up to 1.5x faster (AVX2-optimized implementation) on a 64-bit Intel platform. This compactness and efficiency make qTESLA a very promising candidate for providing secure authentication in a post-quantum world.

The first part of this presentation will cover the signature scheme qTESLA, which has been submitted to the NIST post-quantum cryptography standardization process [4], and describe the rationale behind its main design features. A summary of benchmarking results on a variety of platforms will be described.

In the second part, presenters will discuss their experimental evaluation of the integration of qTESLA into the TLS protocol. They integrated qTESLA into the Open Quantum Safe library (liboqs) which in turn has been integrated into OpenSSL 1.1.1. This allowed them to run experiments using qTESLA certificates to protect TLS 1.3 connections, with either a NewHope or an ECDH-NewHope hybrid as the key exchange algorithm. Presenters will also discuss results including “real-life” connections downloading pages of various-sizes, showing “real-life” equivalence between qTESLA and P256-ECDSA, when taking into account average network latency. Finally, they will also present hybrid ciphersuites combining ECDSA and RSA with qTESLA to provide best-of-both-worlds protection incurring minimal protocol overhead, and demonstrating that early deployments of qTESLA are not only possible, but desirable to protect against the looming quantum threat.

[1] qTESLA’s official website:
[2] qTESLA’s specification:
[3] qTESLA’s software submitted to NIST:
[4] qTESLA’s submission package to the NIST’s post-quantum cryptography standardization process: