Paper 2016/1026

Sharper Ring-LWE Signatures

Paulo S. L. M. Barreto and Patrick Longa and Michael Naehrig and Jefferson E. Ricardini and Gustavo Zanon

Abstract

We present Tesla# (pronounced "Tesla Sharp"), a digital signature scheme based on the RLWE assumption that continues a recent line of proposals of lattice-based digital signature schemes originating in work by Lyubashevsky as well as by Bai and Galbraith. It improves upon all of its predecessors in that it attains much faster key pair generation, signing, and verification, outperforming most (conventional or lattice-based) signature schemes on modern processors. We propose a selection of concrete parameter sets, including a high-security instance that aims at achieving post-quantum security. Based on these parameters, we present a full-fledged software implementation protected against timing and cache attacks that supports two scheme variants: one providing 128 bits of classical security and another providing 128 bits of post-quantum security.

Note: 2016-11-28: A flaw in the tight security reduction of the original Tesla paper (eprint report 2015/755) has been discovered independently by Gus Gutoski and Christopher Peikert. The mistake carries through to the proof of Ring-TESLA (eprint report 2016/030) and is also present in the proof for TESLA# presented here. Remarks similar to those made by the authors of TESLA and Ring-TESLA apply here in that the flaw does not seem to lead to an attack on these schemes. However, the concrete instantiations presented are currently not backed by a formal security argument.