Rabin-Williams signature verification with 3072 bit keys is much faster than EdDSA signature verification of comparable security (when done in software). How much depends on care of coding, hardware, EdDSA parameters. Two data points:
- in the eBATS benchmarks for a skylake CPU,
ronald3072 signature verification (RSA with $e=3$ as an OpenSSL wrapper, by Bernstein) is nearly twice as fast as
ed25519 (archetypal EdDSA carefully optimized by Bernstein); I'm too lazy to see if/when Montgomery arithmetic (which does not pay in the context) is used by OpenSSL RSA signature verification; but since there are at least two modular multiplications in that, versus one in RW, the later can only be faster.
- in the Crypto++ benchmarks, RW 3072 verification can be extrapolated from RW 2048 verification times 2.25 (erring on the safe side), and is over 15 times faster than the fastest ECDSA signature verification (with pre-computation) quoted.
Even for an implementation using a $32\times32\to64$ multiplier, and classical algorithms, the modular multiplication dominating (properly coded) RW signature verification with 3072 bits key uses $k=96$ words, and about $2k^2$ (less than 20000) multiply-and-add. That can't be very long if coded carefully!
I think the theoretical principle of the scheme is right¹. Some details (like exactly what Full-Domain-Hashing is used, and perhaps additional constraints on primes) needs to be ironed out. And of course, the principle of rolling one's crypto is debatable (or just should be summarily rejected, in many real-life contexts).
As of implementation: the signature verification is reasonably easy to get right (as long as the correct number of redundancy bytes are checked), and is inherently immune to timing and other side-channel leakage (excluding fault injection), since nothing secret is involved. However lots of things can go wrong in signature generation, including side-channel (timing, power analysis..) and fault-injection attacks (against the later, at the very least, the signature should be verified independently of what generated it before being released).
¹ Late addition: yes, «The two high-order bits of the Skein output, which are not otherwise used, are used to select which of the four square roots to output» seems to match the Fixed unstructured Rabin–Williams studied and proven secure in Daniel J. Bernstein's Proving tight security for Rabin–Williams signature.