2. Goldwasser and Micali Algorithm

Whatever can be computable from the ciphertext about plaintext is also computable without ciphertext.

2.1. “bit-by-bit” encryption

Plaintext bit “0” is encrypted to a ciphertext in \(QR_n\),

Plaintext bit “1” is encrypted to a ciphertext in \(QNR_n\) such that \(C=yx^2\) and \(y\) is a random integer satisfying

\[(\frac{y}{p}) = (\frac{y}{q}) = -1\]

and \(x\) is uniformly chosen from \(\mathbb{Z}_N^*\).

Note that

\[\begin{split}&(\frac{C}{p}) = (\frac{yx^2}{p}) = (\frac{y}{p})(\frac{x^2}{p}) = -1 \cdot 1 = -1\\&(\frac{C}{q})=-1 \Rightarrow (\frac{C}{N}) = (-1)(-1) = 1\end{split}\]

So plaintext 1 is encrypted to a ciphertext in Pseudo Square mod \(N\).

But \(yx^2\) is \(QNR_n\).

Public key \((y, N)\) Private key \((p, q)\)

2.2. Decryption

If \(C\) is \(QR_n\), then \(b=0\), or it’s \(1\).

The method is to check \((\frac{C}{p})\) (\(p\) not \(n\)) see whether it’s \(\pm1\).

2.3. Security of GM

GM algorithm distributes plaintext bit 0 uniformly over \(QR_N\) and bit 1 over pseudo square mod \(N\).

2.4. How to choose \(y\)

  1. If \(n\) is a Blum integer s.t. \(p\equiv 3~mod~4\) and \(q\equiv 3~mod~4\), then \((-1)\) is a pseudo square mod \(n\).

  2. More general,

  • find \(a \in QNR_p\) and \(b \in QNR_q\)

  • apply Chinese Reminder Theory to \(a\) and \(b\) or Gauss’s Algorithm to compute the integer \(y \in [0, n-1]\) satisfying

\[\begin{split}y \equiv a~mod~p\\y \equiv b~mod~q\end{split}\]

So \(y \in QNR_p\) and \(y \in QNR_q\), i.e. \((\frac{y}{p})=(\frac{y}{q}) = -1\). We find \(y\), which is a pseudo square mod \(n\).

2.5. Performance of GM

The expansion rate of GM (ciphertext / plaintext) is \(\log_2 (n/2)\), it’s not small comparatively.