3
$\begingroup$

In the lite version of Cramer-Shoup we have a group $G$ with generators $g_1$ and $g_2$, private key $a_1, a_2, b_1, b_2$, and public key $A = g_1^{a_1} g_2^{a_2}$, $B = g_1^{b_1} g_2^{b_2}$. Encryption works by picking a random integer $r$ and sending the tuple $(g_1^r, g_2^r, A^r m, B^r)$. When decrypting we check the $B^r$ portion of the ciphertext is correct and, if so, obtain $m$ by calculating the inverse of $A^r$ and multiplying $A^r m$ with it.

Consider the following formulation of DDH: for random group elements $g_1, g_2, u_1, u_2$ and random integer $r$, $(g_1, g_2, u_1, u_2)$ is indistinguishable from $(g_1, g_2, g_1^r, g_2^r)$. Cramer-Shoup lite can be shown to be IND-CCA1 secure under this assumption. The proof goes by employing a hypothetical CCA1 attacker $\mathcal{A}$ which breaks Cramer-Shoup lite to break DDH. Our challenge instance is a quadruple $(g_1, g_2, u_1, u_2)$. We simulate the IND experiment for $\mathcal{A}$ with our own generated private and public keys; thus we can also simulate its decryption oracle since we have full knowledge of the scheme's private key. When $\mathcal{A}$ commits itself to a message pair $m_0, m_1$, we send it one of this messages (randomly chosen) encrypted, but with $g_1^r$ replaced with $u_1$ and $g_2^r$ with $u_2$. Thus $\mathcal{A}$ receives $(u_1, u_2, u_1^{a_1} u_2^{a_2} m, u_1^{b_1} u_2^{b_2})$, which is a valid encryption iff $u_1 = g_1^r$ and $u_2 = g_2^r$ for the same exponent $r$. $\mathcal{A}$'s response (ciphertext is valid or not) is correct with non-negligible probability, so we can distinguish the DDH quadruples with non-negligible probability.

I am having trouble understanding why the argument fails for IND-CCA2. Is it because $\mathcal{A}$ can use $u_1$ and $u_2$ in subsequent decryption queries?

$\endgroup$
  • 2
    $\begingroup$ Given that it's secure for IND-CCA1 but not for IND-CCA2, I would guess the attack for an adaptive attacker exploits some homomorphism... $\endgroup$ – SEJPM Apr 21 '18 at 18:28
4
$\begingroup$

CS-lite has the same homomorphic properties as ElGamal. In particular, compontentwise product of $\textsf{Enc}(pk,m_1)$ and $\textsf{Enc}(pk,m_2)$ is a valid encryption of $m_1 m_2$ (and hence will decrypt properly):

$$(g_1^r, g_2^r, A^r m_1, B^r) \cdot (g_1^s, g_2^s, A^s m_2, B^s) = (g_1^{r+s}, g_2^{r+s}, A^{r+s} (m_1m_2), B^{r+s})$$

So a simple CCA2 attack is to request $\textsf{Enc}(pk,m)$ for an unknown $m$, multiply this ciphertext by a fresh encryption of 1, and ask the decryption oracle to decrypt the result (revealing $m$).

$\endgroup$

Your Answer

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

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