Goldwasser-Micali | Mathematical Cryptography

This is a discussion on how the Goldwasser-Micali cryptosystem can be used to send one bit of data securely. The Goldwasser-Micali cryptosystem is a public-key encryption algorithm developed by Shafi Goldwasser and Silvio Micali in 1982. It has the distinction of being the first probabilistic public-key encryption scheme. It also possesses a partial homomorphic capability, which is discussed and illustrated below.

Alice wishes to send Bob one bit of data, i.e., Alice wishes to send Bob the value of 0 or 1 using a public key cryptosystem. If the algorithm is deterministic in nature, there is a serious security issue with this exchange, i.e., Eve the eavesdropper can find out what the message is by encrypting both 0 and 1 and then comparing to what is sent by Alice to Bob. In fact, this problem exists for any cryptosystem that generates only a small set of possible plaintexts. All Eve has to do is to encrypt every possible plaintext using the public key from Bob and then try to find a match with the message being sent. Thus, a probabilistic encryption is called for so that the bit that is sent will appear random. We focus on one such algorithm called the Goldwasser-Micali cryptosystem.

The Goldwasser-Micali Cryptosystem

The major components of the Goldwasser-Micali cryptosystem are described below. In this presentation, Bob is the publisher of the public key and Alice is the party that encrypts the message to be sent to Bob using Bob’s public key. Bob is the party that has the knowledge of the private key allowing him to decrypt the message from Alice. Of course, Eve the eavesdropper can see all the information exchanged via an insecure channel but does not know the private key held by Bob.

Public Key
Bob chooses two large primes $p$ and $q$ . Let $N=p \times q$ . Bob also chooses a number $a$ such that the Legendre symbols $(\frac{a}{p})=(\frac{a}{q})=-1$ . The public key consists of the numbers $N$ and $a$ , which Alice can use to send one-bit to Bob. The public key is also available for Eve the eavesdropper to see.

Private Key
The private key consists of the two large primes $p$ and $q$ whose product is $N$ . Bob is to keep the knowledge of $p$ and $q$ secret.

Encryption
The message to be sent by Alice is either $m$ = 0 or $m$ = 1. Before the encryption, Alice chooses a random number $r$ such that $1<r <N$ . Using Bob’s public key, Alice calculates the ciphertext $c$ by using the following encryption scheme.

