Why is no security lost by using 32-byte public keys in Schnorr signatures instead of 33?

Question

There is currently a discussion on the mailing list about truncating the 33rd byte from public keys when used in bip-schnorr.

Public keys are (x, y) coordinates and compressed public keys simply replace the y coordinate with a single byte indicating its oddness. The complete y coordinate can then be derived from the given x coordinate, and so the public key can be expressed in just 33 bytes instead of 64.

By removing the "oddness" byte, public keys will only be expressed by the x coordinate, meaning there are two potential points on the curve that could be represented. This also implies that the same single x-coordinate-only public key could actually be derived from two different private keys.

My question is, why does this not affect the security assumptions of the Schnorr signature? Is it just a subtle effect, like replacing 256 bit security with 255 bit security?

Answer 1

From the (very recently updated) bip-schnorr draft:

Implicit Y coordinates are not a reduction in security when expressed as the number of elliptic curve operations an attacker is expected to perform to compute the secret key. An attacker can normalize any given public key to a point whose Y coordinate is a quadratic residue by negating the point if necessary. This is just a subtraction of field elements and not an elliptic curve operation.

The idea is that if somehow using implicit Y coordinates was less secure, then an attacker would always use it - even in the protocol version that has explicit Y coordinates. The attacker would take the full public key, strip the Y coordinate, run his (presumably faster) implicit-Y ECDLP solver on it to find the private key, and if the actual point corresponding to that key is the opposite of what he wants, flip the private key.

This proves that the ECDLP problem's hardness cannot meaningfully be impacted by removing the Y coordinates.

Now, at the same time you may wonder "But clearly, using only half of the private keys must give some reduction in security, even small?". The solution to this paradox is that it indeed helps attackers, but it already does that, even when the Y coordinate (or its parity) is included in the public key, because of the possibility to use the above technique. And in fact, the fastest known discrete logarithm solving algorithms for elliptic curves (for full X/Y coordinates) do exploit this fact.

Answer 2

This article expands on the security proof a bit more (with visual aids!)

https://medium.com/blockstream/reducing-bitcoin-transaction-sizes-with-x-only-pubkeys-f86476af05d7