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

The numbers which are not squares mod and also not squares mod
are called *pseudo-squares*. Example: If , , the squares
mod 35 are 1, 4, 9, 16, 29, 11 (, ;
note we don't include 25 and 14, because
they're divisible by ). 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 (p. 291) and by . Since exactly half the
members of 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 and ``-approximating'']

In addition to announcing , the person receiving messages announces
one pseudo-square . 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 is chosen *at random*. 0 is converted into mod n, 1 is
converted into . Each 0 or 1 in the sequence can be converted
(depending on the choice of ) into one of different
numbers. If the message is of length 500 (about one line of ordinary
text), and
, the message can be encoded into
different possible ciphertexts.

By Lemma 20, 0's are converted to squares, 1's are converted
to pseudo-squares. Since the receiver knows , 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.

2002-12-14