Paper 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.