Welcome to the resource topic for 2019/915
Title:
Unique Rabin-Williams Signature Scheme Decryption
Authors: Lynn Margaret Batten, 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.
ePrint: https://eprint.iacr.org/2019/915
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .