I think we all know RSA. And of course we also know DJB (a.k.a. Daniel J. Bernstein).

Now some already have noticed that he has an opinion towards cryptographic questions.

In his 2008 paper ("RSA signatures and Rabin–Williams signatures: the state of the art" by Bernstein) on state-of-the-art signature schemes he documents the "evolution" of RSA and I get the impression he's advertising the usage of the rabin-williams (RW) cryptosystem with the optimizations mentioned in the paper.

Now (finally) my question:
As Rabin-Williams seems to have so many advantages over RSA (smaller keys, smaller signatures, faster verification, ...) why isn't it in widespread use and everyone still uses "old" RSA?

This seems a bit odd as the latest optimizations are dated as of 2003 (!) which is ten years ago and I think there's also the proof that square-root is equally hard as factoring and I think RW even reduces to FACTORING.


1 Answer 1


At first I want to cite Lindell and Katz book:

A "plain Rabin" encryption scheme, constructed in a manner analogous to plain RSA encryption, is vulnerable to a chosen-ciphertext attack that enables an adversary to learn the entire private key. Although plain RSA is not CCA-secure either, known chosen-ciphertext attacks on plain RSA are less damaging since they recover the message but not the private key. Perhaps the existence of such an attack on "plain Rabin" influenced cryptographers, early on, to reject the use of Rabin encryption entirely.

For RSA and Rabin systems encryption/decryption and signing/verification are similar, so I guess the Rabin digital signature system was rejected due to the same reasons as in the encryption case. But if you look at the IEEE or ANSI standards, you'll find that both RW and RSA systems are standardized. I also think, the RSA scheme became more popular as Rivest, Shamir and Adelman set up the "RSA Data Security" company, so they had more opportunities to implement their system in their security solutions and bring these solutions to customers.

Anyway, the reasons are more "historical" than "technical" and now it's easy to securely implement both signature systems. Nowadays cryptographers have been paying their attention to elliptic curves as the systems based on them usually provide the same or higher level of security, but are more effective in a number of applications. So it's unlikely that Rabin's system will have a second chance agaist RSA though it will be used in applications where the fast signature verification is the main requirement.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.