IACR News item: 30 July 2015
Erdem Alkim, Nina Bindel, Johannes Buchmann, \\\"Ozg\\\"ur Dagdelen
ePrint ReportMoreover, 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.
Additional news items may be found on the IACR news page.