8
$\begingroup$

Decisional Diffie–Hellman assumption, or DDH in short, is a famous problem in cryptography. The DDH assumption holds on a cyclic group $(G,*)$ of (prime) order $q$, if for a generator $g \in G$, and for randomly chosen $a,b,c \in $\mathbb{Z}_q$$, the following pairs are indistinguishable (for probabilistic poly-time algorithms):

  • Type 1: $(g,g^a,g^b,g^{ab})$
  • Type 2: $(g,g^a,g^b,g^{c})$

Now, assume that $G$ is a group on which DDH is hard, and consider the following informal question:

Do we know of a probabilistic poly-time (PPT) algorithm, which gets a Diffie-Hellman pair, along with some partial information about $a$ (say, $a$ is odd), and can correctly output whether the input pair is "Type 1" or "Type 2" (with non-negligible probability)?

By partial information, I mean a string $z$, such that given $z$ and a Diffie-Hellman pair, no PPT algorithm can compute $a$, with non-negligible probability.


It's possible to formalize the above question. However, since the amount of notation required is tedious, I try to use an analogy.

A famous, non-standard cryptographic assumption is called Knowledge-of-Exponent (KEA).

For any adversary A that takes input $q$, $g$, $g^a$ and returns $(C,C^a)$, there exists an "extractor" B, which given the same inputs as $A$ returns $c$ such that $g^c = C$.

Intuitively, it states that, since the adversary cannot solve discrete log to obtain $a$, the only way to output a pair $(C,C^a)$ is to "know" the exponent $c$ where $g^c = C$.

Now, I'm asking a similar question, based on DDH (rather than discrete log): to distinguish "Type 1" and "Type 2" Diffie-Hellman pairs, should we "know" either $a$ or $b$?

A bit more formally (but still not fully formal):

Let $(G,*)$ be a group of prime order $q$, and let $f(\cdot)$ be an arbitrary function whose output length is polynomial in the length of its input. Pick $a$, $b$, and $c$ randomly from $\mathbb{Z}_q$, and let $z=f(a)$. Toss a coin, and let $X = ab$ if the result is heads. Otherwise let $X=c$.

For any PPT adversary A that takes input $(q,g,g^a,g^b,g^X,z)$, and correctly decides between Type 1 and Type 2 with non-negligible probability, there exists a PPT "extractor" B, which takes the same input as A, outputs either $a$ or $b$ (with non-negligible probability).

$\endgroup$
  • $\begingroup$ that's probably a trivial answer for a crypto person, and it's not specific to DDH either, but doesn't Goldreich-Levin give you such an extractor if the advice is $(r, \langle r, a\rangle + \langle r, b\rangle \pmod{2})$, where $r$ is a random $n$-bit 0-1 vector, and $a$ and $b$ are represented as $n$-bit vectors as well $\endgroup$ – Sasho Nikolov Jun 3 '12 at 16:06
  • $\begingroup$ @Sasho: Thanks for the suggestion. I require the extractor to work for any $z$, not a specific one. In other words, given any partial info, if $A$ can distinguish the pairs, $B$ should be able to extract... $\endgroup$ – M.S. Dousti Jun 3 '12 at 23:57
  • $\begingroup$ Then I am confused about what "partial info" means. Why can't $z$ be $1$ if and only if $X = ab$? Sounds implausible that you can extract $a$ or $b$ using this one bit, but you can surely use it to distinguish between the two possible input distributions. $\endgroup$ – Sasho Nikolov Jun 4 '12 at 1:07
  • $\begingroup$ @Sasho: $z$ is partial info about $a$ and $b$, and it cannot depend on $X$. But you may have a point there. I changed the question, so that $z$ can depend only on $a$. $\endgroup$ – M.S. Dousti Jun 4 '12 at 11:43
2
$\begingroup$

Given the latest formulation of your question, this appears to be impossible. Consider the case where you have (families of) cyclic groups $\mathbb{G}$ and $\mathbb{H}$, where $\mathbb{G} \ne \mathbb{H}$ and we have a bilinear map $e: \mathbb{G} \times \mathbb{H} \to \mathbb{T}$. Under the XDH assumption we can suppose that DDH is hard in $\mathbb{G}$ and discrete log is hard in $\mathbb{H}$.

Let $g$ be a generator of $\mathbb{G}$ and $h$ be a generator of $\mathbb{H}$. Then define $f : \mathbb{Z}_{|\mathbb{G}|} \to \mathbb{H}$ as $f(a) = h^a$.

Now given $(g, g^a, g^b, g^X, z=f(a)=h^a)$, we can easily determine whether $X = ab$ by checking $e(g^b, z) \overset{?}= e(g^X,h)$. (You can also similarly verify the correctness of $z$ if you like.) Yet, it would seem unlikely that an extractor could extract $a$ or $b$ from such a tuple. Extracting $b$ is obviously equivalent to discrete log; if there is a distortion map from $\mathbb{H}$ to $\mathbb{G}$ (there cannot be one in the other direction) then extracting $a$ is equivalent to discrete log (in $\mathbb{H}$).

$\endgroup$
  • $\begingroup$ Great answer, thanks! Your answer helped me to get more focused on what I actually wanted: DDH, XDH, and the like do not propose that the corresponding assumption is hard on every group, but that there exists groups on which the associated problem is hard. So, my mistake was that I proposed my assumption on a general group. I have to specify the group (say, $G$ is a cyclic subgroup of $\mathbb{Z}_p^*$ of prime order q), or state the assumption in an existential form: There exists a group $(G,*)$, over which distinguishing results in extraction. Am I still lacking something? $\endgroup$ – M.S. Dousti Jun 5 '12 at 12:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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