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 Patrick Longa and Jefferson E. Ricardini

Abstract: We present qTESLA, a family of post-quantum digital signature schemes based on the ring learning with errors (R-LWE) problem that exhibits several attractive features such as simplicity, high-performance, strong security guarantees against quantum adversaries, and built-in protection against certain side-channel and fault attacks. qTESLA, selected for the first round of NIST's post-quantum cryptography standardization project, consolidates a series of recent proposals of R-LWE-based signature schemes originating in works by Lyubashevsky, and Bai and Galbraith, leading to the best performance among lattice-based signature schemes instantiated against state-of-the-art quantum attacks and implemented with protection against timing and cache side-channels. We provide full-fledged, constant-time reference and AVX2-optimized implementations that showcase the high-speed and simplicity of our scheme. As part of our implementations, we present an efficient and portable Gaussian sampler that gets by without using floating-point operations and is easily implementable in constant-time. While the Gaussian sampling is solely used in qTESLA's key generation, variants of it are used in most lattice-based primitives and, hence, our approach is of independent interest for other lattice-based implementations.

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

Date: received 25 Jan 2019

Contact author: plonga at microsoft com,nbindel@cdc informatik tu-darmstadt de

Available format(s): PDF | BibTeX Citation

Version: 20190128:164048 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]