Cryptology ePrint Archive: Report 2019/085

The Lattice-Based Digital Signature Scheme qTESLA

Erdem Alkim and Paulo S. L. M. Barreto and Nina Bindel and Juliane Kramer and Patrick Longa and Jefferson E. Ricardini

Abstract: We present qTESLA, a family of post-quantum digital signature schemes that exhibits several attractive features such as simplicity and strong security guarantees against quantum adversaries, and built-in protection against certain side-channel and fault attacks. qTESLA---selected for round 2 of NIST's post-quantum cryptography standardization project---consolidates a series of recent schemes originating in works by Lyubashevsky, and Bai and Galbraith. We provide full-fledged, constant-time portable C implementations that showcase the code compactness of the proposed scheme, e.g., our code requires only about 300 lines of C code. Finally, we also provide AVX2-optimized assembly implementations that achieve a factor-1.5 speedup.

Category / Keywords: public-key cryptography / Post-quantum cryptography, lattice-based cryptography, digital signatures, provable security, efficient implementation.

Original Publication (with major differences): ACNS 2020

Date: received 25 Jan 2019, last revised 24 Apr 2020

Contact author: nlbindel at uwaterloo ca, plonga at microsoft com

Available format(s): PDF | BibTeX Citation

Note: This version does not contain heuristic parameter sets, which were removed due to security reasons. The paper includes portable C and AVX2-optimized implementations of provably-secure parameter sets, and a countermeasure to protect against key substitution (KS) attacks, which improves security in the multi-user setting.

Version: 20200424:173343 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]