ElGamal vs. Schnorr vs. ECDSA vs. ...

Here's Schnorr's CRYPTO 89 signature system, except that I've replaced
the multiplicative group with an elliptic-curve group:

* The signer's secret key is a 256-bit integer n.

* The signer's public key is nB, where B is the standard base point
on a standard elliptic curve, specifically Curve25519.

* Given a message m, the signer picks a random 256-bit integer z,
computes r = SHA-256(zB,m), computes s = z + rn mod q where q is
the order of the base point, and sends the signed message (m,r,s).

* Given (m,r,s), the verifier checks that r = SHA-256(sB-rnB,m).

Some notable features of Schnorr's system, compared to (e.g.) ElGamal's
1984 signature system:

* Schnorr doesn't need any inversions mod q. This is a time-saver
with no disadvantages.

* Schnorr includes the random point zB as a hash input, rather than
computing, e.g., r = zB + SHA-256(m). This slows down verification
slightly (especially in parallel contexts) but can save space, as
discussed below.

* Schnorr transmits the hash output r. The alternative is to transmit
the hash input zB: the signer sends (m,zB,s) and the verifier
checks that sB = zB + SHA-256(zB,m) nB. Typically zB is longer than
r; replacing zB with r is now a well-known space-saving feature.

More detailed discussion of the second feature: Schnorr claimed without
proof that, thanks to the hash randomization, security of his signature
system relies only on what's now called ``target collision resistance''
(which is clearly sufficient for other types of signatures, as Naor and
Yung had pointed out in their 1986 UOWHF article) rather than full
collision resistance.

Schnorr suggested taking advantage of this by using a rather small hash
output---only about b bits for b-bit security, rather than the usual 2b
bits---to save space in signatures. Many papers claim that a complete
Schnorr signature takes 4b bits, but that's not true; Schnorr used 3b
bits. (The Boneh-Lynn-Shacham ``short'' signatures use 2b bits.)

One can complain that SHA-256(zB,m) doesn't adequately spread the
randomness of zB through the hashing of m, and that it would be better
to do something like SHA-256(zB,m xor zBzBzB...). The 1995 MDx-MAC paper
by Preneel and van Oorschot discusses these issues in much more detail.

You can find Schnorr's construction, some of Schnorr's observations, and
some of the Preneel-van Oorschot observations repeated without credit in
the recent Halevi/Krawczyk ``randomized hashing'' papers.

---D. J. Bernstein, Professor, Mathematics, Statistics,
and Computer Science, University of Illinois at Chicago
.

Relevant Pages

  • Another look at DLP based short signatures
    ... By DLP based signatures I refer to a class of digital signature schemes such as DSA, Schnorr and ElGamal with, among a couple of others, the following properties: ... Yuliang Zheng described in his "signcryption" paper how to cut the size of r to half the size of s by using a Schnorr based signature scheme with a keyed hash function. ...
    (sci.crypt)
  • Re: rsa implementation question
    ... > There is a notion of blocks in many public-key ciphers, ... It's not about decrypting to sign, encrypting to ... as it would mean that you'd have to find hash collisions. ... I generate a signature for a string "some string" with SHA. ...
    (comp.lang.python)
  • how to verify signature with DSACryptoServiceProvider
    ... computer) and DSACryptoServideProvider for signature of the hash (my ... signed hash to the end of the encrypted file. ... int securedSaltLength = bReader.ReadInt32; ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Sign with RsaCryptoService Provider Verify with win32 Crypto A
    ... Normally the signature should contain ... hash), so I think the .Net version of the code always put the hash id into ... What flags are you using in CryptSignHash and CryptVerifySignature ... I specify CRYPT_NOHASHOID in CryptSignHash and CryptVerifySignature ...
    (microsoft.public.platformsdk.security)
  • Crypto API and Windows 98 SE
    ... I have written a DLL in VB6 that performs key pair decrypt operations ... followed by a key pair signature verification. ... Dim lngReturnValue As Long ... Dim hHash As Long 'the handle to the hash object ...
    (microsoft.public.platformsdk.security)