Security of Schnorr signature versus DSA and DLP

The Schnorr signature scheme is a randomized signature scheme with appendix. The signature is $$3t$$-bit for conjectured $$t$$-bit security in a chosen-messages setup, with at most $$2^{t/2}$$ queries to a signer; a description faithful to the reference paper is later in the question.

It is simple, and 25% more compact than a DSA signature or any other signature scheme with appendix that I could find. No DL-based signature scheme with message recovery that I understand (subset of that DL-MR bibliography) beats it on compactness when used with an arbitrary non-redundant message.

Questions:

What drawback has it against competitors (beyond long-gone patent issues)?

Why are most later expositions silently using a $$2t$$-bit hash thus a $$4t$$-bit signature, including scholars [HAC1996] and the current international standard [ISO14888] (beyond a vague unease about the narrowness of the hash in the original)?

Is there a scheme with security arguably equivalent to DSA (or better, the DLP or related), but with the compactness of the original Schnorr signature scheme? If not, what about proving something with the minor modification proposed in the end, which de-randomizes the generation of the per-message secret, use public-key dependent hashes, and hashes to double width an exponent used for verification?

Schnorr signature bibliography

[Sc89a]: Claus-Peter Schnorr, Method for subscriber identification and for generation and verification of electronic signatures in a data exchange system, EP0383985 in European Patent Register, 1989;
[Sc89b]: id., Efficient Identification and Signatures for Smart Cards, in proceedings of Crypto 1989;
[Sc90a]: id., Method for subscriber identification and for the generation and verification of electronic signatures in a data exchange system, EP0384475 in European Patent Register, 1990;
[Sc90b]: id., Method for identifying subscribers and for generating and verifying electronic signatures in a data exchange system, US Patent 4,995,082;
[Sc91]: id., Efficient Signature Generation by Smart Cards, in Journal of cryptology, 1991.

[HAC96]: Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone Handbook of Applied Cryptoraphy, 1996, section 11.5.3.

[PS96]: David Pointcheval, Jacques Stern, Security Proofs for Signature Schemes, in proceedings of Crypto 1996;
[PS00]: id., Security Arguments for Digital Signatures and Blind Signatures, in Journal of Cryptology, 2000.

[BN06]: Mihir Bellare, Gregory Neven, Multi-signatures in the plain public-key model and a general forking lemma, in proceedings of ACM's CCS 2006.

[NSW09]: Gregory Neven, Nigel Smart, Bogdan Warinschi, Hash function requirements for Schnorr signatures, in Journal of Mathematical Cryptology, 2009.

[Br15]: Daniel R. L. Brown, Short Schnorr signatures require a hash function with more than just random-prefix resistance, ePrint 2015.

[Be15]: Daniel J. Bernstein, Multi-user Schnorr security, revisited at author's website, 2015.

[KMP16]: Eike Kiltz, Daniel Masny, Jiaxin Pan, Optimal Security Proofs for Signatures from Identification Schemes, in proceedings of Crypto 2016.

[ISO14888]: ISO/IEC 14888-3 (currently edition 3, 2016), Information technology - Security techniques - Digital signatures with appendix - Part 3: Discrete logarithm based mechanisms, at ISO (preview) and IEC (preview).

Original Schnorr signature scheme

Based on [Sc91]. The scheme is noted to be applicable to any group of order $$q$$ where the DL problem is hard, but we use the original notation, and its example at conjectured security complexity $$t=72$$-bit in a chosen-messages setup.

One-time init:

• prime $$q$$ of $$\approx2t$$ bits (e.g. $$q$$ over 140-bit)
• prime $$p$$ with $$q$$ dividing $$p-1$$ (e.g. $$p$$ over 512-bit, with caveat)
• generator $$\alpha$$ of order $$q$$; i.e., $$\alpha^q\equiv1\pmod p$$, $$\alpha\ne1\pmod q$$
• one-way hash function $$h:\mathbb Z_p^*\times\{0,1\}^*\to\{0,1\}^t$$

Hash $$h$$ must be such that for any fixed $$x$$, the function $$m\to h(x,m)$$ is one-way (preimage-resistant for fixed $$x$$). $$h(x,m)$$ should be about equidistributed, with at least $$\lceil\log_2q\rceil$$ of $$x$$ taken into consideration (modern cryptographic hashes meet these requirements).

Key setup (per user):

• Pick private key $$s$$ (uniformly) random in $$\{1,2,\dots,q\}$$
• Publish public key $$v\gets\alpha^{-s}\bmod p$$

Signature of message $$m$$:

