Paper 2016/1026

Sharper Ring-LWE Signatures

Paulo S. L. M. Barreto, Patrick Longa, Michael Naehrig, 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Post-quantum cryptographydigital signaturesring-LWEimplementation
Contact author(s)
pbarreto @ uw edu
mnaehrig @ microsoft com
History
2016-11-28: revised
2016-11-01: received
See all versions
Short URL
https://ia.cr/2016/1026
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1026,
      author = {Paulo S.  L.  M.  Barreto and Patrick Longa and Michael Naehrig and Jefferson E.  Ricardini and Gustavo Zanon},
      title = {Sharper Ring-{LWE} Signatures},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/1026},
      year = {2016},
      url = {https://eprint.iacr.org/2016/1026}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.