Score:3

Solving DDH from an ElGamal adversary

ps flag
bs-

Suppose an adversary wins IND-CPA against ElGamal,

  1. They're given public key $h=g^x$,
  2. Give a pair of messages $m = [m0,m1]$,
  3. Get back ciphertext $(a,b) = (g^r, g^{xr} \cdot g^{m[b]})$,

from which they determine $b$ with probability better than guessing (plus some negligible probability):

How can such an adversary be used to solve DDH?


Katz & Lindell (Introduction to Modern Cryptography), Shoup (Sequences of Games), et al., present game hopping proofs whereby an adversary's advantage in IND-CPA against ElGamal is transferred to an advantage against some ElGamal variant with uniformly-distributed group elements in place of ciphertexts: That's the aspect I don't follow; I'll hone in on my confusion below, other solutions may also exist. (Above and below I use $g^m$, whilst Katz & Lindell use $m$, this seems irrelevant.)


Katz & Lindell introduce adversary $\mathcal A$ with advantage $\epsilon(n)$ against IND-CPA of ElGamal, and consider a variant of ElGamal which outputs ciphertexts $(g^r, g^z \cdot g^m)$, i.e., a variant in which "the second component of the ciphertext...is a uniformly-distributed group element...independent of the message $m$...The first component of the ciphertext is trivially independent of $m$. Taken together...the entire ciphertext contains no information about $m$." This I understand. Next they assert the advantage of $\mathcal A$ against the ElGamal variant is $\frac{1}{2}$, I don't follow this inference.


Perhaps the inference is simply: The advantage of any algorithm $\mathcal B$ against the ElGamal variant is $\frac{1}{2}$. Intuitively, always returning zero results in success half the time, as does always returning one at the other extreme, as does any alternative strategy—the ElGamal variant delivers perfect secrecy.

poncho avatar
my flag
We don't give the answer to homework problems - if you show what you've tried, we'll give hints...
Maarten Bodewes avatar
in flag
What do you mean with " I don't follow that step.". I presume you don't *understand* it rather than not *perform* it? In that case it should not be in small caps, it should be in the question front and center as it shows effort. If possible, indicate *why* / which part you do not understand.
bs- avatar
ps flag
bs-
@MaartenBodewes, I wanted to ask a more general question; if an answer regurgitates Katz & Lindell or Shoup or ..., then I'd ask about the specific aspect I can't follow. That said, it's been a while, perhaps I'll add the detail, focus on the aforementioned proofs, fill in that gap.
Maarten Bodewes avatar
in flag
This site is about producing good answers to concise questions. Questions are not just there for the asker, they should generally be useable by others (the knowledgebase concept of StackExchange). Asking for something generic and then changing the question to something more specific is not the modus operandi that we try to pursue.
bs- avatar
ps flag
bs-
@MaartenBodewes, okay, understood. I've revised to focus on the narrower question. Thanks
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.