# Key construction in the Full Cramer-Shoup cryptosystem

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?

• I don't understand your last sentence. What do you mean by “use the less private keys”? Could you give an example? – Gilles 'SO- stop being evil' Apr 22 '14 at 8:53
• Could we change the scheme? If so, there is a chance. – xagawa Apr 22 '14 at 9:39
• There are six serect keys ($x_1,x_2,y_1,y_2,z_1,z_2$)in this scheme, is it possible if we only use fewer keys ,such as ($x_1,x_2,y_1,y_2$), to modify the scheme, but it also aganst CCA-2. – user13076 Apr 22 '14 at 12:29
• Um, no, there's only one secret key in this scheme. $\:$ There are six secret exponents in this scheme. $\hspace{.41 in}$ – user991 Apr 22 '14 at 15:16
• It is less efficient to compute the exponents, is it practical in our life? Does this scheme exists some improvement yet？@Ricky Demer – user13076 Apr 23 '14 at 2:34

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.