Re: [Hash] randomized hashes and DSA

"D. J. Bernstein" <> Thu, 18 August 2005 08:46 UTC

Received: from localhost.localdomain ([] by with esmtp (Exim 4.32) id 1E5g37-0001z8-CO; Thu, 18 Aug 2005 04:46:57 -0400
Received: from ([] by with esmtp (Exim 4.32) id 1E5g35-0001z0-OB for; Thu, 18 Aug 2005 04:46:55 -0400
Received: from (ietf-mx []) by (8.9.1a/8.9.1a) with ESMTP id EAA20016 for <>; Thu, 18 Aug 2005 04:46:53 -0400 (EDT)
Received: from ([]) by with smtp (Exim 4.43) id 1E5gcn-0000g4-3O for; Thu, 18 Aug 2005 05:23:50 -0400
Received: (qmail 25949 invoked by uid 1016); 18 Aug 2005 08:47:12 -0000
Date: 18 Aug 2005 08:47:12 -0000
Message-ID: <>
Automatic-Legal-Notices: See
From: "D. J. Bernstein" <>
Subject: Re: [Hash] randomized hashes and DSA
References: <> <>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
X-Spam-Score: 0.0 (/)
X-Scan-Signature: 0bc60ec82efc80c84b8d02f4b0e4de22
X-Mailman-Version: 2.1.5
Precedence: list
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>

Apparently some people think that it's a new idea to use H(r,m) instead
of H(m) in the ElGamal/Schnorr/DSA/etc. family of signature systems. In
fact, this idea was clearly stated by Schnorr in his CRYPTO 1989 paper,
page 244:

   In order to thwart the chosen message attack the function h(x,m) must
   be one-way in the argument m. ... It is not necessary that the
   function h(x,m) is collision-free with respect to m.

Every security issue for H(r,m) in this family of systems is also
present for H(m). The security bounds for H(r,m) in this context are at
least as good as the security bounds for H(m); see, in particular, the
Goh-Jarecki theorems in EUROCRYPT 2003. Nobody can seriously claim that
this use of r is a security problem.

There are problems with randomization:

   * It costs time.
   * It costs bandwidth for RSA signatures.
   * The security gains are purely speculative.
   * Nobody is willing to claim that the security gains are large (e.g.,
     that randomized MD4 is hard to break).

But it's not reasonable to claim that randomization _loses_ security.
There's nothing wrong with Schnorr's signature system.

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

Hash mailing list