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 and . Let . Bob also chooses a number such that the Legendre symbols . The public key consists of the numbers and , 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 and whose product is . Bob is to keep the knowledge of and secret.
Encryption
The message to be sent by Alice is either = 0 or = 1. Before the encryption, Alice chooses a random number such that . Using Bob’s public key, Alice calculates the ciphertext by using the following encryption scheme.
The ciphertext is sent to Bob by Alice.
Decryption
Once Bob receives the ciphertext , he computes the Legendre symbol . The plaintext is recovered according to the following scheme.
More on Goldwasser-Micali
Recall that and with and unknown except to Bob. Bob is in a position to make use of this private information to determine whether the received ciphertext is a quadratic residue. Note that a number is a quadratic residue modulo if and only if is a quadratic residue modulo and is a quadratic residue modulo . Once Bob receives the ciphertext , he can check whether is a quadratic residue modulo and then modulo . If is a quadratic residue modulo both and , then is square modulo and the plaintext is 0. If the ciphertext is a quadratic nonresidue modulo one of and , 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.
Thus, all Bob has to do to recover the plaintext from the ciphertext 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 .
During the entire exchange, Eve the eavesdropper can see the numbers , (the public key) and the ciphertext . When the plaintext is = 0, the ciphertext is a quadratic residue modulo , i.e., is a square. When the plaintext is = 1, the ciphertext is a quadratic nonresidue modulo . If Eve can determine whether the ciphertext is a quadratic residue modulo , she would know the plaintext . 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 if the two prime factors of 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 , she can obtain the single bit that was transmitted.
Because the modulus is composite, evaluating the Jacobi symbol would not reveal the information on the plaintext. This is because the symbol will always be 1 regardless the the value of the ciphertext, as shown below.
Examples
Example 1
The public key is = 80,549,389 and = 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 = 0 or = 1 for illustration. Alice chooses the random number = 70,254,916. The following calculates the encryption.
Thus, if the plaintext is = 0, the ciphertext is = 1,370,266 and if the plaintext is = 1, the ciphertext is = 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 = 8147 and = 9887. He then computes the following Legendre symbols depending on the received ciphertext.
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 and , she would need to solve one of the following equations (depending on the ciphertext) if she wants to uncover the plaintext.
Solving these equations is precisely the quadratic residuosity problem (discussed here). Note that evaluating the Jacobi symbol would not help. The following Jacobi symbols are evaluated here. Both are shown to be 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, , , , and .
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 and are ciphertexts corresponding to the two bits and , respectively, then modulo will be the ciphertext for the bit . Here, the operation 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, where = 5309 and = 7639. Then = 40,555,451. The number = 25,841,451. The pair of numbers and represents Bob’s public key.
Example 2
In this example, Alice wishes to send Bob a bit of = 0. She chooses the random number = 19,873,118. The ciphertext is then modulo .
Subsequently, Alice sends another bit = 1 to Bob. This time she uses the random number = 35,378,670. The ciphertext is then modulo .
The product of the two ciphertext is modulo . If Bob were to decrypt the result , he would evaluate the Legendre symbol using Euler’s criterion as follows:
The Legendre symbol is -1. Thus the ciphertext corresponds to a plaintext bit of 1, which is . Thus, multiplying the two ciphertexts gives the same ciphertext that would correspond to a ciphertext produced from encrypting .
Example 3
In this example, Alice is to send two separate bits of 1, say, = 1 and = 1. The ciphertext for is denoted by . The ciphertext for is denoted by . We have . Thus, when we multiply the two individual ciphertexts and , the resulting ciphertext should correspond to a bit of 0. For , Alice uses the random = 27,288,758. For , Alice uses the random = 15,416,582. Here’s the calculation.
Let’s decrypt the ciphertext , a job performed by Bob.
This shows that the combined ciphertext is for a bit of 0, which is .
Dan Ma Goldwasser-Micali Cryptosystem
Dan Ma Homomorphic Encryption Algorithm
Daniel Ma Goldwasser-Micali Cryptosystem
Daniel Ma Homomorphic Encryption Algorithm
Dan Ma Quadratic Residuosity Problem
Daniel Ma Quadratic Residuosity Problem
2023 – Dan Ma