EC Schnorr signature: multiple standard?

Question

I'm working on some EC-Schnorr signature code. Reading various papers on that, it seems EC-Schnorr is not standardized as well as ECDSA.

For example, I found two main differences in two main actors specs (also found other minor variants in other papers);

according to BSI Schnorr signature is computed as:

1. $k$ a random
2. $Q$ = $kG$, $r = Q_x$
3. $h = H(M \mathbin\Vert Q_x)$
4. $s = k − h \times d \mod n$
5. Output $(h, s)$

and according to libsecp256k1:

1. $k$ a random
2. $Q = kG$, $r = Q_x$
3. $h = H(r \mathbin\Vert m) = H(Q_x \mathbin\Vert M)$
4. $s = k - h \times d \mod n$
5. Output $(r, s)$.

Difference are located in:

• step 3 : order of data to hash
• step 5 : value to return

Of course, signature verification algorithm differ a bit according to that.

So, I wonder:

1. if there is specification more standard than another?
2. in case of several standards how to choose one?
3. what about interoperability?
4. what about security (for eg: $H(Q_x \mathbin\Vert M)$ is better than $H(M \mathbin\Vert Q_x)$ in my opinion)?

Answer 1

Adding to other answers, I note that both schemes are related to (but clearly different from) those standardized in ISO/IEC 14888-3:2016 (non-functional preview):

• The BSI's EC-Schnorr original specification was similar to ISO/IEC 14888-3's EC-SDSA-opt, standing for Elliptic Curve Schnorr Digital Signature Algorithm optimized version, except that EC-Schnorr outputs $H(M\mathbin\|Q_x)$ but EC-SDSA-opt outputs $H(Q_x\mathbin\|M)$.
  ISO/IEC 14888-3 also defines EC-SDSA which outputs $H(Q_x\mathbin\|Q_y\mathbin\|M)$.
  The BSI's current specification now matches the definition of EC-SDSA in ISO/IEC 14888-3.
• The question's libsecp256k1 (possibly matching this source) is similar to ISO/IEC 14888-3's EC-FSDSA (where the F stands for full), except that libsecp256k1 outputs (and later hashes) $Q_x$ where EC-FSDSA uses $Q_x\mathbin\|Q_y$. It follows that EC-FSDSA has a significantly larger signature than libsecp256k1 does (for $b$-bit security it is $6b$-bit, rather than $4b$-bit).

There are more variants related to libsecp256k1 in blockchain contexts. Update: like BIP-340 Schnorr; they come and go faster than I care to keep track. That information in the following table regarding BIP-Schnorr is to be taken as a wild guess, that changed over time.

---

Summary of the schemes discussed: $$ \begin{array}{l|rllr} \text{scheme}&\text{public}&\,\,\,\text{ first}&\,\,\text{ second}&\text{sign. }\,\\ &\text{key }\,\,&\text{component}&\text{component}&\text{size }\,\,\,\\ \hline \text{[Sc91]}&-d\,G&H(Q,M)&k+d\;h&b+2b\\ \text{EC-SDSA}&-d\,G&H(Q_x\mathbin\|Q_y\mathbin\|M)&k+d\;h&2b+2b\\ \text{EC-SDSA-opt}&-d\,G&H(Q_x\mathbin\|M)&k+d\;h&2b+2b\\ \text{EC-FSDSA}&-d\,G&Q_x\mathbin\|Q_y&k+d\;H(Q_x\mathbin\|Q_y\mathbin\|M)&4b+2b\\ \text{EC-Schnorr old}&d\,G&H(M\mathbin\|Q_x)&k-d\;h&2b+2b\\ \text{libsecp256k1}&d\,G&Q_x&k-d\;H(Q_x\mathbin\|M)&2b+2b\\ \text{BIP-Schnorr ?}&d\,G&Q_x&k+d\;H(Q_x\mathbin\|\text{Pub}_x\mathbin\|M)&2b+2b\\ \end{array} $$

• $M$ is the message to be signed.
• $G$ is the group generator.
• $k$ is the secret drawn by the signer (randomly or pseudo-randomly) at each signature.
• $Q=k\,G=\underbrace{G+\ldots+G}_{k\text{ terms}}$.
• $Q_x$ (resp. $Q_y$) is the $x$ (resp. $y$) component of $Q$ as a bytestring.
• $b$ is the intended security in bits; the group size $n$, $Q_x$ and $Q_y$ are about $2b$-bit.
• $H$ is the hash function, and $h$ is the result of the hash, often also the signature's first component. For $\text{[Sc91]}$, $h$ is $b$-bit wide, and the input of $H$ combines an unspecified fraction of $Q$ with $M$. In other schemes, $h$ is about $2b$-bit, or wider and reduced modulo the group order.
• $\text{Pub}$ is the public key in the normal meaning of that in Schnorr signature (that is, not a hash), and $\text{Pub}_x$ would be the $x$ component of that. Including it in the hashed data simplifies (perhaps strengthens) security reduction in a multi-users configuration.
• An implicit $\bmod n$ is omitted for the signature's second component.
• Conversion between integer and bistring is omitted (though essential for interoperability).

$\text{[Sc91]}$ is Claus-Peter Schnorr, Efficient Signature Generation by Smart Cards, in Journal of cryptology, 1991; refer to this for an exposition and more bibliography.

In $\text{EC-Schnorr}$, the signature's first component is an ASN.1 integer rather than a bytestring.

