2
$\begingroup$

I was reading the Cramer Shoup CCA2 secure encryption scheme. The scheme is as follows.

Public key = $(g_1, g_2, c, d, h, hk)$, where $c = g_1^{x_1}g_2^{y_1}$, $d = g_1^{x_2}g_2^{y_2}$, $h = g_1^z$, hk is hash key of a universal one-way hash function.

Secret key = $(x_1, y_1, x_2, y_2, z)$

Encryption(pk, m; r) = $(u_1, u_2, e, v)$, where $u_1 = g_1^r, u_2 = g_2^r, e = h^r.m, \alpha = \mathsf{Hash}(hk, (u_1, u_2, e)), v = c^r.d^{r\alpha}$.

In elgamal scheme, the ciphertext consists of only $u_1, e$ terms. I didn't fully understand the intuition behind the additional terms in the public key and ciphertext. What purpose is each term serving? What terms are eradicating CCA1 attack and what terms are eradicating CCA2 attack?

I came up with this simpler scheme, and couldn't find a CCA attack on this. Is this scheme secure?

Public key = $(g_1, c, d, h, hk)$, where $c = g_1^x$, $d = g_1^y$, $h = g_1^z$, $hk$ is hash key of a universal one-way hash function.

Secret key = $x, y, z$

Encryption(pk, m; r) = $(u_1, e, v)$, where $u_1 = g_1^r, e = h^r.m, \alpha = \mathsf{Hash}(hk, (u_1, e)), v = c^r.d^{r\alpha}$.

|improve this question
$\endgroup$
  • $\begingroup$ What have you done to study the proof of the CCA2 reduction theorem for Cramer–Shoup? What have you done to carry it over to a corresponding CCA2 reduction theorem for your simpler scheme? $\endgroup$ – Squeamish Ossifrage Jun 16 at 23:57
  • $\begingroup$ I read CS paper. Suppose adversary A breaks CCA2 security of the above scheme, they construct a reduction algo. B that breaks DDH problem on instance $(g_1, g_2, u_1, u_2)$. B samples $x_1, x_2, y_1, y_2, z_1, z_2$, sets the pk in a similar way to the original scheme, except that $h = g_1^{z_1}g_2^{z_2}$. When A asks for encryption query, B sends ciphertext $(u_1, u_2, u_1^{z_1}u_2^{z_2}m_b, u_1^{x_1+x_2\alpha}.u_2^{y_1+y_2\alpha})$. B responds to decryption queries using $z_1, z_2$. They prove that if $u_2$ is random, challenge ciphertext hides b. Otherwise, B imitates the original CCA2 game. $\endgroup$ – satya Jun 17 at 1:07
  • $\begingroup$ But the proof didn't give me an intuition about the work accomplished each term in public parameters and ciphertext. $\endgroup$ – satya Jun 17 at 1:08
  • $\begingroup$ Regarding the simpler encryption scheme, I couldn't prove it secure. Suppose the reduction algorithm receives $(g_1, g_2, g_3, g_4)$ as DDH challenge. It needs to create pk as in scheme. On challenge encryption query, it needs to set $u_1$ to $g_4$ and $h^r$ to $g_4^z$ so that $b$ is hidden when $g_4$ is random. But I don't know how to proceed after this. At the same time, I couldn't find a simple mauling attack on the scheme. $\endgroup$ – satya Jun 17 at 1:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.