Rabin-Williams scheme

ID: rabin-williams-scheme

The Rabin-Williams scheme is a family of modified Rabin cryptosystem constructions using a modulus with distinct prime numbers and . These congruences make sign and doubling adjustments useful for producing quadratic residues before taking modular square roots. In signature variants, the private integer factorization permits root extraction while the public verification uses squaring.
The arithmetic mechanism can be seen without fixing a full message encoding. For a unit modulo , exactly one of is a quadratic residue modulo both primes: the two signs change both Legendre symbols, while multiplication by changes only one of them. For the toy modulus and , the adjustment has square root , since .
A complete digital signature scheme must additionally specify message hashing or redundancy, the selected root, and how the adjustment is encoded and verified. The congruence calculation alone is not such a scheme. A specific modified-Rabin message-recovery construction is given in the primary handbook, rather than being identical to raw four-root Rabin encryption.[ref]

New to topics? Read the docs here!