TUbilio (Technical University of Darmstadt) · 2015 · 22 citations · 24 references
Open access
ComputingComputer EngineeringComputer ScienceAlgorithmsCryptographySecurity ProtocolsClassical CryptographyCryptographic ComplexityDigital SignaturesLattice-based CryptographyPost-quantum CryptographyDigital Signature SchemesLearning With Errors ProblemPost-quantum Signature SchemesRandom Oracle ModelReductionsSecurity ReductionsSignature Scheme ConstructionsSignature Schemes
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 clas- sical 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.
24
A fast quantum mechanical algorithm for database search
Lov K. Grover · 1996 · 8.6K citations · Full text
Mihir Bellare, Phillip Rogaway · 1993 · 4.7K citations · Full text
On lattices, learning with errors, random linear codes, and cryptography
Oded Regev · 2005 · 2.2K citations
Generating hard instances of lattice problems (extended abstract)
Miklós Ajtai · 1996 · 1.3K citations · Full text
On Lovász’ lattice reduction and the nearest lattice point problem
László Babai · COMBINATORICA · 1986 · 930 citations