Paper 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.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- Post-quantum cryptographylattice-based cryptographydigital signaturesprovable securityefficient implementationGaussian sampling.
- Contact author(s)
- plonga @ microsoft com,nbindel @ cdc informatik tu-darmstadt de
- History
- 2020-04-24: last of 4 revisions
- 2019-01-28: received
- See all versions
- Short URL
- https://ia.cr/2019/085
- License
-
CC BY