The Lattice-Based Digital Signature Scheme qTESLA

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

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

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},
      note = {\url{https://eprint.iacr.org/2019/085}},
      url = {https://eprint.iacr.org/2019/085}
}