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 (alternative version).
[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.
- 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). - 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. - 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.