Paper 2015/755

Revisiting TESLA in the quantum random oracle model

Erdem Alkim, Nina Bindel, Johannes Buchmann, Özgür Dagdelen, Edward Eaton, Gus Gutoski, Juliane Krämer, and Filip Pawlega


We study a scheme of Bai and Galbraith (CT-RSA’14), also known as TESLA. TESLA was thought to have a tight security reduction from the learning with errors problem (LWE) in the random oracle model (ROM). Moreover, a variant using chameleon hash functions was lifted to the quantum random oracle model (QROM). However, both reductions were later found to be flawed and hence it remained unresolved until now whether TESLA can be proven to be tightly secure in the (Q)ROM. In the present paper we provide an entirely new, tight security reduction for TESLA from LWE in the QROM (and thus in the ROM). Our security reduction involves the adaptive re-programming of a quantum oracle. Furthermore, we propose parameter sets targeting 128 bits of security against both classical and quantum adversaries and compare TESLA’s performance with state-of-the-art signature schemes.

Available format(s)
Publication info
Published elsewhere. Major revision. PQCrypto 2017; The Eighth International Conference on Post-Quantum Cryptography
Quantum Random OraclePost Quantum CryptographyLattice-Based CryptographySignature SchemeTight Security Reduction
Contact author(s)
nbindel @ cdc informatik tu-darmstadt de
2017-05-04: last of 4 revisions
2015-07-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Erdem Alkim and Nina Bindel and Johannes Buchmann and Özgür Dagdelen and Edward Eaton and Gus Gutoski and Juliane Krämer and Filip Pawlega},
      title = {Revisiting TESLA in the quantum random oracle model},
      howpublished = {Cryptology ePrint Archive, Paper 2015/755},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.