The Lattice-Based Digital Signature Scheme qTESLA

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

Paper 2019/085

The Lattice-Based Digital Signature Scheme qTESLA

Erdem Alkim, Paulo S. L. M. Barreto, Nina Bindel, Juliane Kramer, 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.

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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Major revision. ACNS 2020
Keywords: Post-quantum cryptography lattice-based cryptography digital signatures provable security efficient implementation.
Contact author(s): nlbindel @ uwaterloo ca
plonga @ microsoft com
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

BibTeX

@misc{cryptoeprint:2019/085,
      author = {Erdem Alkim and Paulo S.  L.  M.  Barreto and Nina Bindel and Juliane Kramer and Patrick Longa and Jefferson E.  Ricardini},
      title = {The Lattice-Based Digital Signature Scheme {qTESLA}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/085},
      year = {2019},
      url = {https://eprint.iacr.org/2019/085}
}