TESLA: Tightly Secure, Efficient Signature Scheme from Standard Lattices

Abstract. In general, lattice-based cryptographic primitives offer very good performance and allow for strong security reductions. However, today’s most efficient lattice-based signature schemes sacrifice security to achieve good performance. Firstly, security is based on ideal lattice problems, which potentially are weaker than standard lattice problems. Secondly, the respective security reductions are loose; hence, their choices of parameters offer security merely heuristically. 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 original proposal by Bai and Galbraith (CT-RSA’14) twofold; we enhance the security by both tightening the reduction proof and minimizing the underlying security assumptions. Remarkably, we even greatly improve TESLA’s performance while providing stronger security.