Re: Koblitz and Menezes: 'Another Look at "Provable Security"'

From: David Wagner (daw_at_taverner.cs.berkeley.edu)
Date: 11/06/04 

Date: Sat, 6 Nov 2004 22:02:12 +0000 (UTC)

D. J. Bernstein wrote:
>There's certainly some value---but there's also cost. In particular,
>because PSS scrambles its randomizer, it's incompatible with the fastest
>signature-verification algorithms.

Ahh, good point. I had forgotten about that.

>Fortunately, PSS isn't the state of the art. The security proofs, the
>weak assumptions, and the high speed can all be achieved simultaneously.
>See http://cr.yp.to/papers.html#rwtight.
>
>The crucial modification in signature systems was posted to sci.crypt in
>1997 by Barwood, and independently by Wigley. The security impact of the
>modification, in the claw-free-permutation-pair setting, was pointed out
>in 2003 by Katz and Wang; my paper adapts the Katz-Wang proof to Rabin.

I agree. Your scheme is my favorite instantiation of this line of
research. It is a shame that it is not better known (and a shame that
implementors seem to be so focused on RSA-based schemes, rather than
Rabin-based schemes).

Relevant Pages