Compact Schnorr signature?

Question

The commonly-used ECDSA signature consists of 2 scalars $(r,s)$. There's also a Schnorr signature. Given private key $k$, public key $C = [k]G$ and the message $M$:

1. Generate random scalar $k_1$
2. Calculate the $C_1 = [k_1]G$
3. Calculate the challenge $e = H(C_1 \mathbin\Vert M)$ where $H$ is a selected hash function
4. Calculate $k_2 = k_1 + e\cdot k$
5. Signature is $(C_1, k_2)$

The verifier then verifies that $[k_2]G = C_1 + [e]C$

Both schemes seem to be nearly equally secure. I like more the Schnorr's scheme, because it uses nothing more than just a common ECC arithmetics. However the drawback is that the signature is bigger: instead of 2 scalars it's now scalar + point (with 2 coordinates).

One way to solve this is to store the curve point in a compressed way: its $x$ coordinate and the sign bit, from which the $y$ coordinate may be recovered. But this requires extra calculations.

I thought about an easier way. Let's just store the $x(C_1)$—the $x$ coordinate, and the challenge formula should be adjusted to account only for $x(C_1)$.

The verifier should verify the following: $x([k_2]G - [e]C) = x(C_1)$. That is calculate the left-side curve point, take its $x$ coordinate and compare to the signature.

Is this a common practice? Is there a potential flaw in this scheme?

Answer 1

This would work, but note that your weakening verification (slightly). Instead of only $(C_1,k_2)$ being a valid signature, now also $(-C_1,k_2)$ is valid. If you want to do signatures by only using $x$-coordinates you can use the qDSA signature scheme, which indeed saves a few bits in the signature size and public key.

There is actually a more serious compression of Schnorr signatures, which I think is quite common. It is already described in Schnorr's original paper. Instead of having a signature $(C_1,k_2)$ we use $(e,k_2)$, where it actually suffices to have relatively small $e$ (say 128 bits for 128-bit security level). Now we can verify by computing $\bar C_1 = [k_2]G - [e]C$ and checking that $H(\bar C_1\,||\,M) = e$.

This leads to a 48-byte signature as opposed to a 64-byte one, so saves significantly more than a bit. A downside is that you cannot batch-verify signature anymore, though I don't know if that's actually used in practice.

Answer 2

As pointed in CurveEnthusiast's answer (starting second paragraph), the original Schnorr signature scheme does not work as described, and when using a narrow hash ($b$-bit wide for $b$-bit security) allows signatures about 25% shorter than what the question describes.

The signature of the original Schnorr signature scheme is $(e,k_2)$, rather than $(C_1,k_2)$. And the verifier checks if $e\overset?=H\big(([k_2]G+[e]\overline C)\mathbin\|M\big)$ with the public key $\overline C=[-k]G$, rather than if $[k_2]G\overset?=C_1+[e]C$.

Using $e$, rather than $C_1$, as the first component of the signature, makes it shorter when a narrow hash is used. It is conjectured that the hash needs only resist preimage to be secure, thus can be narrow. Using that original scheme with narrow hash gives away provable security (AFAIK), but opens to no known attack (AFAIK). Additions/comment on that welcome!

Using $\overline C$ rather than $C$ simplifies verification.

I collected references in this question, and made a taxonomy of Schnorr-like signature schemes in this answer.