<p>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}$.</p>

<p>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$.</p>

<p>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}$).</p>

CC BY-SA 3.0
2012-06-05T12:56:40.470Z
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?
Sadeq Dousti
CC BY-SA 3.0
2012-06-05T03:37:09.643Z
2012-06-05T05:56:55.337Z
2012-06-05T05:56:55.337Z
mikero
<p><a href="https://en.wikipedia.org/wiki/Decisional_Diffie-Hellman_assumption" rel="nofollow noreferrer">Decisional Diffie–Hellman assumption</a>, or DDH in short, is a famous problem in cryptography.
The DDH assumption holds on a cyclic group <span class="math-container">$(G,*)$</span> of (prime) order <span class="math-container">$q$</span>, if for a generator <span class="math-container">$g \in G$</span>, and for randomly chosen <span class="math-container">$a,b,c \in $</span>\mathbb{Z}_q$$, the following pairs are indistinguishable (for probabilistic poly-time algorithms):</p>
<ul>
<li>Type 1: <span class="math-container">$(g,g^a,g^b,g^{ab})$</span></li>
<li>Type 2: <span class="math-container">$(g,g^a,g^b,g^{c})$</span></li>
</ul>
<p>Now, assume that <span class="math-container">$G$</span> is a group on which DDH is hard, and consider the following <em>informal</em> question:</p>
<blockquote>
<p>Do we know of a probabilistic poly-time (PPT) algorithm, which gets a Diffie-Hellman pair, along with some <strong>partial</strong> information about <span class="math-container">$a$</span> (say, <span class="math-container">$a$</span> is odd), and can correctly output whether the input pair is &quot;Type 1&quot; or &quot;Type 2&quot; (with non-negligible probability)?</p>
</blockquote>
<p>By partial information, I mean a string <span class="math-container">$z$</span>, such that given <span class="math-container">$z$</span> and a Diffie-Hellman pair, no PPT algorithm can compute <span class="math-container">$a$</span>, with non-negligible probability.</p>
<hr />
<p>It's possible to formalize the above question. However, since the amount of notation required is tedious, I try to use an analogy.</p>
<p>A famous, non-standard cryptographic assumption is called <a href="https://doi.org/10.1007/978-3-540-28628-8_17" rel="nofollow noreferrer">Knowledge-of-Exponent</a> (KEA).</p>
<blockquote>
<p>For any adversary <strong>A</strong> that takes input <span class="math-container">$q$</span>, <span class="math-container">$g$</span>, <span class="math-container">$g^a$</span> and returns <span class="math-container">$(C,C^a)$</span>, there exists
an &quot;extractor&quot; <strong>B</strong>, which given the same inputs as <span class="math-container">$A$</span> returns <span class="math-container">$c$</span> such that <span class="math-container">$g^c = C$</span>.</p>
</blockquote>
<p>Intuitively, it states that, since the adversary cannot solve discrete log to obtain <span class="math-container">$a$</span>, the only way to output a pair <span class="math-container">$(C,C^a)$</span> is to &quot;know&quot; the exponent <span class="math-container">$c$</span> where <span class="math-container">$g^c = C$</span>.</p>
<p>Now, I'm asking a similar question, based on DDH (rather than discrete log): to distinguish &quot;Type 1&quot; and &quot;Type 2&quot; Diffie-Hellman pairs, should we &quot;know&quot; either <span class="math-container">$a$</span> or <span class="math-container">$b$</span>?</p>
<p>A bit more formally (but still not fully formal):</p>
<blockquote>
<p>Let <span class="math-container">$(G,*)$</span> be a group of prime order <span class="math-container">$q$</span>, and let <span class="math-container">$f(\cdot)$</span> be an arbitrary function whose output length is polynomial in the length of its input.
Pick <span class="math-container">$a$</span>, <span class="math-container">$b$</span>, and <span class="math-container">$c$</span> randomly from <span class="math-container">$\mathbb{Z}_q$</span>, and let <span class="math-container">$z=f(a)$</span>.
Toss a coin, and let <span class="math-container">$X = ab$</span> if the result is heads. Otherwise let <span class="math-container">$X=c$</span>.</p>
</blockquote>
<blockquote>
<p>For any PPT adversary <strong>A</strong> that takes input <span class="math-container">$(q,g,g^a,g^b,g^X,z)$</span>, and correctly decides between Type 1 and Type 2 with non-negligible probability, there exists
a PPT &quot;extractor&quot; <strong>B</strong>, which takes the same input as <strong>A</strong>, outputs either <span class="math-container">$a$</span> or <span class="math-container">$b$</span> (with non-negligible probability).</p>
</blockquote>

CC BY-SA 3.0
2012-06-03T16:06:40.723Z
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
Sasho Nikolov
CC BY-SA 3.0
2012-06-03T23:57:15.113Z
@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...
Sadeq Dousti
CC BY-SA 3.0
2012-06-04T01:07:46.833Z
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.
Sasho Nikolov
CC BY-SA 3.0
2012-06-04T11:43:58.733Z
@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$.
Sadeq Dousti
<cr.crypto-security><randomized-algorithms>
Deciding DDH based in partial information
Sadeq Dousti
# Deciding DDH based in partial information

(Asked by: username_0 on 2012-06-02)

[Decisional Diffie–Hellman assumption](https://en.wikipedia.org/wiki/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](https://doi.org/10.1007/978-3-540-28628-8_17) (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).

**Tags:** cr.crypto-security, randomized-algorithms
> **Comments:**
> **username_1**: 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  
> **username_0**: @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...  
> **username_1**: 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.  
> **username_0**: @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$.  

---

## 1 answers

### Answer by username_2 on 2012-06-05. Score: 2 | Accepted answer

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

> **Comments:**
> **username_0**: 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?  

---

