You are looking at a specific version 20190813:220447 of this paper. See the latest version.

Paper 2019/915

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Rabin-WilliamsCRTSignature Scheme.
Contact author(s)
lynn batten @ deakin edu au
History
2019-08-13: received
Short URL
https://ia.cr/2019/915
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.