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

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?

-
The problem is that they do not have the same distribution. In fact the distributions are distinct. Otherwise decrypting would be impossible. –  Maeher Jan 16 '13 at 9:01
why don't they have the same distribution? they're both uniform distributions over the same group. –  Anh Jan 16 '13 at 9:21
You have assumed that $(g^x)^r$ is uniformly random. Unless you can cite a theorem or something like that, you'd have to prove this statement. –  mikeazo Jan 16 '13 at 12:19
Well $g^{xr}$ is in fact uniformly distributed. However, $(g^x,g^r,m\cdot g^{xr})$ is not. There is a simple distinguisher: Compute $x$ (this means computing the discrete log, but even a computationally unbounded adversary can obviously not distinguish a distribution from itself) Now youǘe got the secret key, so simply decrypt and trivially decide which distribution you are dealing with. –  Maeher Jan 16 '13 at 13:07
@Maeher is correct. What is amiss is that you are not considering all the values (that are functionally dependent on x,r,m) that you have available. As for a step-by-step proof, see: shoup.net/papers/games.pdf (Section 3). And read the whole paper if you want more intuition into how to structure proofs. –  PulpSpy Jan 16 '13 at 14:42

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.

-
This doesn't answer the question; it's not 'how does a reduction proof work', it's rather 'why doesn't this alternative proof method work'. Maeher's comment is the best answer: the distribution is not uniformly distributed. Each element within the ciphertext is uniformly distributed, however there are correlations between the elements, and hence overall the output is nonuniform. –  poncho Jan 16 '13 at 14:13
@poncho, I took the question to be more general ("Why is proof-by-reduction needed?") with ElGamal as solely an example. You are correct though in that I did not address the (sub)question. –  mikeazo Jan 16 '13 at 14:32