Why is no security lost by using 32-byte public keys in Schnorr signatures instead of 33? 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?
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 a 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.