<p>This is basically an invalid question. It doesn't matter how you sign data. As long as you're using elliptic curve and (EC)DLP (Elliptic Curve Discrete Logarithm Problem), then a quantum computer should be (by definition, with Shor's algorithm) be able to break it. This is because signature verification requires a publicly available public key. If you have a quantum computer and a public key, you get the private key.</p>
<p>Asking whether quantum computers can break digital signatures, is like asking whether a reinforced safe can be opened by anyone, while the key to that safe is public information. It doesn't matter how you reinforce the safe, if there's a way to make a key that opens that safe by anyone.</p>

CC BY-SA 4.0
2021-07-16T15:58:09.580Z
There exist (presumed) post-quantum safe digital signature algorithms, which do involve private and public keys. Those keys won't be based on variants of the discrete logarithm problem, though.
Pieter Wuille
CC BY-SA 4.0
2021-07-16T16:06:13.497Z
@PieterWuille If I understand your point correctly, you're saying that there's post-quantum signatures that involve asymmetric keys and that are safe. Yes, of course, no disagreement there. My criticism for the question was based on that it claimed that the signature is "vulnerable" instead of focusing on the key generation algorithm, which may or may not be vulnerable, and which are the components that usually carry the security, since the headline of quantum computers involvement in cryptocurrency is breaking ECDLP.
The Quantum Physicist
CC BY-SA 4.0
2021-07-16T16:09:55.707Z
That's fair - though in theory it's not impossible that the key generation algorithm is quatum secure, while the signing algorithm isn't. That's a stretch of course, generally they'll be based on the same computational hardness problem. But it's not impossible to construct a (possibly contrived) signature scheme for which this is the case.
Pieter Wuille
CC BY-SA 4.0
2021-07-16T16:22:10.457Z
For example, you could construct a scheme where a secret key is just random bytes, and the public key is a (traditional, say SHA256) hash of the private key. But then the signature is a DL- or pairing-based zero knowledge proof that that hash was computed correctly, which additionally commits to the message. This won't necessarily let a quantum attacker find the private key, but they could forge signatures.
Pieter Wuille
CC BY-SA 4.0
2021-07-16T20:25:37.593Z
@PieterWuille Makes sense. Totally agree with you there. That's a case I wasn't covering in my response. Cheers!
The Quantum Physicist
CC BY-SA 4.0
2020-06-21T12:57:57.467Z
2020-06-21T12:57:57.467Z
The Quantum Physicist
<p>No, ECDSA and EC-Schnorr, as well as related schemes like EdDSA, all belong to the class of elliptic curve cryptography. Their security is based on the assumption that the EC discrete logarithm is unfeasibly hard to compute. This assumption is not true if a sufficiently strong general purpose quantum computer would exist.</p>

<p>Quantum resistant signature algorithms do exist, but they all rely on very large signatures - which may make them unfeasibly expensive for purposes like Bitcoin. Furthermore, much less research exists into features on top (like homomorphic derivation like BIP32 uses, or aggregation), making them effectively a step backwards in terms of functionality if we'd adopt that instead.</p>

<p>However, I am not very worried about this. Quantum Computing in general has a very long way to go before it comes even close to tackling problems like solving discrete logarithms for curves of our size. A general-purpose QC with several 1000s of qbits would be needed, and it is not even known whether it is physically possible to build such a computer.</p>

CC BY-SA 4.0
2024-04-11T05:31:44.567Z
Do you have an update to this answer given the current advancement of quantum computers?
Hans
CC BY-SA 3.0
2017-08-12T17:44:23.023Z
2017-08-13T01:57:13.237Z
2017-08-13T01:57:13.237Z
Pieter Wuille
<p>Here (<a href="https://bitcoincore.org/en/2017/03/23/schnorr-signature-aggregation/" rel="nofollow noreferrer">https://bitcoincore.org/en/2017/03/23/schnorr-signature-aggregation/</a>) it says Schnorr replaces ECDSA, we know that ECDSA can be broken by quantum computers. Is Schnorr safe from q-computers?</p>

<ecdsa><quantum-computing><schnorr-signatures>
Are Schnorr signatures quantum-computer resistant?
MCCCS
# Are Schnorr signatures quantum-computer resistant?

(Asked by: username_0 on 2017-08-12)

Here (<https://bitcoincore.org/en/2017/03/23/schnorr-signature-aggregation/>) it says Schnorr replaces ECDSA, we know that ECDSA can be broken by quantum computers. Is Schnorr safe from q-computers?

**Tags:** ecdsa, quantum-computing, schnorr-signatures


---

## 2 answers

### Answer by username_2 on 2017-08-12. Score: 20 | Accepted answer

No, ECDSA and EC-Schnorr, as well as related schemes like EdDSA, all belong to the class of elliptic curve cryptography. Their security is based on the assumption that the EC discrete logarithm is unfeasibly hard to compute. This assumption is not true if a sufficiently strong general purpose quantum computer would exist.

Quantum resistant signature algorithms do exist, but they all rely on very large signatures - which may make them unfeasibly expensive for purposes like Bitcoin. Furthermore, much less research exists into features on top (like homomorphic derivation like BIP32 uses, or aggregation), making them effectively a step backwards in terms of functionality if we'd adopt that instead.

However, I am not very worried about this. Quantum Computing in general has a very long way to go before it comes even close to tackling problems like solving discrete logarithms for curves of our size. A general-purpose QC with several 1000s of qbits would be needed, and it is not even known whether it is physically possible to build such a computer.

> **Comments:**
> **username_3**: Do you have an update to this answer given the current advancement of quantum computers?  

---

### Answer by username_1 on 2020-06-21. Score: 1

This is basically an invalid question. It doesn't matter how you sign data. As long as you're using elliptic curve and (EC)DLP (Elliptic Curve Discrete Logarithm Problem), then a quantum computer should be (by definition, with Shor's algorithm) be able to break it. This is because signature verification requires a publicly available public key. If you have a quantum computer and a public key, you get the private key.

Asking whether quantum computers can break digital signatures, is like asking whether a reinforced safe can be opened by anyone, while the key to that safe is public information. It doesn't matter how you reinforce the safe, if there's a way to make a key that opens that safe by anyone.

> **Comments:**
> **username_2**: There exist (presumed) post-quantum safe digital signature algorithms, which do involve private and public keys. Those keys won't be based on variants of the discrete logarithm problem, though.  
> **username_1**: @username_2 If I understand your point correctly, you're saying that there's post-quantum signatures that involve asymmetric keys and that are safe. Yes, of course, no disagreement there. My criticism for the question was based on that it claimed that the signature is "vulnerable" instead of focusing on the key generation algorithm, which may or may not be vulnerable, and which are the components that usually carry the security, since the headline of quantum computers involvement in cryptocurrency is breaking ECDLP.  
> **username_2**: That's fair - though in theory it's not impossible that the key generation algorithm is quatum secure, while the signing algorithm isn't. That's a stretch of course, generally they'll be based on the same computational hardness problem. But it's not impossible to construct a (possibly contrived) signature scheme for which this is the case.  
> **username_2**: For example, you could construct a scheme where a secret key is just random bytes, and the public key is a (traditional, say SHA256) hash of the private key. But then the signature is a DL- or pairing-based zero knowledge proof that that hash was computed correctly, which additionally commits to the message. This won't necessarily let a quantum attacker find the private key, but they could forge signatures.  
> **username_1**: @username_2 Makes sense. Totally agree with you there. That's a case I wasn't covering in my response. Cheers!  

---

