The Lattice-Based Digital Signature Scheme qTESLA

Alkim E., Barreto P. S. L. M., Bindel N., Kraemer J., Longa P., Ricardini J. E.

18th International Conference on Applied Cryptography and Network Security (ACNS), ELECTR NETWORK, 19 - 22 October 2020, vol.12146, pp.441-460 identifier identifier

  • Publication Type: Conference Paper / Full Text
  • Volume: 12146
  • Doi Number: 10.1007/978-3-030-57808-4_22
  • Country: ELECTR NETWORK
  • Page Numbers: pp.441-460
  • Keywords: Post-quantum cryptography, Lattice-based cryptography, Digital signatures, Provable security, Efficient implementation, SECURITY
  • Ondokuz Mayıs University Affiliated: Yes

Abstract

We present qTESLA, a post-quantum provably-secure digital signature scheme that exhibits several attractive features such as simplicity, strong security guarantees against quantum adversaries, and builtin 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 consisting of only about 300 lines of C code, which showcases the code compactness of the scheme. Our results also demonstrate that a conservative, provably-secure signature scheme can be efficient and practical, even with a compact and portable implementation. For instance, our C-only implementation executes signing and verification in approximately 0.9 ms on an x64 Intel processor using the proposed level 1 parameter set. Finally, we also provide AVX2-optimized assembly implementations that achieve an additional factor-1.5 speedup.