• Pick $$r$$ (uniformly) random in $$\{1,2,\dots,q\}$$
• $$x\gets\alpha^r\bmod p$$
• $$e\gets h(x,m)$$
• $$y\gets r+s\,e\bmod q$$
• output signature $$(e,y)$$

Verification of alleged message $$m$$, signature $$(e,y)$$, verified public key $$v$$

• $$\bar x\gets\alpha^y\,v^e\bmod p$$
• Check that $$e=h(\bar x,m)$$

Genuine signatures check because $$\bar x\equiv\alpha^y\,v^e\equiv\alpha^{r+s\,e}\,\alpha^{-s\,e}\equiv\alpha^r\equiv x\pmod p$$.

With $$r$$ secret and uniformly random, and $$y=r+s\,e\bmod q$$, knowledge of $$(y,e)$$ by itself leaks nothing about $$s$$. Refer to the article for other security arguments, all on the tune of: that plausible attack works but with cost at least $$2^t$$ hashes or breaking the DLP or an apparently more complex problem additionally involving $$h$$.

Note: [Sc89a], [Sc90a], and [Sc91] (but not [Sc89b]) mention that the system can be transposed to other groups such as Elliptic Curve groups.

Tentative: strengthened Schnorr signature scheme

I propose three independent changes, which keep the same signature size. The overall goal is to improve security, and perhaps make it reducible to DLP in the group used.

