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

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 its) security to achieve good performance: first, security is based on ideal lattice problems, that might not be as hard as standard 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 signatures 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 standard 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 improve TESLA's performance by a factor of two. 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 thus far.

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

Date: received 29 Jul 2015

Contact author: nbindel at cdc informatik tu-darmstadt de

Available format(s): PDF | BibTeX Citation

Version: 20150730:095248 (All versions of this report)

Short URL: ia.cr/2015/755

Discussion forum: Show discussion | Start new discussion