3. Cramer-Shoup Encryption

Cramer-Shoup Encryption Algorithm can defend Adaptive CCA. It is designed based on Decision D-H problem.

3.1. Key Setup

  • Cyclic Group \(G\) is of prime order \(q\) and \(q\) is a large prime number.

  • Hash function \(H(s) = a \in \mathbb{Z}_q\)

private key: \((x_1, x_2, y_1, y_2, z_1, z_2)\) all chosen randomly from \(\mathbb{Z}_q\)

public key: \(g_1, g_2\) chosen randomly from \(G\).

\[\begin{split}c = g_1^{x_1} g_2^{x_2}\\d= g_1^{y_1} g_2^{y_2}\\h=g_1^{z_1} g_2^{z_2}\end{split}\]

Recall that, a cyclic group of prime order \(p\) means each element is generated by \(g^{kp}\) where \(g\) is the generator and \(k=1, 2, 3, \cdots\).

3.2. Encryption

Plaintext \(m\) and a randomly chosen integer \(r \in \mathbb{Z}_q\), compute

\[\begin{split}&u_1 = g_1^r, u_2 = g_2^r\\&e=h^rm, v=c^rd^{r\alpha}\\&\alpha=H(u_1, u_2, c)\end{split}\]

Ciphertext is \((u_1, u_2, e, v)\)

3.3. Verification and Decryption

  1. Verification

Check if \(v = u_1^{x_1}u_2^{x_2}(u_1^{y_1}u_2^{y_2})^\alpha\). If yes, pass the verification; if no, reject.

  1. Decryption

\(m = eu_1^{-z_1}u_2^{-z_2}\)

3.4. Correctness

\[\begin{split}&u_1^{x_1}u_2^{x_2}=(g_1^r)^{x_1}(g_2^r)^{x_2} = (g_1^{x_1}g_2^{x_2})^r = c^r\\ &u_1^{y_1}u_2^{y_2}=(g_1^r)^{y_1}(g_2^r)^{y_2} = d^r\\ &[u_1^{x_1}u_2^{x_2}][u_1^{y_1}u_2^{y_2}]^\alpha = c^rd^{r\alpha} = v\end{split}\]

Also,

\[eu_1^{-z_1}u_2^{-z_2} = \frac{h^rm}{u_1^{z_1}u_2^{z_2}} = \frac{h^rm}{(g_1^{z_1}g_2^{z_2})^r} = \frac{h^rm}{h^r} = m\]

Idea of D-H is used in \(u_1^{x_1}u_2^{x_2} = c^r\).