Oh the delight of cryptocurrency people who don't know how to implement a random oracle: https://eprint.iacr.org/2023/841

Doesn't break the signatures in the general case, but with enough special cases...

When you say "bitcoin's ECDSA signatures" are you specifically referring to signatures from before the taproot switch to Schnorr? Are you including breaking the hash of P2SH addresses?

@BoltonBailey Can you please explain:

1. What did the taproot switch to schnorr accomplish, functionally speaking?

2. What are P2SH addresses? Are these the private keys corresponding to users' wallets?

@jonsimon P2SH refers to "Pay to Script Hash". It refers to the fact that bitcoin addresses took the form of hashes of ECDSA public keys, rather than the curve points themselves. So to sign, you would need the preimage of the hash as well as the private key.

This leads to an interesting state of affairs where, as long as you haven't spent from an address before, an adversary only learns your ECDSA key when you publish a transaction spending from it. So even if they are quantum, if they can't crack your ECDSA keys in the ten minutes it takes for your transaction to get in a block, your transaction is safe.

I am told that Schnorr signatures changed this, not sure what the situation is now, but the main thing I'm asking is, does the quantum computer have to break the hash (presumably not, as it's widely accepted it would be hard for quantum computers to do this, so this market would be a clear NO buy if this were the criterion) and does the quantum computer have to break the key in 10 minutes for this to resolve yes?

@BoltonBailey Schnorr signatures are just a different type of signature scheme, they are functionally equivalent. But apparently they don't use elliptic curve groups, so I guess this market doesn't refer to them. The other thing is that in early bitcoin history, I don't even think ECDSA signatures were protected by hashes.

@BoltonBailey I guess I should have used "P2PKH" which is "Pay to public key hash". There is also P2PK "Pay to public key" which is from early bitcoin history, and where there's no hash protecting the keys.

@BoltonBailey They would have to break the latest implementation of of ECDSA on bitcoin, which does hash the public key. And by broken I mean some entity can actually crack it with the amount of compute they have in less than 10 years.

@JonathanRay Ok thanks for the clarification. If you are requiring the attacker to actually break the hash too then I suspect this is much less likely than 20%.

@JonathanRay If that is the criterion though, I'd politely ask you to include it in the description, as I think it could otherwise potentially be interpreted either way.

@BoltonBailey Schnorr signatures do use groups on elliptic curves - really any group where the inverse of your group operation is hard (notably if you come up with a group with an operation that isn't reversed by quantum computers, the Schnorr signature construction can be used).

Also hashing the public key is irrelevant to the primary attack enabled by cryptography relevant quantum computers: taking the public key, and solving the discrete logarithm problem to extract the private key. In particular, Schnorr signatures and similar constructions depend on both - so breaking the hash or solving the DLP should satisfy this.

@Imuli Wikipedia tells me:

All users of the signature scheme agree on a group, G, of prime order, q, with generator, g, in which the discrete log problem is assumed to be hard. Typically a Schnorr group is used.

The Schnorr group article makes it clear that such groups are multiplicative subgroups of prime fields. Do you know if the bitcoin implementation uses elliptic curves? (Either way it would be distinct from ECDSA, but it would be nice to know).

@BoltonBailey Yes, Bitcoin uses Schnorr signatures on secp256k1. Most modern applications use them over an elliptic curve and Schnorr signatures are mostly a modern thing because they were patented in the US until 2008 - so I would say "typically" really ought to be "originally", but that's uncited claims on Wikipedia for you!

@BoltonBailey I'll also take this opportunity to express my annoyance about (EC)DSA being an acronym of a category of algorithms - (Elliptic Curve) Digital Signature Algorithm - that Schnorr signatures on secp256k1 are a member of and a standard formulation of an algorithm in that category (which Schnorr provides an alternative to). In particular it seems that @JonathanRay intends us to interpret this as the category not the specific algorithm, given that ECDSA the standard doesn't prepend the public key when hashing the message.