The Goldwasser-Micali encryption system

As in many previously discussed systems, the person receiving messages chooses two primes ($\sim100$ digits) $p,q$ and announces $n=pq$. This system is concerned with whether, for a given number $a$, there is $x$ with ${x^2}\equiv{a}\hbox{ (mod }{n})$. Such $a$ are called squares or (in most books and papers) quadratic residues. For technical reasons, when we refer to squares mod $n$, we will exclude $a$ which are divisible by $p$ or $q$. The following facts are easy to prove, in some cases using primitive roots.

Lemma 20   If $a,b$ are squares, then $ab$ is a square. If $a$ is a square and $b$ is not a square, then $ab$ is not a square.

Lemma 21   $a$ is a square mod $n$ if and only if it is a square mod $p$ and a square mod $q$.

Lemma 22   Let $h=\frac{p-1}{2}$. If $a$ is a square mod $p$, ${a^h}\equiv{1}\hbox{ (mod }{p})$. If $a$ is not a square, $a^h{\equiv}-1$.

This implies that, if $p$ and $q$ are known, it is easy to decide whether $a$ is a square. The encryption system depends on the assumption (called QRA in the paper [p. 294]) that this problem is very difficult if $p,q$ are unknown.

Lemma 23   $1/2$ of the numbers from 1 to $p-1$ are squares mod $p$. Take the numbers from 1 to $n$ and leave out those divisible by $p$ or by $q$. Divide the remaining $(p-1)(q-1)$ numbers into four groups according to whether they are squares or not mod $p$ and also mod $q$. There are $(p-1)(q-1)/4$ numbers in each group.

The numbers which are not squares mod $p$ and also not squares mod $q$ are called pseudo-squares. Example: If $p=5$, $q=7$, the squares mod 35 are 1, 4, 9, 16, 29, 11 ($29{\equiv}8^2$, $11{\equiv}9^2$; note we don't include 25 and 14, because they're divisible by $p,q$). The pseudo-squares must be congruent to 2 or 3 mod 5 and to 3, 5, or 6 mod 7. Thus the pseudo-squares are 17, 12, 27, 3, 33, 13.

The encryption system is primarily concerned with the union of the set of squares and pseudo-squares-- this set is unfortunately denoted both by $Z^1_n$ (p. 291) and by $Z^{{}+1}_n$. Since exactly half the members of $Z^1_n$ are squares, the crude idea of saying ``this is a square'' all the time will only be right half the time. (QRA) says that no algorithm that runs in a reasonable amount of time can do much better than this. [the precise definitions of ``reasonable'' and ``much better'' are what require the concepts of circuits of size $k$ and ``$\epsilon$-approximating'']

In addition to announcing $n$, the person receiving messages announces one pseudo-square $y$. To send a sequence of 0's and 1's, the sender converts them into numbers as follows: for each number in the sequence, an $x$ is chosen at random. 0 is converted into $x^2$ mod n, 1 is converted into $yx^2$. Each 0 or 1 in the sequence can be converted (depending on the choice of $x$) into one of $(p-1)(q-1)/4$ different numbers. If the message is of length 500 (about one line of ordinary text), and $p,q\approx10^{100}$, the message can be encoded into $(1/4)10^{100000}$ different possible ciphertexts.

By Lemma 20, 0's are converted to squares, 1's are converted to pseudo-squares. Since the receiver knows $p,q$, Lemmas 21 and 22 show he can efficiently decode the message.

In the subsequent sections, we will give the essential ideas of Goldwasser & Micali's proof that (assuming QRA) this system will prevent the adversary from obtaining any partial information about the plaintext.