3

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?

11

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.

| improve this answer | |
3

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

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.