Cryptology ePrint Archive: Report 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.

Category / Keywords: signature scheme, lattice cryptography, tight security, efficiency, quantum security

Date: received 29 Jul 2015, last revised 16 Nov 2016

Contact author: nbindel at cdc informatik tu-darmstadt de

Available format(s): PDF | BibTeX Citation

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.

Version: 20161117:055833 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]