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?
Add a comment
|
2 Answers
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.
answered Aug 12, 2017 at 17:44
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.
answered Jun 21, 2020 at 12:57
-
2There 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. Jul 16, 2021 at 15:58
-
@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. Jul 16, 2021 at 16:06
-
1That'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. Jul 16, 2021 at 16:09
-
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. Jul 16, 2021 at 16:22
-
1@PieterWuille Makes sense. Totally agree with you there. That's a case I wasn't covering in my response. Cheers! Jul 16, 2021 at 20:25