$\displaystyle c \equiv \left\{ \begin{array}{rl} r^2 \ \text{mod} \ N &\ \text{if } m = 0\\ a \cdot r^2 \ \text{mod} \ N &\ \text{if } m = 1 \end{array} \right.$

The ciphertext $c$ is sent to Bob by Alice.

Decryption
Once Bob receives the ciphertext $c$ , he computes the Legendre symbol $(\frac{c}{p})$ . The plaintext is recovered according to the following scheme.

$\displaystyle m = \left\{ \begin{array}{rl} 0 &\ \text{if } \displaystyle \biggl(\frac{c}{p} \biggr) = 1\\ 1 &\ \text{if } \displaystyle \biggl(\frac{c}{p} \biggr) = -1 \end{array} \right.$

More on Goldwasser-Micali

Recall that $N=p \times q$ and with $p$ and $q$ unknown except to Bob. Bob is in a position to make use of this private information to determine whether the received ciphertext $c$ is a quadratic residue. Note that a number $a$ is a quadratic residue modulo $N$ if and only if $a$ is a quadratic residue modulo $p$ and $a$ is a quadratic residue modulo $q$ . Once Bob receives the ciphertext $c$ , he can check whether $c$ is a quadratic residue modulo $p$ and then modulo $q$ . If $c$ is a quadratic residue modulo both $p$ and $q$ , then $c$ is square modulo $N$ and the plaintext is 0. If the ciphertext $c$ is a quadratic nonresidue modulo one of $p$ and $q$ , then the plaintext is a 1. However, the decryption can be carried out according to scheme in the preceding section. The following shows why the decryption scheme works.

$\displaystyle \biggl(\frac{c}{p} \biggr) = \left\{ \begin{array}{ll} \displaystyle \biggl(\frac{r^2}{p} \biggr)=\biggl(\frac{r}{p} \biggr)^2=1 &\ \text{if } m = 0\\ \displaystyle \biggl(\frac{a r^2}{p} \biggr)=\biggl(\frac{a}{p} \biggr) \times \biggl(\frac{r}{p} \biggr)^2=-1 &\ \text{if } \displaystyle m = 1 \end{array} \right.$

Thus, all Bob has to do to recover the plaintext $m$ from the ciphertext $c$ is to evaluate a Legendre symbol, which is an efficient algorithm. This is possible for Bob to do since he possesses the private key, which is the prime factorization of the modulus $N$ .

During the entire exchange, Eve the eavesdropper can see the numbers $N$ , $a$ (the public key) and the ciphertext $c$ . When the plaintext is $m$ = 0, the ciphertext $c$ is a quadratic residue modulo $N$ , i.e., $c$ is a square. When the plaintext is $m$ = 1, the ciphertext $c$ is a quadratic nonresidue modulo $N$ . If Eve can determine whether the ciphertext $c$ is a quadratic residue modulo $N$ , she would know the plaintext $m$ . This is precisely solving the quadratic residuosity problem (discussed here). At the root, the security of the Goldwasser-Micali cryptosystem is based the assumption that it is hard to determine of a number is a square modulo $N$ if the two prime factors of $N$ are unknown.

Note the difference between Bob and Eve. Bob uncovers the plaintext using the private key that he possesses. For Eve to obtain the plaintext, one possible way is to solve the quadratic residuosity problem. Of course, if she can factor the modulus $N$ , she can obtain the single bit $m$ that was transmitted.

Because the modulus $N$ is composite, evaluating the Jacobi symbol $(\frac{c}{N})$ would not reveal the information on the plaintext. This is because the symbol $(\frac{c}{N})$ will always be 1 regardless the the value of the ciphertext, as shown below.

$\displaystyle \biggl(\frac{c}{N} \biggr) = \left\{ \begin{array}{ll} \displaystyle \biggl(\frac{r^2}{N} \biggr)=\biggl(\frac{r}{N} \biggr)^2=1 &\ \text{if } m = 0\\ \displaystyle \biggl(\frac{a r^2}{N} \biggr)=\biggl(\frac{a}{N} \biggr) = \biggl(\frac{a}{p} \biggr) \times \biggl(\frac{a}{q} \biggr)=1 &\ \text{if } \displaystyle m = 1 \end{array} \right.$

Examples

Example 1
The public key is $N$ = 80,549,389 and $a$ = 34,382,465. Let’s go through each step in the Goldwasser-Micali process for Alice and Bob.

Alice chooses a message to be sent. For the purpose of this example, we can encrypt both $m$ = 0 or $m$ = 1 for illustration. Alice chooses the random number $r$ = 70,254,916. The following calculates the encryption.

$\displaystyle c \equiv \left\{ \begin{array}{ll} 70254916^2 \equiv 1370266 \ \text{mod} \ N &\ \text{if } m = 0\\ 34382465 \cdot 70254916^2 \equiv 26807757 \ \text{mod} \ N &\ \text{if } m = 1 \end{array} \right.$

Thus, if the plaintext is $m$ = 0, the ciphertext is $c$ = 1,370,266 and if the plaintext is $m$ = 1, the ciphertext is $c$ = 26,807,757.

Once Bob receives the ciphertext from Alice, he uses his knowledge of the secret key to decrypt. The secret key is the pair $p$ = 8147 and $q$ = 9887. He then computes the following Legendre symbols depending on the received ciphertext.

$\displaystyle \biggl(\frac{c}{p} \biggr) = \biggl(\frac{1370266}{8147} \biggr)=1$

$\displaystyle \biggl(\frac{c}{p} \biggr) = \biggl(\frac{26807757}{8147} \biggr)=-1$

If the value of the symbol is 1, Bob would know the one-bit plaintext is 0 and if the value of the symbol is -1, the plaintext is 1.

For Eve, without knowing $p$ and $q$ , she would need to solve one of the following equations (depending on the ciphertext) if she wants to uncover the plaintext.

$x^2 \equiv 1370266 \ \text{mod} \ 80549389$

$x^2 \equiv 26807757 \ \text{mod} \ 80549389$

Solving these equations is precisely the quadratic residuosity problem (discussed here). Note that evaluating the Jacobi symbol $(\frac{c}{N})$ would not help. The following Jacobi symbols are evaluated here. Both are shown to be 1.

$\displaystyle \biggl(\frac{c}{N}\biggr)=\biggl(\frac{1370266}{80549389}\biggr)=1$

$\displaystyle \biggl(\frac{c}{N}\biggr)=\biggl(\frac{26807757}{80549389}\biggr)=1$

Homomorphic Properties

The Goldwasser-Micali cryptosystem has the property that we can perform a mathematical operation on the encrypted data such that the results would be the same as the encrypted results that would be produced from encrypting the results of performing the same operation on the corresponding plaintexts. This property is called the homomorphic property and the mathematical operation in this instance is the Boolean logic operation called eXclusive OR (XOR), which is widely used in cryptography and other settings.

The operation XOR takes two input bits and produces one output bit in the following manner. If the bits are the same, the result is 0. If the two bits are different, the result is 1. More specifically, $0 \bigoplus 0=0$ , $0 \bigoplus 1=1$ , $1 \bigoplus 0=1$ , and $1 \bigoplus 1=0$ .

In general, a homomorphic encryption algorithm refers to an encryption algorithm that allows certain mathematical operations such as addition and multiplication to be performed on ciphertexts so that the results are the same as the ciphertexts that would be produced from encrypting the results of performing the same operations on the corresponding plaintexts.

For the Goldwasser-Micali encryption algorithm, the homomorphic property is limited to the XOR logical operation. So, the algorithm is an example of a partial homomorphic encryption algorithm. It is a partial homomorphic encryption algorithm in this sense: If $c_1$ and $c_2$ are ciphertexts corresponding to the two bits $m_1$ and $m_2$ , respectively, then $c_1 \cdot c_2$ modulo $N$ will be the ciphertext for the bit $m_1 \bigoplus m_2$ . Here, the operation $\bigoplus$ is the Boolean logic operation XOR described above. Thus, multiplying two ciphertexts produces the same result as encrypting the XOR of the corresponding two plaintext bits.

Homomorphic encryption algorithm has huge consequence for many business enterprises. The ability to perform computation on encrypted data means data processing can be outsourced to a third party vendor. If the third party vendor has the homomorphic capability, there will be no need to trust the third party vendor to properly secure the data. The third party vendor can then perform computation on the encrypted data without the need of the secret key, and thus privacy is not compromised. We now give examples to demonstrate the homomorphic encryption in the Goldwasser-Micali algorithm.

For the following two examples, $N=p \times q$ where $p$ = 5309 and $q$ = 7639. Then $N$ = 40,555,451. The number $a$ = 25,841,451. The pair of numbers $N$ and $a$ represents Bob’s public key.

Example 2
In this example, Alice wishes to send Bob a bit of $m_1$ = 0. She chooses the random number $r$ = 19,873,118. The ciphertext is then $c_1 \equiv r^2 \equiv 35,567,683$ modulo $N$ .

Subsequently, Alice sends another bit $m_2$ = 1 to Bob. This time she uses the random number $r$ = 35,378,670. The ciphertext is then $c_2 \equiv a \cdot r^2 \equiv 33955554$ modulo $N$ .

The product of the two ciphertext is $c_1 \cdot c_2 \equiv 35,567,683 \cdot 33955554 \equiv 17149549$ modulo $N$ . If Bob were to decrypt the result $c_1 \cdot c_2$ , he would evaluate the Legendre symbol using Euler’s criterion as follows:

$\displaystyle \biggl( \frac{17149549}{5309} \biggr)=17149549^{\frac{5309-1}{2}} \equiv -1 \ \text{mod} \ 5309$

The Legendre symbol is -1. Thus the ciphertext $c_1 \cdot c_2$ corresponds to a plaintext bit of 1, which is $m_1 \bigoplus m_2=0 \bigoplus 1=1$ . Thus, multiplying the two ciphertexts gives the same ciphertext that would correspond to a ciphertext produced from encrypting $m_1 \bigoplus m_2=0 \bigoplus 1=1$ . $\square$

Example 3
In this example, Alice is to send two separate bits of 1, say, $m_3$ = 1 and $m_4$ = 1. The ciphertext for $m_3$ is denoted by $c_3$ . The ciphertext for $m_4$ is denoted by $c_4$ . We have $m_3 \bigoplus m_4=0$ . Thus, when we multiply the two individual ciphertexts $c_3$ and $c_4$ , the resulting ciphertext should correspond to a bit of 0. For $c_3$ , Alice uses the random $r$ = 27,288,758. For $c_4$ , Alice uses the random $r$ = 15,416,582. Here’s the calculation.