Revisiting TESLA in the quantum random oracle model

By: Gus Gutoski, Security Researcher and Edward Eaton, Security Researcher and Filip Pawlega, Security Developer, ISARA Corporation and Erdem Alkim and Nina Bindel and Johannes Buchmann and Özgür Dagdelen
Date: originally posted to the IACR Cryptology ePrint Archive on 29 Jul 2015

Abstract: 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.

Category / Keywords: Quantum Random Oracle, Post Quantum Cryptography, Lattice-Based Cryptography, Signature Scheme, Tight Security Reduction

Original Publication (with minor differences): PQCrypto 2017; The Eighth International Conference on Post-Quantum Cryptography


Download the whitepaper in PDF format from IACR Cryptology ePrint Archive.

Review IACR Cryptology ePrint Archive page for this report.