### Unique Rabin-Williams Signature Scheme Decryption

Lynn Margaret Batten and Hugh Cowie Williams

##### Abstract

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)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Rabin-WilliamsCRTSignature Scheme.
Contact author(s)
lynn batten @ deakin edu au
History
Short URL
https://ia.cr/2019/915

CC BY

BibTeX

@misc{cryptoeprint:2019/915,
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{https://eprint.iacr.org/2019/915}},
url = {https://eprint.iacr.org/2019/915}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.