Is this a good choice of a digital signature scheme?

Question

This is a concrete instantiation of Rabin-Williams signatures.

Specifically:

• The private key is 2 primes $p, q$.
• The public key is their product $N = pq$ and is approximately 3072 bits long.
• the hash function is Skein-512 with 3072 + 512 = 3584 bits output (Skein allows arbitrary output lengths).
• The padding scheme is deterministic full-domain-hashing, using the 3072 low-order bits of the Skein output.
• 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.

Example applications are CA signatures and distribution package manager signatures where signature verification speed is critical.

Questions:

• Is Rabin-Williams with 3072 bit keys faster or slower to verify than EdDSA?
• Is the scheme I gave secure? I think that it is an instantiation of a scheme that was proven secure in the random oracle model by Bernstein in this paper. While Skein is less used than other secure hash algorithms, it was an SHA-3 finalist and underwent a substantial amount of cryptanalysis.

Answer 1

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.