The Lattice-Based Digital Signature Scheme qTESLA
18th International Conference on Applied Cryptography and Network Security (ACNS), ELECTR NETWORK, 19 - 22 October 2020, vol.12146, pp.441-460, (Full Text)
- 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.