# Does Linear Cramer-Shoup have pseudo-random ciphertexts?

"Linear Cramer-Shoup" is defined on pages 4 and 5 of $\:$ eprint.iacr.org/2007/074.pdf .

Are the ciphertexts in Linear Cramer-Shoup computationally indistinguishable from uniform
under a chosen-ciphertext attack? $\:$ (We can assume without loss of generality either that
$M$ is the identity element or that $M$ is a a random element unknown to the adversary.)

This is not homework, and is relevant to a Zero Knowledge
Proof of Knowledge protocol I'm thinking about.

-
Note: $\:$ I am asking whether the ciphertexts are indistinguishable from (a) uniform (tuple of group elements), $\:\:$ not whether they are indistinguishable from each other. $\;\;$ (That is proven in the paper.) $\hspace{1 in}$ –  Ricky Demer Mar 17 '13 at 20:11

The security claim on page 5 of the Linear Cramer-Shoup paper is that their modified scheme is CCA secure, which is weaker than the IND-CCA2 security of the original DDH based Cramer-Shoup scheme. However, from the outline of the security proof, it seems the author actually means the LCS scheme is CCA2 secure.

Also note the first sentence on page 6:

"Clearly, if $A$ has a different advantage in guessing the bit $b$ when $B$ is run with a Linear tuple $(g_1,g_2,g_3,g_1^{r_1},g_2^{r_2},g_3^{r_1+r_2})$ and when $B$ is run with a random tuple $(g_1,g_2,g_3,g_1^{r_1},g_2^{r_2},\eta)$, we obtain a distinguisher for the Linear problem."

The cipher text $(u_1,u_2,u_3,e,v)$ consists of the last three elements of such a linear tuple, plus a blinded message $e$ and a verifier $v$.

Since $u_1 = g_1^{r_1}$ and $u_2 = g_2^{r_2}$ and $r_1, r_2$ are selected at random, these two values are trivially indistinguishable from uniform, because they are uniform. Since $u_3 = g_3^{r_1 + r_2}$, this value is indistinguishable from uniform by the Linear assumption.

The blinded value $e$ is proven to be "independent of the view of the adversary", which I interpret as being indistinguishable from uniform. The proof is interesting. Basically, it is based on the following derived problem:

Given $(g^s,g^t,g^{sa},g^{tb},g^{a+b},g^{ad+be+cf})$ and any number of points on the "plane" $P(x,y) = g^{xd+ye+(x+y)f}$ except $P(a,b)$, output yes if $c = a + b$, no otherwise.

The uniformity of $v$ might be derived using the same technique. Set $g = g_3, g^z = g_1, g^w = g_2$. We then have:

$v^\prime = g^{r_1z(x_1+\alpha{y_1}) + r_2w(x_2+\alpha{y_2}) + r_3(x_3+\alpha{y_3})}$, where $v^\prime = v \iff r_3 = r_1 + r_2$.

Clearly, if $r_3$ is selected uniformly at random, $v^\prime$ is also uniform, so if you are unable to tell if $r_3 = r_1 + r_2$, you are unable to distinguish $v$ from uniform.

-
Hi Henrick. Did you read the proof? In page 5, Shacham constructed a DLIN solver B from an IND-CCA2 distinguisher A. –  xagawa Mar 17 '13 at 14:03
Yes, but I was stumped by the fact that the author didn't make the corresponding security claim in the above paragraph. If you argue this is a mere terminology issue, I stand corrected. –  Henrick Hellström Mar 17 '13 at 17:18
The OP is not asking about IND-CCA2 security. The OP wants to know if the ciphertexts are computationally indistinguishable from uniform random. That's not implied by IND-CCA2 (you can have IND-CCA2, but not uniform random ciphertexts). –  D.W. Mar 18 '13 at 1:06
Is there an implied "One can easily generate a different ciphertext that (with high probability) is valid if and only if the challenge is a valid ciphertext."? $\:$ If no, then I don't see why what I was asking about is obvious. –  Ricky Demer Mar 18 '13 at 11:36
@RickyDemer: It is obvious that if the adversary chooses a cipher text completely at random, there is a high probability that the (legitimate) decryptor will fail the verification of $v$. If the adversary is able to detect that, the answer to your question is obviously "no", and I assumed you knew that already. However, if the adversary is unable to detect if a legitimate cipher text is failed or passed, both $e$ and $v$ will, afaict, be indistiguishable from uniform. –  Henrick Hellström Mar 18 '13 at 12:04
show 5 more comments