= Solution
Use the square-root encryption convention called the <Rabin-Williams scheme> in https://www.dpmms.cam.ac.uk/~twk10/Shan.pdf[the Cambridge course notes]. Choose distinct large primes $p,q\equiv3\pmod4$, keep them secret, and publish $N=pq$. A message block $m\in\{0,\ldots,N-1\}$ is encrypted as
$$
\boxed{c=m^2\pmod N.}
$$
Usually require $\gcd(m,N)=1$; otherwise the message itself reveals a factor. For a <quadratic residue> $c$ modulo $p$, <Euler criterion> gives $c^{(p-1)/2}=1$, so $c^{(p+1)/4}$ 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 $N$. Message redundancy identifies the intended root; squaring alone does not identify it uniquely.
To reduce <integer factorization> to recovery of square roots, choose $x$ uniformly from $(\mathbb Z/N\mathbb Z)^\times$, compute $c=x^2$, and ask the alleged decoder for any root $y$ of $c$. Conditional on $c$, the secret $x$ is uniform among its four roots, even if the decoder deterministically chooses $y$. With probability $1/2$, $y\not\equiv\pm x\pmod N$. Then the signs agree modulo one prime and disagree modulo the other. Since
$$
N\mid(x-y)(x+y),\qquad\boxed{1<\gcd(x-y,N)<N,}
$$
the <greatest common divisor> factors $N$. Independent trials require an expected two successful oracle calls. If a trial's chosen $x$ is not a unit, $\gcd(x,N)$ already factors $N$. 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 $N$ with its factorization secret. Bob chooses uniformly a unit $x$ with $0<x<N/2$ and sends $c=x^2\bmod N$. Alice computes the two roots $r_1,r_2$ in this half interval, selects a binary digit in which they differ, and announces a guess for that digit of Bob's $x$. Bob reveals $x$; Alice verifies its range and square, and their common bit records whether her guess was correct. Alice then reveals $p,q$, so Bob verifies the primes, product, and differing digit.
Conditional on $c$, Bob's original root is equally likely to be $r_1$ or $r_2$, so Alice's guess succeeds with probability $1/2$. Bob cannot change his answer to the other half-interval root without finding a nontrivial second square root, which would factor $N$ by the argument above. Thus, assuming factorization is hard and the prescribed sampling and completed exchange are followed,
$$
\boxed{\mathbb P(\text{Alice wins})=\mathbb P(\text{Bob wins})=\tfrac12.}
$$
The revealed factors make the completed transcript checkable. The protocol does not prevent a party from aborting communication.
Back to article page
