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)
- 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
-
CC BY