Is Cramer-Shoup backdoorable?

Question

We recently had the question whether it's possible to have multiple private keys with one public key for the cramer-shoup cryptosystem.

There it was stated that finding such "secondary" private keys is possible if $log_{g_1}(g_2) \bmod q$ is known. However computing this discrete logarithm is infeasible as both $g$s need to be random.

But the description also mentions that shared group parameters are allowed, meaning a party A could generate the $g$s so other partys could use them.

Now let's assume this party A to be some standardization body, like NIST, getting the $g$s by somebody (for example the NSA). Now let's further assume that there exists some $a$ for which $g^a_1\equiv g_2 \pmod q$ holds and that the supplying party knows $a$.

Can the supplying party (knowing $a$) anyhow break the security of Cramer-Shoup (=IND-CCA2) if honest parties use the backdoored parameters?

Note: "honest parties" use the standardized group and choose their private keys following the specification and assume security of the parameters.

Answer 1

A Cramer-Shoup public key has the form:

$B = g_1^{b_1} g_2^{b_2}; \quad C = g_1^{c_1} g_2^{c_2}; \quad D = g_1^{d_1} g_2^{d_2}$

and an encryption of $m$ has the form:

$g_1^r, ~ g_2^r, ~ m B^r, ~ (CD^\mu)^r$

where $\mu$ is a hash of the first 3 components.

CCA security proof breaks down:

In the CCA security proof, you observe that if you know the private key then you can generate the challenge ciphertext as a function of $g_1^r$ and $g_2^r$ (mirroring how the receiver would actually decrypt), which gives:

$g_1^r, ~ g_2^r, ~ m [(g_1^r)^{b_1} (g_2^r)^{b_2}], ~ [ (g_1^r)^{c_1 + d_1 \mu} (g_2^r)^{c_2 + d_2 \mu} ]$

Then the first step of the proof is to replace $g_1^r, g_2^r$ with $g_1^{r_1}, g_2^{r_2}$ with $r_1, r_2$ random. This change is indistinguishable by DDH, but not if the discrete log of $g_2$ with respect to $g_1$ is known, as in your case. The rest of the proof follows from an information-theoretic argument.

Explicit CCA attack unclear:

Even though the proof seems to break down, I'm having trouble demonstrating an explicit attack on CCA security. You can definitely break the hybrids of the CCA security proof without even consulting the decryption oracle. But we know the scheme remains CPA-secure (see below), so this it's possible that there's a problem only in the proof while the scheme remains CCA secure (though I doubt that).

CPA security maintained:

Even if you give the adversary everything but $b_1$ -- including the discrete log of $g_2$ with respect to $g_1$ -- you can still argue that the scheme is CPA secure. That's because we still have $r, b_1$ chosen uniformly, so $g_1^{r b_1}$ is pseudorandom given $g_1^r$, $g_1^{b_1}$. In particular, the third ciphertext component (the only one that involves the plaintext) is pseudorandom.