Paper 2019/915

Unique Rabin-Williams Signature Scheme Decryption

Lynn Margaret Batten and Hugh Cowie Williams


Abstract. The extremely efficient Rabin-Williams signature scheme relies on decryption of a quadratic equation in order to retrieve the original message. Customarily, square roots are found using the Chinese Remainder Theorem. This can be done in polynomial time, but generally produces four options for the correct message which must be analyzed to determine the correct one. This paper resolves the problem of efficient deterministic decryption to the correct message modulo $p^2q$ by establishing conditions on the primes $p$ and $q$ as well as on any legitimate message. We do this using the CRT modulo pq to find four roots. We show that the correct root (initial message) is the only one of these four which is in our allowed message set (it is in fact the smallest of the four integers) and which satisfies a quadratic equation modulo $p^2q$; no additional work is required to eliminate the others. As a result, we propose what we believe is now the most efficient version of R-W signature scheme decryption.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Rabin-WilliamsCRTSignature Scheme.
Contact author(s)
lynn batten @ deakin edu au
2019-08-13: received
Short URL
Creative Commons Attribution


      author = {Lynn Margaret Batten and Hugh Cowie Williams},
      title = {Unique Rabin-Williams Signature Scheme Decryption},
      howpublished = {Cryptology ePrint Archive, Paper 2019/915},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.