Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

"Linear Cramer-Shoup" is defined on pages 4 and 5 of $\:$ .

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.

share|improve this question
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
up vote 1 down vote accepted

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.

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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