Convert a Schnorr Public Key to a compressed ECDSA Public Key

Given a Schnorr Public Key (32 bytes) x, I'd like to generate a compressed ECDSA Public Key (33 bytes) and thus be able to generate the bitcoin address that the private key holder can generate with their private key.

• A Schnorr Public Key is x (BIP340, https://bips.xyz/340 - more detail about the Schnorr signature.)

• An uncompressed ECDSA public key has the starting byte 0x04 + x + y

• A compressed ECDSA public key has a starting byte of either (0x02 or 0x03) + x

• Thus the ECDSA compressed public key will be either 0x02 + x or 0x03 + x

Is there any possible way to deduce which one from just the x value?

Edit: Given @fgrieu point that it may not be safe to reuse a key in this way across two different signature schemes, I've decided against pursuing this approach out of an abundance of caution. I'll leave the question here as it may be of academic interest.

A Schnorr Public Key $K$ per the linked BIP340 is 32 bytes representing, in big-endian order, the X coordinates of any point on the Elliptic Curve secp256k1 not the point at infinity. As noted there,

every public key has two corresponding secret keys

namely some integer $d'\in[1,n)$ such that $d'\cdot G$ has X coordinate $K$, and $n-d'$ which also is such that $(n-d')\cdot G$ has X coordinate $K$.

Prefixing $K$ with $\text{02}$ and $\text{03}$ forms two valid ECDSA public keys in compressed form, which respective privates keys form the set $\{d',n-d'\}$, in some order.

$K$ does not correspond to any one of these two keys in particular. Knowing $d'$, we can compute $d'\cdot G$, and the parity of the $Y$ coordinate of the result is the same as the parity of the prefix of the matching public key. In other words, if $(d',K)$ is a valid BIP340 (private, public) key pair, one of $(d',02\mathbin\|G)$ or $(d',03\mathbin\|G)$ is a valid ECDSA key pair, and which can be told knowing $d'$.

When $d'$ is used to sign per BIP340, it first get converted as part of the signing process to $d$ equal to $d'$ or $n-d'$, whichever is such that the Y coordinate of $dG$ is an even integer in $(1,p)$. Thus if $(d',K)$ is a valid BIP340 (private, public) key pair, then $d$, as derived from $d'$ as part of the signing process, is such that $(d,02\mathbin\|K)$ is a valid ECDSA key pair. In that sense the $02$ prefix is preferred.

Notice that the standard security proof of ECDSA (resp. Schnorr) signature assumes the private key is not used for any other purpose than performing an ECDSA (resp. Schnorr) signature, therefore using the same key pair for both systems is not proven safe by these arguments (I'm not stating it's unsafe, only that standard proofs of security are invalidated). Absent more security argument, it would be contrary to good cryptography practices to use the same key for two signature systems. It raises a number of issues

• can an adversary turn the signature of a known message under one system into the signature of the same message under the other system ?
• what can an adversary do with the same message independently signed under both systems ?

TL;DR

0x02 for an unmodified Schnorr signature scheme with typical implicit $y$ coordinates; with BIP0340 one can only convert if one has access to the private key (see fgrieu's answer).

Background

Elliptic curve cryptography schemes over prime fields historically worked with points $(x,y)$ which satisfy the curve equation modulo $p$ and with no other constraints. The Weierstrass equation $y^2=x^3+ax+b$ modulo $p$ for fixed $x$ reduces to a quadratic equation $y^2=C$ for some $C$. If $C\neq 0,\infty$ then there are either 0 or 2 solutions, so that for almost all $x$ values corresponding to a solution there are two possible $y$ values which are negations of each other modulo $p$. To save bandwidth the only the full $x$-coordinates was transmitted together with a prefix to determine which square root to use as $y$.

For some schemes (e.g. ECDH when the shared secret is the $x$-coordinate of the point $aB=bA=abG$) the prefix can even be omitted as both $y$ values would lead to the same answer. In other schemes the multiplicity of possible $y$ values caused issues such as signature malleability. The former phenomenon led to a desire to only communicate using $x$-coordinates and the latter to restricting the choice of $y$ to only one of the two possible values. The two desires are compatible if one uses implicit $y$ coordinates which is the approach taken in BIP0340. This note observes that the implicit choice of which $y$ coordinates to use can be achieved in 3 possible ways:

1. Choosing $0\le y<p/2$ (recall that the two choices of $y$ coordinate are negations of each other modulo $p$)
2. Choosing $0\le y<p$ and even (again this choice is permissible and unambiguous due to the negation property)
3. Choosing $y$ so that $y$ itself is a square (this is only permissible and unambiguous if $p\equiv 3\pmod 4$ which is the case for the secp256k1 characteristic prime).

The writers specifically choose the second option precisely because of compatibility with the existing point compression schemes. This is because it corresponds to the $y$ coordinate obtained when decompressing a point that is prefixed with 0x02. Thus Schnorr public (verification) keys with correct implicit $y$-coordinates can be converted to secp256k1 ECDSA public (verification) keys simply by prepending 0x02. It also means that secp256k1 ECDSA public (verification) keys prefixed by 0x02 can be converted to Schnorr public (verification) keys by dropping the prefix. To convert secp256k1 ECDSA keys that are prefixed with 0x03 to Schnorr keys with correct implicit $y$-coordinates, the choice of $y$ needs to be changed which in turn requires a change of private (signing) key. Fortunately the two choices of $y$ correspond to negations of the private (signing) key modulo $\ell$ (the order of the curve group modulo $p$ and the conversion can be achieved by deleting the 0x03 prefix and changing the private key from the 256-bit value $s$ to the value $\ell-s$.

Alternatively, if a modified signing process such as BIP0340 is used which checks and corrects private (signing) keys with every signature, then the 0x03 can simply be dropped. Likewise if one has a BIP0340 private (signing) key which produces an incorrect implicit $y$ coordinate one can prepend 0x03 to generate an ECDSA key. Note that knowledge of the private key is necessary to do the conversion.

Summary

To convert secp256k1 ECDSA keys to BIP0340 keys and vice-versa:

BIP0340 to ECDSA Find out if the associated private key produces a correct or incorrect implicit $y$-coordinate. If correct prepend 0x02; if incorrect prepend 0x03.

ECDSA to BIP0340 Drop the prefix from the public (verification) key.

Acknowledgement

Apologies and thanks to fgrieu for pointing out the modified signing process in BIP0340

Comments on Security

TO FOLLOW (SPOILER: BEYOND THE USUAL CAVEATS ABOUT REPEATED EPHEMERAL VALUES AND LINEAR DEPENDENCIES BETWEEN SECRET EPHEMERAL VALUES, THERE IS NO EXTRA RISK).