3. Blum and Goldwasser Encryption

Comparing to Goldwasser and Micali Algorithm, Blum and Goldwasser Encryption (short for BG) has fix expansion rate.

It combines a stream cipher and a Pseudo Random Number

3.1. Key Generation

• \(n=pq\) where \(p\equiv 3~mod~4\) and \(q\equiv 3~mod~4\). \(n\) is a Blum integer.

• compute two integers \(a, b\) using Extended Euclidean algorithm such that

\[ap + bq = 1\]

public key: \(n\)

private key: \((p, q, a, b)\)

3.2. Encryption

Bob gets Alice’s public key \(n\). \(k = \lfloor \log_2 n \rfloor\) and \(h = \lfloor \log_2 k \rfloor\).

Message \(m\) is then split into \(t\) segments and each segment is of of \(h\) bits.

Choose a seed \(x_0 \in QR_n\) (Simply choose a random \(r \in \mathbb{Z}_n^*\) and set \(x_0 \equiv r^2~mod~n\))

For \(i\) to \(t\) do:

\(x_i = (x_{i-1}^2 ~mod~n)\)

let \(p_i\) be the \(h\) least significant bits of \(x_i\)

\(c_i = p_i \oplus m_i\)

The ciphertext is \((c_1, c_2, \cdots, c_t, x_{t+1})\)

3.3. Decryption

\[\begin{split}&d_1 = ((p+1)/4)^{t+1}~mod~(p-1)\\&d_2 = ((q+1)/4)^{t+1}~mod~(q-1)\\&u = x_{t+1}^{d_1}~mod~p\\&v = x_{t+1}^{d_2}~mod~q\\&x_0 = vap + ubq~mod~n\end{split}\]

for \(i=1\) to \(t\) do:

\(x_i = (x_{i-1})^2~mod~n\)

\(m_i = p_i \oplus c_i\)