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

<p><a href="https://medium.com/blockstream/reducing-bitcoin-transaction-sizes-with-x-only-pubkeys-f86476af05d7" rel="nofollow noreferrer">https://medium.com/blockstream/reducing-bitcoin-transaction-sizes-with-x-only-pubkeys-f86476af05d7</a></p>

CC BY-SA 4.0
2019-11-13T14:02:45.993Z
2019-11-13T14:02:45.993Z
pinhead
<p>From the (very recently updated) <a href="https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki" rel="nofollow noreferrer">bip-schnorr</a> draft:</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>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.</p>
<p>This proves that the ECDLP problem's hardness cannot meaningfully be impacted by removing the Y coordinates.</p>
<p>Now, at the same time you may wonder &quot;But clearly, using only half of the private keys must give <em>some</em> reduction in security, even small?&quot;. The solution to this paradox is that it indeed helps attackers, but it <em>already</em> 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.</p>

CC BY-SA 4.0
2019-08-31T01:59:46.543Z
2023-11-13T10:13:51.723Z
2023-11-13T10:13:51.723Z
Pieter Wuille
<p>There is currently <a href="https://www.mail-archive.com/bitcoin-dev@lists.linuxfoundation.org/msg08284.html" rel="nofollow noreferrer">a discussion on the mailing list</a> about truncating the 33rd byte from public keys when used in bip-schnorr. </p>

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

<p>By removing the "oddness" byte, public keys will only be expressed by the <code>x</code> coordinate, meaning there are <strong>two</strong> 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 <strong>two different</strong> private keys.</p>

<p>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? </p>

<security><taproot><schnorr-signatures><x-only-pubkeys>
Why is no security lost by using 32-byte public keys in Schnorr signatures instead of 33?
pinhead
# Why is no security lost by using 32-byte public keys in Schnorr signatures instead of 33?

(Asked by: username_0 on 2019-08-30)

There is currently [a discussion on the mailing list](https://www.mail-archive.com/bitcoin-dev@lists.linuxfoundation.org/msg08284.html) 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?

**Tags:** security, taproot, schnorr-signatures, x-only-pubkeys


---

## 2 answers

### Answer by username_1 on 2019-08-31. Score: 14 | Accepted answer

From the (very recently updated) [bip-schnorr](https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki) 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 by username_0 on 2019-11-13. Score: 4

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>


---

