You are looking at a specific version 20161117:055833 of this paper. See the latest version.

Paper 2015/755

TESLA: Tightly-Secure Efficient Signatures from Standard Lattices

Erdem Alkim and Nina Bindel and Johannes Buchmann and Özgür Dagdelen and Peter Schwabe

Abstract

Generally, lattice-based cryptographic primitives offer good performance and allow for strong security reductions. However, the most efficient current lattice-based signature schemes sacrifice (part of their) security to achieve good performance: first, security is not based on the worst-case hardness of lattice problems. Secondly, the security reductions of the most efficient schemes are non-tight; hence, their choices of parameters offer security merely heuristically. Moreover, lattice-based signature schemes are instantiated for classical adversaries, although they are based on presumably quantum-hard problems. Yet, it is not known how such schemes perform in a post-quantum world. We bridge this gap by proving the lattice-based signature scheme TESLA to be tightly secure based on the learning with errors problem over lattices in the random-oracle model. As such, we improve the security of the original proposal by Bai and Galbraith (CT-RSA’14) twofold: we tighten the security reduction and we minimize the underlying security assumptions. Remarkably, by enhancing the security we can greatly improve TESLA’s performance. Furthermore, we are first to propose parameters providing a security of 128 bits against both classical and quantum adversaries, for a lattice-based signature scheme. Our implementation of TESLA competes well with state-of-the-art lattice-based signatures and SPHINCS (EUROCRYPT’15), the only signature scheme instantiated with quantum-hard parameters so far.

Note: Warning: Gus Gutoski and Chris Peikert independently informed us about a mistake in the security reduction from LWE to TESLA. This mistake affects all versions of the paper; we are currently working on fixing this mistake. Note that the mistake does not, as far as we can tell, lead to any attack against TESLA. Moreover, the (non-tight) security reduction given by Bai and Galbraith still holds.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
signature schemelattice cryptographytight securityefficiencyquantum security
Contact author(s)
nbindel @ cdc informatik tu-darmstadt de
History
2017-05-04: last of 4 revisions
2015-07-30: received
See all versions
Short URL
https://ia.cr/2015/755
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.