Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Revisiting TESLA in the quantum random oracle model

Erdem Alkım, Nina Bindel, Johannes A Buchmann, Özgür Dagdelen, Edward Eaton, Gus Gutoski, Juliane Krämer, Filip Pawlega

Published Jan 1, 2015• 3 citations
OpenAlex

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.

Related papers

TESLA: Tightly-Secure Efficient Signatures from Standard Lattices.

Erdem Alkım, Nina Bindel, Johannes A Buchmann +2 more

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 its) security to achieve good performance: first, security is based on ideal lattice problems, that might not be as hard as standard 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 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 quantumhard parameters thus far.

•Jul 29, 2015•23 citations

Signature Schemes in the Quantum Random-Oracle Model

Edward Eaton

A signature scheme is a fundamental component in modern digital communication. It allows for authenticated messages, without which it would be nearly impossible to ensure security when using most modern technologies. However, there is a growing threat to this fundamental piece of electronic infrastructure. Universal quantum computers, which were originally envisioned by Richard Feynman, have moved from being a theoretical future technology into one that could realistically be available in a matter of decades. In 1994, Peter Shor devised an algorithm that would run on a quantum computer that could be used to solve mathematical problems that formed the foundation of public-key cryptography. \n \nWhile Shor's algorithm clearly establishes that new mathematical problems must be found and studied that can admit efficient cryptographic protocols, it is equally important that the models in which we consider security are also updated to consider the possibility of a malicious adversary having a quantum computer. \n \nIn the random-oracle model, a hash function is replaced by a truly random function that any relevant party is able to query. This model can enable security reductions where otherwise none are known. However, it has been noted that this model does not properly consider the possibility of a quantum computer. For this, we must instead consider the quantum random-oracle model. \n \nIn this thesis, we explain the basics of quantum physics and quantum computation in order to give a complete motivation for the quantum random-oracle model. We explain many of the difficulties that may be encountered in the quantum random-oracle model, and how some of these problems may be solved. We then show prove three signature schemes secure in the quantum random-oracle model: the LMS hash-based scheme, TESLA, a lattice-based scheme, and the TOO transformation using chameleon hashes. The first two schemes are strong candidates for post-quantum standardization.

•Apr 25, 2017•1 citation

A tight security reduction in the quantum random oracle model for code-based signature schemes

André Chailloux, Thomas Debris-Alazard

Quantum secure signature schemes have a lot of attention recently, in particular because of the NIST call to standardize quantum safe cryptography. However, only few signature schemes can have concrete quantum security because of technical difficulties associated with the Quantum Random Oracle Model (QROM). In this paper, we show that code-based signature schemes based on the full domain hash paradigm can behave very well in the QROM i.e. that we can have tight security reductions. We also study quantum algorithms related to the underlying code-based assumption. Finally, we apply our reduction to a concrete example: the SURF signature scheme. We provide parameters for 128 bits of quantum security in the QROM and show that the obtained parameters are competitive compared to other similar quantum secure signature schemes.

arXiv:1709.06870•Sep 20, 2017•3 citations

A provable secure signature in the quantum random oracle model

Zhen Zhang, Huiyan Chen, Yufan Chen

With the development of quantum computation, quantum computers will break the almost classical cryptography. It is imminent to design post-quantum cryptography algorithm that could resist quantum adversaries. Lattice-based problem has been verified that could resist quantum attacks. Our goal is to design a signature and try to prove it is secure in the quantum random oracle model. Our new signature scheme is redesigned based on the signature proposed by Lyu, but that scheme only proved secure in the random oracle model. The difference between the two signature is that we introduce the middle-product operation. So our signature is based on middle-product LWE hard assumption, which enjoys a security proof from PL WE. Then we combine the secure chameleon hash function and our new scheme, prove that our new combined signature is still secure in the quantum random oracle model.

International Conference on Blockchain Technology and Information Security (ICBCTIS)•Jul 1, 2022•2 citations

A Lattice-based Provably Secure Multisignature Scheme in Quantum Random Oracle Model.

Masayuki Fukumitsu, Shingo Hasegawa

The multisignature schemes are attracted to utilize in some cryptographic applications such as the blockchain. Though the lattice-based constructions of multisignature schemes exist as quantum-secure multisignature, a multisignature scheme whose security is proven in the quantum random oracle model (QROM), rather than the classical random oracle model (CROM), is not known.

•Jan 1, 2021•0 citations

Revisiting TESLA in the Quantum Random Oracle Model

Erdem Alkım, Nina Bindel, Johannes A Buchmann +5 more

Lecture notes in computer science•Jan 1, 2017•65 citations
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.
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 its) security to achieve good performance: first, security is based on ideal lattice problems, that might not be as hard as standard 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 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 quantumhard parameters thus far.
A signature scheme is a fundamental component in modern digital communication. It allows for authenticated messages, without which it would be nearly impossible to ensure security when using most modern technologies. However, there is a growing threat to this fundamental piece of electronic infrastructure. Universal quantum computers, which were originally envisioned by Richard Feynman, have moved from being a theoretical future technology into one that could realistically be available in a matter of decades. In 1994, Peter Shor devised an algorithm that would run on a quantum computer that could be used to solve mathematical problems that formed the foundation of public-key cryptography. \n \nWhile Shor's algorithm clearly establishes that new mathematical problems must be found and studied that can admit efficient cryptographic protocols, it is equally important that the models in which we consider security are also updated to consider the possibility of a malicious adversary having a quantum computer. \n \nIn the random-oracle model, a hash function is replaced by a truly random function that any relevant party is able to query. This model can enable security reductions where otherwise none are known. However, it has been noted that this model does not properly consider the possibility of a quantum computer. For this, we must instead consider the quantum random-oracle model. \n \nIn this thesis, we explain the basics of quantum physics and quantum computation in order to give a complete motivation for the quantum random-oracle model. We explain many of the difficulties that may be encountered in the quantum random-oracle model, and how some of these problems may be solved. We then show prove three signature schemes secure in the quantum random-oracle model: the LMS hash-based scheme, TESLA, a lattice-based scheme, and the TOO transformation using chameleon hashes. The first two schemes are strong candidates for post-quantum standardization.
Quantum secure signature schemes have a lot of attention recently, in particular because of the NIST call to standardize quantum safe cryptography. However, only few signature schemes can have concrete quantum security because of technical difficulties associated with the Quantum Random Oracle Model (QROM). In this paper, we show that code-based signature schemes based on the full domain hash paradigm can behave very well in the QROM i.e. that we can have tight security reductions. We also study quantum algorithms related to the underlying code-based assumption. Finally, we apply our reduction to a concrete example: the SURF signature scheme. We provide parameters for 128 bits of quantum security in the QROM and show that the obtained parameters are competitive compared to other similar quantum secure signature schemes.
With the development of quantum computation, quantum computers will break the almost classical cryptography. It is imminent to design post-quantum cryptography algorithm that could resist quantum adversaries. Lattice-based problem has been verified that could resist quantum attacks. Our goal is to design a signature and try to prove it is secure in the quantum random oracle model. Our new signature scheme is redesigned based on the signature proposed by Lyu, but that scheme only proved secure in the random oracle model. The difference between the two signature is that we introduce the middle-product operation. So our signature is based on middle-product LWE hard assumption, which enjoys a security proof from PL WE. Then we combine the secure chameleon hash function and our new scheme, prove that our new combined signature is still secure in the quantum random oracle model.