Cryptographic System

Question

The Mad Hatter sets up what he believes is a zero-knowledge protocol. The integer n is the product of two large primes p and q and he wants to prove to the March Hare that he knows the factorization of n without revealing to anyone the actual factors $p$, $q$. He devises the following procedure:

March Hare chooses a random integer $x \pmod n$, computes $y \equiv x^2 \pmod n$, and sends $y$ to Mad Hatter. Mad Hatter then computes the square roots $z_i$ of $y$ modulo $n$ and sends $z = \min(z_i)$ to March Hare who verifies that $z^2 \equiv y \pmod n$. The Hatter offers to repeat this $10$ times with different values of $y$.

1. Should the March Hare be convinced that the Hatter knows $p$ and $q$?
   My guess: yes

2. Is March Hare able to use all this information to factor $n$? (In which cases this isn’t a zero knowledge procedure at all).
   My guess: no

3. The Knave of Hearts, who eavesdropped the entire sequence, recovers all ten values of $\{y_i,z_i\}$. Can he use this to obtain any information about $p$ and $q$?
   My guess: no

Does this look right?

Answer 1

Unless $x$ happens to be a multiple of $p$ or $q$, the number $y=x^2$ has four square roots modulo $pq$, namely the solutions for $z$ of the Chinese remainder systems $$ z \equiv \pm x \pmod p \\ z \equiv \pm x \pmod q $$ for each of the four combinations of $\pm$.

If the March Hare chooses $x$s at random, there's a pretty good chance that the response he gets back in at least one of the ten tries is not one of $x$ or $pq-x$. He then knows a $z$ that differs from his $x$ by some multiple of either $p$ or $q$, and therefore $\gcd(z-x,pq)$ will be one of the factors.

However, since the Hatter promises the numerically smallest square root, the Hare can do better than choosing $x$ completely at random. In fact, if he chooses $x$ between $\frac{n-\sqrt n}2$ and $\frac{n+\sqrt n}2$, then he can be certain that the $z$ he gets back will be useful to him (why?), and he only needs to ask a single question.

Does any of this help the Knave, though?

Answer 2

The answer to the second question is yes. The March hare could use this information to factor.

We have

$$x^2-y^2 \equiv (x+y)(x-y) \equiv 0 \pmod{ pq}$$

There is a chance that $p|(x+y)$ but $q\nmid (x+y)$ or that $q|(x-y)$ but $p\nmid (x-y)$. If one has some multiples of p one can calculate the gcd of these multiples to find p.

From this one can also deduce that the Mad Hatter knows p and q because he can derive it with this method in the same way as the Arch Hare.

So to 1 and 2 the answer is yes.

The knave can't use this information. If he could, then he could factor the system without the help of March Hare and Mad Hatter.

The Knave could select $19$ random integer in $\{1,...,n/2\}$. There is a $50:50$ chance that at least for $10$ of this $19$ integers $i$ is the the smallest root of $i^2$. Assume that this is the case for our $19$ integers. Then apply the factorization algorithm that knave uses to factor n by using $10$ intercepted numbers to all $10$-element subsets of the $19$ integers.

But it is not clear for an arbitrary sequence of number, because this algorithm exponentially with length of the series of numbers.