# 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. Jan 16, 2013 at 9:01
• why don't they have the same distribution? they're both uniform distributions over the same group.
– Anh
Jan 16, 2013 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. Jan 16, 2013 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. Jan 16, 2013 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. Jan 16, 2013 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. Jan 16, 2013 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. Jan 16, 2013 at 14:32

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.

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}.

• This does not address the question. Whether or not $g^{xr}$ is uniform is irrelevant. The distributions are disjoint either way. Aug 2, 2021 at 10:29
• If g^{xr} is not random, then you cannot argue that the cipher text c=m g^{xr} perfectly hides the message m. This is why the argument from the original post is not correct. In other words, arguing the uniformity of the cipher text is not enough (in fact not correct here), that is why we need to find a different way (reduction to DDH) to prove the security. Aug 3, 2021 at 14:08
• No, even when $g^{xr}$ is uniform (as would be the case in a prime order group) , the argument breaks down. That's not the issue at all. Aug 3, 2021 at 17:53