Variants of the Rabin-Williams public-key signature system have, for twenty-five years, held the speed records for signature verification. Are these systems secure? There are many other signature systems of RSA/Rabin type. One can break each system by factoring the signer’s public key n or by breaking the system’s hash function H. Are there other attacks? This is not an idle concern: some RSA-type systems have been broken by embarrassing attacks that (1) are much faster than known methods to factor n and (2) work for every function H (or a large fraction of choices of H), given oracle access to H. Some systems have been proven immune to embarrassing attacks. For example, in the 1993 paper that popularized this line of work (along with the terminology “secure in the random-oracle model,” which seems to have engendered considerable confusion), Bellare and Rogaway proved the following security property for the traditional “FDH” form of exponent-e RSA: every H-generic attack on RSA-FDH can be converted (without serious loss of efficiency) into an algorithm to compute eth roots modulo n. Unfortunately, a closer look reveals that most of these proofs merely limit the embarrassment, without actually ruling it out. For example, the Bellare-Rogaway root-finding algorithm has only a 1/h chance of success, where h is the number of hash values seen by the FDH attack. Coron introduced a better algorithm having a 1/s chance of success, where s is the number of signatures seen by the FDH attack; but s can still be quite large. Randomized signatures, in which long random strings are prepended to messages before the messages are signed, allow much tighter proofs. For example, every H-generic attack on randomized exponent-e RSA (or Rabin’s 1979 signature system) can be converted into a algorithm to compute eth roots modulo n (or to factor n) with a good chance of success. But generating random strings takes time, and transmitting the strings consumes bandwidth. Can we do better?

A 2002 theorem of Coron is widely interpreted as saying that FDH is stuck at 1/s: tight proofs require randomization. The randomized “RSA-PSS” and “PRab” systems have tight security proofs and work around the bandwidth problem, but they still take time to generate long random strings, and they are incompatible with the fastest known verification techniques. A tight security proof by Katz and Wang allows much shorter random strings for some RSA variants but breaks down for Rabin-Williams. In my talk I’ll explain three state-of-the-art variants of the Rabin-Williams public-key signature system. All three variants have tight security proofs, and all three provide extremely fast signature verification. What’s most surprising is the FDH variant, which has a tight security proof despite hashing unrandomized messages; in the Rabin-Williams context, a minor technical assumption in Coron’s theorem turns out to be a major loophole.