A protocol for two distant parties to agree on a random bit without trusting either party to announce an unverified coin toss. In the Rabin-Williams scheme, a publicly committed square hides which of two half-interval roots the sender selected. The other party guesses a digit distinguishing those roots; subsequent root and factor revelations verify the completed exchange. The protocol's fairness relies on prescribed randomness and the difficulty of finding a second root; it does not force a party to complete communication.
Use the square-root encryption convention called the Rabin-Williams scheme in the Cambridge course notes. Choose distinct large primes , keep them secret, and publish . A message block is encrypted as
Usually require ; otherwise the message itself reveals a factor. For a quadratic residue modulo , Euler criterion gives , so is a square root. Compute both signs modulo each prime, then combine the four sign choices by the Chinese remainder theorem. For a unit ciphertext there are four roots modulo . Message redundancy identifies the intended root; squaring alone does not identify it uniquely.
To reduce integer factorization to recovery of square roots, choose uniformly from , compute , and ask the alleged decoder for any root of . Conditional on , the secret is uniform among its four roots, even if the decoder deterministically chooses . With probability , . Then the signs agree modulo one prime and disagree modulo the other. Since
the greatest common divisor factors . Independent trials require an expected two successful oracle calls. If a trial's chosen is not a unit, already factors . This establishes the computational equivalence between factorization and inversion of the squaring map; it does not claim that learning any partial information about a formatted message is equivalent to full inversion.
For coin flipping by telephone, Alice publishes with its factorization secret. Bob chooses uniformly a unit with and sends . Alice computes the two roots in this half interval, selects a binary digit in which they differ, and announces a guess for that digit of Bob's . Bob reveals ; Alice verifies its range and square, and their common bit records whether her guess was correct. Alice then reveals , so Bob verifies the primes, product, and differing digit.
Conditional on , Bob's original root is equally likely to be or , so Alice's guess succeeds with probability . Bob cannot change his answer to the other half-interval root without finding a nontrivial second square root, which would factor by the argument above. Thus, assuming factorization is hard and the prescribed sampling and completed exchange are followed,
The revealed factors make the completed transcript checkable. The protocol does not prevent a party from aborting communication.
Rabin cryptosystem Created 2026-09-24 Updated 2026-11-05
The Rabin cryptosystem uses modular squaring with public modulus , where and are distinct odd prime numbers kept secret. The raw encryption map sends a message representative to
Knowing the prime factorization lets the receiver compute modular square roots modulo each prime and combine them by the Chinese remainder theorem. For a message coprime to , its ciphertext has exactly four roots modulo , corresponding to the two sign choices modulo each prime. A full encryption scheme therefore needs a specified message encoding or other rule to select the intended root; raw modular squaring by itself is four-to-one on the units.[ref]
For example, and give . Its four roots are modulo . The relation to integer factorization is especially direct: two roots that differ by more than an overall sign reveal a nontrivial factor through a greatest common divisor. The Rabin-Williams scheme is a more specific variant, rather than another name for every Rabin cryptosystem.