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?

  • $\begingroup$ I don't understand your last sentence. What do you mean by “use the less private keys”? Could you give an example? $\endgroup$ Commented Apr 22, 2014 at 8:53
  • $\begingroup$ Could we change the scheme? If so, there is a chance. $\endgroup$
    – xagawa
    Commented Apr 22, 2014 at 9:39
  • $\begingroup$ 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. $\endgroup$
    – user13076
    Commented Apr 22, 2014 at 12:29
  • $\begingroup$ Um, no, there's only one secret key in this scheme. $\:$ There are six secret exponents in this scheme. $\hspace{.41 in}$ $\endgroup$
    – user991
    Commented Apr 22, 2014 at 15:16
  • $\begingroup$ It is less efficient to compute the exponents, is it practical in our life? Does this scheme exists some improvement yet?@Ricky Demer $\endgroup$
    – user13076
    Commented Apr 23, 2014 at 2:34

1 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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.