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.