📂Number Theory

Proof of the Goldwasser-Micali Probabilistic Key Cryptosystem

Buildup

Let’s name them Alice, Bob, and Eve from left to right. Alice and Bob are the parties exchanging messages, and Eve is the passive attacker interested in the message. The orange box represents information known only to Alice, the sky-blue box represents information known only to Bob, and the black box represents information that is public (also known to Eve).

Alice has a message $m \in \left\{ 0 , 1 \right\}$ that she needs to receive from Bob. $\displaystyle \left( {{ x } \over { y }} \right)$ represents the Jacobi symbol.

Algorithm ¹

Key Setup: Alice publishes a large prime $p$, $q$ user’s product $N=pq$ and $\displaystyle \left( {{ a } \over { p }} \right) = \left( {{ a } \over { q }} \right) = -1$ that meets the condition $a$.

---

Encryption: Bob selects a random $1 < r < N$ and calculates $c \equiv \begin{cases} r^2 &, m=0 \\ a r^2 &, m=1 \end{cases}$ to publish.

---

Decryption: Alice calculates $\displaystyle m = \begin{cases} 0 &, \left( {{ c } \over { p }} \right) = 1 \\ 1 &, \left( {{ c } \over { p }} \right) = -1 \end{cases}$. Since Eve realistically cannot know $p$, she cannot know $m$.

Explanation

The Goldwasser-Micali probabilistic key cryptosystem was developed by Shafi Goldwasser and Silvio Micali, who were awarded the Turing Award in 2012 for this achievement.

Regardless of the cryptosystem, if the set of plaintexts is small, an attacker might not decrypt but can create and compare ciphers directly, which might lead to a breach. For example, if the expected messages are ‘attack’, ‘defend’, ‘retreat’, then trying all three could decrypt the message.

Of course, this is an extreme example, and it should be understood as preventing attacks when guessing what the plaintext might be. However, to that extent, the cryptosystem becomes surprisingly robust. The set of plaintexts can be mapped one-to-one with natural numbers, and since natural numbers can be represented in binary form, a proof for a 1-bit plaintext $m \in \left\{ 0 , 1 \right\}$ is sufficient.

The term Probabilistic in the name does not actually refer to probability in the strict mathematical sense. From the attacker’s perspective, the answer is either $0$ or $1$, so theoretically, she has about $\displaystyle {{1} \over {2}}$ chance of guessing correctly. However, for a $n$ bit plaintext, the probability drops to $\displaystyle {{1} \over {2^n}}$. It’s not that the attacker can’t guess correctly, but that she won’t know if she did, hence the term probability. But, calculating $N=pq$ is not trivial because the prime factorization problem is formidable. This makes it a solid cryptosystem.

The proof is shockingly simple, not because it’s difficult or complicated, but because it’s easy and straightforward. Anyone who has studied number theory might have encountered the Legendre symbol and Gauss’s law of quadratic reciprocity, but the fact that such a practical idea could come from there is unbelievable. Mathematicians are indeed bright and particularly inventive in applied mathematics, but this is truly a masterpiece that spontaneously inspires admiration.

Proof

Decryption

Alice knows the prime factorization $N = pq$ of $N$, so she can calculate $\displaystyle \left( {{ c } \over { p }} \right)$.

---

Case 1. $m=0$

$$ \begin{align*} \displaystyle \left( {{ c } \over { p }} \right) =& \left( {{ r^2 } \over { p }} \right) \\ =& \left( {{ r } \over { p }} \right) \left( {{ r } \over { p }} \right) \\ =& 1 \end{align*} $$

---

Case 2. $m=1$

$$ \begin{align*} \displaystyle \left( {{ c } \over { p }} \right) =& \left( {{ a r^2 } \over { p }} \right) \\ =& \left( {{ a } \over { p }} \right) \left( {{ r } \over { p }} \right) \left( {{ r } \over { p }} \right) \\ =& \left( {{ a } \over { p }} \right) \\ =& -1 \end{align*} $$

■

Encryption

Case 1. $m=0$

$$ \begin{align*} \displaystyle \left( {{ c } \over { N }} \right) =& \left( {{ r^2 } \over { N }} \right) \\ =& \left( {{ r } \over { N }} \right) \left( {{ r } \over { N }} \right) \\ =& 1 \end{align*} $$

---

Case 2. $m=1$

$$ \begin{align*} \displaystyle \left( {{ c } \over { N }} \right) =& \left( {{ a r^2 } \over { N }} \right) \\ =& \left( {{ a } \over { N }} \right) \left( {{ r } \over { N }} \right) \left( {{ r } \over { N }} \right) \\ =& \left( {{ a } \over { N }} \right) \\ =& \left( {{ a } \over { p }} \right) \left( {{ a } \over { q }} \right) \\ =& (-1) \cdot (-1) \\ =& 1 \end{align*} $$

---

Since Eve also knows $N$, she could calculate $\displaystyle \left( {{ c } \over { N }} \right)$. However, regardless of what $m$ is, the result is always $\displaystyle \left( {{ c } \over { N }} \right) = 1$, so she cannot know what $m$ is. Therefore, she needs to solve the prime factorization problem $N=pq$ to calculate $\displaystyle \left( {{ c } \over { p }} \right)$. This is very difficult, so Bob can securely transmit the message $m$ to Alice.

■