Key construction in the Full Cramer-Shoup cryptosystem

Question

The Full Cramer-Shoup Encryption scheme needs to choose six random numbers from $\mathbb{Z}_q$, which we denote them by $ x_1,x_2,y_1,y_2,z_1,z_2 $. Then the scheme hides these random numbers in the values $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}}$.

It is clear that the proportion of public key to private key is near to 1:2, because we can denote them by binary-tuple, which have two private keys and one public key, such as $((x_1,x_2),c)$, $((y_1,y_2),d)$, $((z_1,z_2),h)$.

Is it possible we use the less private keys to achieve the scheme, because my intuition tells me it have so many private keys?

Answer 1

Yes, if you allow to introduce other primitives into the PKE scheme. The Kurosawa-Desmedt scheme is an example whose secret key consists of four exponents in $\mathbb{Z}_q$.

Let us fix a group $\mathbb{G}$ of prime order $q$. Let $H$ be a secure hash function (TCR security).

Cramer and Shoup

Let us review the Cramer-Shoup scheme. As you wrote, the scheme is summarized as follows:

• $\mathrm{pk} = (c,d,h) = (g_1^{x_1} g_2^{x_2}, g_1^{y_1} g_2^{y_2},g_1^{z_1} g_2^{z_2}) \in \mathbb{G}^3$
• $\mathrm{sk} = (x_1,x_2,y_1,y_2,z_1,z_2) \in \mathbb{Z}_q^6$
• $\mathrm{ct} = (u_1, u_2, e, v)$, where $u_1 = g_1^r$, $u_2 = g_2^r$, $K = h^r$, $e = E_K(m)$, $\alpha = H(u_1,u_2,e) \in \mathbb{Z}_q$, and $v = c^r d^{r\alpha}$.

I omit the decryption algorithm. The scheme is IND-CCA2 secure if the DDH assumption holds and the SKE scheme ($E_K$) is one-time secure.

Kurosawa and Desmedt (CRYPTO 2004)

Kurosawa and Desmedt proposed a new PKE scheme with more compact secret key, as you wanted. The scheme is summarized as follows:

• $\mathrm{pk} = (c,d) = (g_1^{x_1} g_2^{x_2}, g_1^{y_1} g_2^{y_2}) \in \mathbb{G}^2$
• $\mathrm{sk} = (x_1,x_2,y_1,y_2) \in \mathbb{Z}_q^4$
• $\mathrm{CT} = (u_1, u_2, e, t)$, where $u_1 = g_1^r$, $u_2 = g_2^r$, $\alpha = H(u_1, u_2) \in \mathbb{Z}_q$, $v = c^r d^{r\alpha}$, $(k, K) = KDF(v)$, $e = E_K(m)$, and $t = MAC_k(e)$.

The scheme is IND-CCA2 secure if the DDH assumption holds, the SKE scheme ($E_K$) is one-time secure, and the MAC scheme ($MAC_k$) is secure. In this scheme, $v$ is used to extract keys for SKE and MAC, while in the CS scheme, $v$ is used to serve integrity of $u_1,u_2,e$. By this change, they successfully removed $h$ from the public key and $z_1,z_2$ from the secret key.

Others

There are tons of PKE/KEM schemes improving the Cramer--Shoup PKE/KEM scheme; efficient ones based on slightly stronger assumptions, say, GDH, HDH, and GHDH assumptions, and less efficient ones based on weaker assumption. Some researchers try to make schemes compact by employing the random oracles. You can find them by search engines, say, Google Scholar.