4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ as far as I can remember is the Schnorr signature (e, K2) $\endgroup$ – user27950 Mar 19 '18 at 11:24
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for your answer, very precise and complete. So, I understand that there's no specific significant flow in what I suggested, but there are plenty of other compression options in addition. And after all the compression scheme should be selected based on the desires size/security trade-off. $\endgroup$ – valdo Mar 19 '18 at 19:42
  • $\begingroup$ Perhaps I'm not reading closely enough, but I don't see the suggestion of compressing the signature by hashing it in Schnorr's original paper. Am I missing something, or was that idea introduced in a different paper? (I'm not sure offhand who might have suggested it.) $\endgroup$ – Squeamish Ossifrage Mar 19 '18 at 21:15
  • $\begingroup$ @SqueamishOssifrage I do not remember anything like that and I don't have the time to check at the moment. But there are two versions of the "original" paper. A conference and a journal version. Maybe it's only included in one of them. $\endgroup$ – Maeher Mar 19 '18 at 21:23
  • $\begingroup$ @SqueamishOssifrage The paper I reference mentions it on page 242, regarding "Minimizing the number of communication bits." $\endgroup$ – CurveEnthusiast Mar 19 '18 at 21:23
  • $\begingroup$ @SqueamishOssifrage I agree it was a bit unclear, edited it. $\endgroup$ – CurveEnthusiast Mar 19 '18 at 21:28
1
$\begingroup$

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.

$\endgroup$

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.