1. Replace picking $$r$$ random in $$\{1,2,\dots,q\}$$ at signature, by $$r=\operatorname{mac}(s,m)$$ with $$\operatorname{mac}:\{1,2,\dots,q\}\times \{0,1\}^*\to\{1,2\dots,q\}$$.
Rationale: remove need for an RNG, which failure is a tried and tested recipe for disaster in (EC)DSA. This de-randomization technique is used in many modern signature schemes, including Ed25519 (with attribution to George Barwood, Feb 1997, sci.crypt).
2. Make $$h$$ dependent on the public key $$v$$, and targeting security in the ROM; thus
$$h:\mathbb Z_p^*\times\mathbb Z_p^*\times\{0,1\}^*\to\{0,1\}^t$$, with result noted $$h_v(x,m)$$
Rationale: better support a security claim of $$2^{t/2}$$ chosen signatures per public key; play no game with hash properties, since hashing has become relatively cheap.
3. Add hash function $$h'$$ dependent on the public key $$v$$ and message $$m$$, that expands $$e$$ to the width of $$q$$ before use.
$$h':\{1,2,\dots,q\}\times\{0,1\}^t\times\{0,1\}^*\to\{1,2,\dots,2^{\left\lfloor\log_2(q)\right\rfloor}\}$$, with result noted $$h_v'(e,m)$$
Signature is modified to perform $$y\gets r+s\,h_v'(e,m)\bmod q$$
Verification is modified to perform $$\bar x\gets\alpha^y\,v^{h_v'(e,m)}\bmod p$$
Rationale:
• Introducing $$h'$$ make the exponent of $$v$$ in the verification reach most of the exponent domain when $$m$$ varies, rather than a fraction $$2^{-t}$$ of that, with hope to help reuse the security argument in [PS96] or [NSW09].
• The increase in signature verification cost due to the extra width is low when using "Shamir's trick" of combining the two modular exponentiations in $$\alpha^y\,v^{h_v'(e,m)}\bmod p$$.
• A second premimage attack on $$h$$ alone no longer leads to forgery (without $$h'$$, such attack is possible by brute force with an expected $$2^t$$ invocation of $$h$$ with altered $$m$$, and no group operation).
• The relatively narrow $$e$$ is shielded between two hashes.

Note: The cost of hashing the bulk of a large $$m$$ can be shared between $$\operatorname{mac}(s,m)$$ (for the signer only), $$h_v(x,m)$$, and $$h_v'(e,m)$$, by using a common collision-resistant hash of $$m$$ over width $$\ge2t$$ as an intermediary common step.

• Maybe I misunderstand this, but deterministic signatures are a security no go since they trivially allow concluding that if two signatures (to the same key) are equal, most likely the message is equal. For the same reason, you should always use a random (or at least pseudorandom but still almost certainly unique) IV for any encryption algorithm. (Of course, it would be easy to randomize the hash function and the resulting scheme should at least suffer less from the consequences of a poor RNG.) May 20 '19 at 12:02
• @Ame Vogel: Not divulging info on the message is not part of the standard goals of a signature scheme. And if it was a requirement, being a non-deterministic signature scheme is not enough. Take the example of RSASSA-PSS: it is a non-deterministic signature scheme, but it does allow to test if the messages are the same or not by a test on the signatures (that test requires the public key, but that's public).
– fgrieu
May 20 '19 at 12:15

Your post was a bit confusing to me, I think you're thinking of this from the wrong perspective.

Is there a scheme with security arguably equivalent to DSA (or better, the DLP or related), but with the compactness of the original Schnorr signature scheme?

Yes, Schnorr signatures. They are really what you should be doing. It is theoretically and intuitively the right thing to do, as opposed to the hideous (EC)DSA scheme. Schnorr signatures do have a reduction to the DLP in the underlying group (see [PS96]), albeit not a very tight one. My feeling is that DSA is just a hack to get around the Schnorr patent, and now that is gone, DSA should go with it. Let me try to back these claims up somewhat.

Let's look at Schnorr signatures first. We define them by first considering the Schnorr identification scheme. In a group in which the DLP is hard, it allows us to prove knowledge of a discrete log without revealing any information about the discrete log itself, in an interactive way. It is mathematically correct, and you can reduce its security to the DLP. It is an interactive protocol, but we can make it non-interactive by applying the Fiat-Shamir heuristic. Again, the reduction to the DLP still remains. By including a message in the challenge, we obtain a signature scheme.

Now let's look at ECDSA, for example. We work in an elliptic curve over a finite field $\mathbb{F}_p$, for a prime $p$, and let's say we have a base point $G$ with order $n$. The protocol kind of goes like this

1. Choose a uniformly random $k$ from $[1,n-1]$
2. Compute $(x_1,y_1) = k\times G$
3. Compute $r = x_1 \bmod n$.

Let's think about what's happening here. Choosing $k$ from $[1,n-1]$ makes sense, as it will be some secret discrete log. Then exponentiate $G$ with $k$ also makes sense, as $G$ has order $n$. Then we compute $r = x_1 \bmod n$. Think about what you are doing here, and then realize that this makes no sense whatsoever. The element $x_1$ is in $\mathbb{F}_p$, so why are we reducing this modulo $n$? Mathematically, this is completely silly. What if $x_1$ was in $\mathbb{F}_{p^2}$ or some larger field? Then the operation makes even less sense. Because this makes no sense, it will be near impossible to come up with a proof of security for this scheme (and as far as I know, noone has).

To summarize, the real question should be why are people still using (EC)DSA (and yes, I realize there could be legacy issues)? It is a malformed adaptation of Schnorr which should become a mistake of the past.

Let me try to get to your other questions as well.

What drawback has it against competitors (beyond long-gone patent issues)?

There are some things to be said here. First of all, the way you describe the scheme, is not necessarily how it has to be done. The signature could be $(x,y)$ instead, of size $4t$. In fact, in my opinion this is the natural starting point, while taking the hash is kind of a "compressed" version of this. I believe this is actually how it would be more commonly done, as it allows for batch signature verification (whereas the hashed version does not).

Moreover, it may not be easy to get enough randomness to pick $r$ uniformly random. Instead, you can pick it pseudorandom, as a hash of some appropriate things. Finally, you could include the public key in the computation of $e$, so $e\leftarrow h(x,m,v)$ to prevent multi-target attacks.

What I'm simply doing, is describing the EdDSA signature scheme. It is essentially just a Schnorr signature, with the above changes applied. Depending on context, it is arguably the way to go.

Why are most later expositions silently using a 2t-bit hash thus a 4t-bit signature

I can't give a definitive answer on this, but I believe for a while it was unclear how long the hash should be to give the appropriate security level. But, as I said above, the $4t$-bit signature size is probably most common.

I propose three independent changes, which keep the same signature size.

The first two are applied in EdDSA. I'm not sure what the point of the third is. The values $e$ and $v$ are public, why do we care about their structure?

• If modern expositions are $4t$ rather than $3t$ because "for a while it was unclear how long the hash should be", then it means the original exposition was unsafe (or perhaps could not be proven safe?); this change must have some justification, since it has a significant size drawback! Also: If the signature is $(x,y)$ rather than $(h(x,m),y)$ in the original, it has size $4t$ for an EC group where $x$ is $2t$, but is much larger ($>9t)$ with (the subgroup of order $q$ of) $\mathbb Z_p^*$ considered in the original; or perhaps that $x$ is truncated to $2t$ or $t$ before hashing?
– fgrieu
Jun 25 '17 at 22:07
• @fgrieu No, the original was (and is) okay. The scheme has a proof of security in the Random Oracle Model, so it wasn't clear what kind of hash you should actually use to instantiate this. The safe thing to do would be to use a $2t$-bit output, providing collision resistance, but this was shown unnecessary, so that a $t$-bit hash suffices. At least that is the way this paper neven.org/papers/schnorr.pdf describes it. Jun 25 '17 at 23:40
• @fgrieu Indeed, I mostly have the EC case in the back of my mind. For other groups compression could be much more valuable! Again, do note that compression is not the holy grail here as it also has drawbacks (i.e. no batch verification). Jun 25 '17 at 23:42
• Many thanks for the Neven/Smart/Warinschi paper! It mentions and tries to address just what's bugging me: "It is hard however to extract from (Pointcheval/Stern's) proof any guidance on the output length of H, because it only considers hash functions mapping into $\mathbb Z_q$". My tentative modification 3 is trying to do this while keeping $e=h_v(x,m)$ of $t$ bits, by using $h_v'\circ h_v$ with output in the full $\mathbb Z_q$.
– fgrieu
Jun 26 '17 at 6:20

Partial answer to my own question, after some weeks of research based on the question's expanded bibliography.

History

The Schnorr signature scheme was initially proposed with a $t$-bit hash ($3t$-bit signature), at a time when security proof where the exception. [PS96] proved security for a $2t$-bit ideal hash assuming the underlying discrete logarithm is hard, using their newly introduced Forking Lemma; that's possibly why contemporary expositions and [ISO14888] use this hash width. [BN06] define a General Forking Lemma, and apply it to a multi-user setup with $2t$-bit random oracle.

• Outlines a proof of security (in the Random Oracle Model) for $t$-bit ideal hash using the General Forking Lemma and other results of [BN06].
• States proof of a necessary (in ROM) and sufficient (in the Generic Group Model) security condition for the hash: random-prefix preimage (RPP) and random-prefix second preimage (RPSP) security (which differ from first preimage and second preimage by a random prefix imposed by the experiment); their proof is stated for $2t$-bit hash and $\log_2(q)\ge2t$ (and then is tight); or $t$-bit hash and $\log_2(q)\ge3t$.
• States security (without claim of proof nor specific $\log_2(q)$ bound) for a Merkle-Damgård hash of $2t$-bit truncated to $t$-bit (noting that a $t$-bit Merkle-Damgård hash was previously shown to have a best $3t/4$-security w.r.t. RPP).

[Br15] exhibits a pathological $t$-bit RPP and RPSP hash that makes $\log_2(q)=2t$ insecure, noting that it does not invalidate anything in [NSW09].

[Be15] independently points that some claimed security proofs (not in the question's bibliography) in a multi-user setup turned out to be incorrect, and states that starting the hashed data with a fixed-length representation of the public key is a safe workaround.

[KMP16] further dissects the security in different models, citing many other source; and shows that the problem noted in [Be15] can be essentially repaired, allowing signature in a multi-user setup without access to the public key.

[ISO14888] standardizes SDSA, EC-SDSA, and EC-FSDSA, with standard $2t$-bit hashes and $\log_2(q)\approx2t$. SDSA stands for Schnorr Digital Signature Algorithm (with reference to [Sc89b] [Sc91]), EC for Elliptic-Curve variants, F for Full. EC-SDSA exists in two variants, using as the first component of the signature $h(\Pi_X\|\Pi_Y\|m)$ (with reference to [Sc91]) or $h(\Pi_X\|m)$ (with reference to [NSW09]). EC-FSDSA uses $\Pi_X\|\Pi_Y$ as the first component of the signature (with reference to [Sc91], even though I find that only in the authentication protocol; that's the variant described as the natural starting point in CurveEnthusiast's answer).

Wrapup

The Schnorr signature scheme has no identified technical drawback compared to its competitors. However, as put by ETSI TS 119 312 V1.2.1 (2017-05)

Due to former patent issues (the U.S. Patent 4,995,082 expired in February 2008) Schnorr signatures are not commonly used.

The original Schnorr signature scheme with $t$-bit hash as a component of the signature and a group where the DLP is hard is proven secure in the Random Oracle Model for an ideal hash (believed including practical unbroken $2t$-bit hashes truncated to $t$-bit); and in the Generic Group Model with a RPP and RSPP hash but with $\log_2(q)\approx3t$ (thus $4t$-bit signature); there is no known break for practical hashes and $\log_2(q)\approx2t$ (thus $3t$-bit signature).

The scheme is proven secure with $2t$-bit ideal hash; and in the Generic Group Model with a RPP and RSPP hash and $\log_2(q)\approx2t$ (thus $4t$-bit signature).

Replacing the random generation of $r$ by a deterministic one as in the question's improvement 1 has become the academically accepted practice (it is neither considered nor explicitly forbidden by [ISO14888]).

In a multi-user setup, starting hashing with a fixed-size representation of the public key is recommendable.

• You can also show tight multi-user security of Schnorr without key-prefixing as proven by Kiltz et al. in Crypto 16: eprint.iacr.org/2016/191 Jul 16 '17 at 6:15