    Next: Weak laws of large Up: Probabilistic Encryption Previous: Probabilistic Encryption   Contents

## The Goldwasser-Micali encryption system

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

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

Lemma 21 is a square mod if and only if it is a square mod and a square mod .

Lemma 22   Let . If is a square mod , . If is not a square, .

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.

Lemma 23 of the numbers from 1 to are squares mod . Take the numbers from 1 to and leave out those divisible by or by . Divide the remaining numbers into four groups according to whether they are squares or not mod and also mod . There are numbers in each group.

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.    Next: Weak laws of large Up: Probabilistic Encryption Previous: Probabilistic Encryption   Contents
Translated from LaTeX by Scott Sutherland
2002-12-14