$\text{EC-Schnorr}$ (resp. $\text{EC-SDSA}$, $\text{EC-SDSA-opt}$, $\text{EC-FSDSA}$ ) have registered Object IDentifier 0.4.0.127.0.7.1.1.4.3 (resp. 1.0.14888.3.0.11, 1.0.14888.3.0.13, 1.0.14888.3.0.12).

These 7 schemes are incompatible; Andrew S. Tanenbaum's "The nice thing about standards is that you have so many to choose from" is an understatement!

ETSI's Electronic Signatures and Infrastructures (ESI); Cryptographic Suites TS 119 312 V1.3.1 (2019-02) states:

For interoperability reasons only one version (EC-SDSA-opt) from the EC-XDSA Schnorr variants defined in ISO/IEC 14888-3 is selected by the present document. EC-SDSA in the optimized version has the small advantage of minimal data transfer for smart cards.

but that rationale works only against EC-FSDSA as far as I can tell. If the Smart Card itself computes or verifies the signature, as it should, what's transferred is the signature, which is $4b$-bit in both EC-SDSA-opt and EC-SDSA.

Hashing $M$ first is a specificity of EC-Schnorr; my guess is that it was designed for constrained environments like Smart Cards, where it allows offloading the bulk of the hashing of $M$ externally (also, on a multicore CPU, that allows hashing $M$ in a separate thread). As long as the hash is secure, it should not make any difference in security.

Answer 2

The $(r,s)$ version in theory is more secure than $(h,s)$. Bellare, Namprempre, Neven 2004 paper "Security Proofs for IBI and Signature Schemes" showed that Schnorr signature in the form of $(r,s)$ (which they named as BNN signature) can achieve semi-strong unforgeability (ss-euf); while the signature in the form of $(h,s)$ can only achieve normal unforgeability.

The security proof of the ss-euf can be found related to the security of Okamoto-IBI and BNN-IBI in the paper. These 2 IBI schemes are not captured by the transformation framework which transform a standard identification scheme to IBI. So they need to provide direct proofs, by considering additional security from the underlying standard signature scheme, which is the BNN signature. In order for the 2 IBI to be secure, the underlying signature has to be at least semi-strong secure, that is why the authors showed the security of semi-strong for the signature.

Back to Schnorr signature, in the non-EC version, $(r,s)$ is $(Q,s)$, whose size is significantly larger than that of $(h,s)$ and not preferable in practice. In EC version both are of the same length, but I guess $(r,s)$ would be slower during verification. If there is no limitation on verification side, I would prefer to use $(r,s)$ due to its stronger security property.

Answer 3

Probably the most widely deployed Schnorr-type signature scheme over elliptic curve groups today is EdDSA, in its instantiation Ed25519 over Curve25519 with SHA-512. A public key is the encoding of a point $A$ in the $\mathbb F_q$-rational points of an elliptic curve $E/\mathbb F_q$ of order $h \ell$ for large prime $\ell$, over a finite field of odd prime power $q$; a signature on a message $m \in \{0,1\}^*$ is a pair $(R, s)$ of a point $R \in E(\mathbb F_q)$ and a scalar $s \in \mathbb Z/\ell\mathbb Z$ satisfying $$[h \cdot s]B = [h] R + [h \cdot H(\underline R \mathbin\Vert \underline A \mathbin\Vert m)]A$$ where $B \in E(\mathbb F_q)$ is the standard base point of order $\ell$ and $H\colon \{0,1\}^* \to \mathbb Z/\ell\mathbb Z$ is a uniform random function. The signer knows the secret scalar $a \in \mathbb Z/\ell\mathbb Z$ such that $A = [a]B$; choosing $r = H(k \mathbin\Vert m)$ and $R = [r]B$, where $k$ is a long-term secret, the signer can then compute $$s \equiv r + H(\underline R \mathbin\Vert \underline A \mathbin\Vert m) \cdot a,$$ which straightforwardly satisfies the verification equation.

In your notation, this corresponds to

1. $k$ chosen pseudorandomly from $m$ via long-term secret
2. $Q = [k]G$
3. $h = H(\underline Q \mathbin\Vert \underline{[d]G} \mathbin\Vert m)$
4. $s \equiv k + h \times d \mod n$
5. Output $(\underline Q, s)$

Here $\underline Q$ denotes the standard encoding of the point $Q$, which consists of an encoding of its $x$ coordinate and a single bit for the sign of its $y$ coordinate.

Choosing $k$ as a pseudorandom function of the message under a long-term secret obviates the need for an entropy source at signing time. Hashing the public key $[d]G$ into $h$ limits the malleability of public keys and provides confidence in multi-user security of the system. Encoding $Q$ instead of $h$ enables fast batch verification, though I'm not sure I've ever heard of anyone caring about that in practice. Since $H$ need not be collision-resistant, you could follow Schnorr's original recommendation to save space in signatures by using a smaller, say 128-bit, hash, and transmitting $(h, s)$ instead of $(\underline Q, s)$—but the size benefit in the elliptic curve setting is modest, and the multi-user security story isn't as clear.

More discussion of the design space.

Answer 4

The original Schnorr signature is byproduct of the Schnorr id-signature scheme using the Fiat-Shamir trick. The construction was given in the paper of C.P.Schnorr. In the signature Scheme the output is $(h,s)$ and not $(r,s)$. So I would prefer the first implementation.