Why is proof-by-reduction needed (for Elgamal proof of security, for example)?

Question

The textbook proof for Elgamal encryption basically reduces to the Decisional Diffie-Hellman assumption (DDH).

Elgamal: $Gen(.): x \xleftarrow{R} \mathbb{Z}_p$; $Enc(m,g^x): r \xleftarrow{R} \mathbb{Z}_p, U= m.(g^x)^r, V = g^r$; $Dec(U,V,x): m = U/V^x$.

Suppose I prove the secure of Elgamal (in the CPA security model) as follows:

Since $r$ is uniformly random, $(g^x)^r$ is also uniformly random. Thus, $m.(g^x)^r$ follows a uniform distribution. Given two message $m_0, m_1$ during the Challenge phase, the corresponding ciphertext $c_0$ and $c_1$ follow the same uniform distribution. Therefore, the advantage of the adversary is the same as distinguishing two identical distributions, which is 0.

Can someone tell me what is amiss in the proof above? Why is it (or isn't it) sufficient to show that the ciphertexts following a uniform distribution, i.e. indistinguishable from a truly random value?

Answer 1

Why is proof-by-reduction needed?

In general, reduction proofs are a very common thing in computer science. Specifically in cryptography, the reasoning goes something like this:

The general cryptographic community believes that problem $X$ is very difficult to solve. I have designed a new cipher $Y$ and want to convince the community that it would be hard to break. So, I assume that someone could efficiently break $Y$, then I show that using an efficient break of $Y$, someone could also solve problem $X$. Therefore, we can conclude that breaking $Y$ is at least as hard as solving $X$. Since general consensus is that $X$ is really hard to solve, $Y$ must be a secure cipher.

That is not the only way to prove security of a cipher. If I remember correctly, the proof of security for the one-time-pad does not follow this paradigm. It has, over time, however, proven to be a very good way to prove security of a cipher and has worked well in practice.

Can someone tell me what is amiss in the proof above? Why is it (or isn't it) sufficient to show that the ciphertexts following a uniform distribution, i.e. indistinguishable from a truly random value?

See Maeher's comment.

Answer 2

In addition to mikeazo's answer, what you are trying to do, is to replace the DDH problem with 'uniform distribution problem'. It seems legit, but not convincing as the proof is not based on a well studied problem. For instance, maybe the way $Gen(\cdot)$ operates does not confirm a uniform distribution. But, linking the scheme to DDH, which means using a DDH-secure $Gen(\cdot)$ function, the scheme is secure as long as DDH is not broken.

Answer 3

If r is random, in fact g^{xr} is not always random over the multiplicative group Z_p^{}. Note that g is a generator of Z_p^{} and p is an odd prime.

if x is also odd, then g^x will generate the whole group Z_p^{}, i.e., g^x is a generator as well. Therefore, is r is uniformly chosen from the set {1,2,...,p-2} (r should not choose p-1 since g^{p-1} is 1), then g^{xr} will be random over Z_p^{}-{1}={2,3,...,p-1}.

However, if x is even, say x=2, then g^x is no longer a generator and thus g^{xr} will not loop over the set {2,3,...,p-1} for r in the set {1,2....,p-2}.

Consider a toy example.

p=5, Z_p^{*}={1,2,3,4}, r is chosen from {1,2,3}. Let g=2, x=1, 2^2=4 mod 5, 2^3=3 mod 5, 2^4=1 mod 5. Then g^{xr}=2^{r} will loop over {2,3,4} for r in {1,2,3}. (Note that x is chosen as 1 for illustration purpose. In the real encryption, x should not choose 1.)

However, if g=2, x=2, then g^{xr}=2^{2r}=4^r will loop over {1,4} for r in {1,2,3}.