9
$\begingroup$

In Section 8 of this, Lindell presents a construction of an oblivious transfer protocol which is secure in the malicious model under the following variant of the DDH assumption (page 53):

[F]or every probabilistic-polynomial time non-uniform distinguisher $D$ there exists a negligible function $\mu$ such that $$|\mathrm{Pr}[D(\mathbb{G},q,g_0,g_1,(g_0)^r,(g_1)^r) = 1] - \mathrm{Pr}[D(\mathbb{G},q,g_0,g_1,(g_0)^r,(g_1)^{r+1}) = 1]| \le \mu(n)$$ where $\mathbb{G}$ is a group of [prime] order $q$ with generators $g_0$, $g_1$.

It is then stated that this assumption "follows easily from the standard DDH assumption" using its random self-reducibility property (as described for example by Naor and Reingold).

As I understand it, random self-reducibility means that from any fixed instance we can generate a random one, which can then be solved by an assumed algorithm solving a random instance. Thus no particular instance can be harder than the average case, and so in particular the worst case is exactly as hard as the average case.

However, this does not seem to preclude a particular case from being easier than the average case, and in particular the case $(g^a,g^b,g^{a(b+1)})$, so I fail to see how the hardness of the average case (which is the "standard DDH assumption") implies the hardness of this particular case.

$\endgroup$
  • $\begingroup$ If worst case = average, how can any instance be easier? Wouldn't that make the average easier as well? I.e. if for some set max = mean, then they are all equal. $\endgroup$ – otus May 23 '16 at 10:04
  • 1
    $\begingroup$ @otus Well, if you generate a random instance, any particular instance occurs only with negligible probability, so I'm not sure the existence of weak instances contradicts "worst case = average case". $\endgroup$ – fkraiem May 23 '16 at 10:10
  • $\begingroup$ In an asymptotic sense at least. $\endgroup$ – fkraiem May 23 '16 at 10:11
  • $\begingroup$ Oh, right. It only means easy instances are negligibly rare. $\endgroup$ – otus May 23 '16 at 10:13
6
$\begingroup$

You are absolutely right! The random self-reducibility goes in the other direction, and this variant of the DDH assumption does not follow from it. I have no idea what the author was thinking when he wrote it :-). In any case, the paper has now been updated in ePrint and fixed. Thank you for catching this.

I include the proof of this variant here:

Consider the following DDH variant that states that for every probabilistic-polynomial time non-uniform distinguisher $D$ there exists a negligible function $\mu$ such that \begin{equation} \left|\Pr[D(\mathbb{G},q,g_0,g_1,(g_0)^r,(g_1)^r)=1] - \Pr[D(\mathbb{G},q,g_0,g_1,(g_0)^r,(g_1)^{r+1})=1]\right| \leq \mu(n) \label{eq:ddh} \end{equation} where $\mathbb{G}$ is a group of prime order $q$ with generator $g_0$, $g_1\in\mathbb{G}$ is a random group element, and $r\in\mathbb{Z}_q$ is randomly chosen. This assumption can be proven to be to be true if the standard DDH assumption holds. In order to see this, observe that by the standard DDH assumption \begin{equation} \left|\Pr[D(\mathbb{G},q,g_0,g_1,(g_0)^r,(g_1)^r)=1] - \Pr[D(\mathbb{G},q,g_0,g_1,(g_0)^r,(g_1)^s)=1]\right| \leq \mu(n) \label{eq:ddh1} \end{equation} where $g_1\in\mathbb{G}$ and $r,s\in\mathbb{Z}_q$ are randomly chosen. In addition, observe that the distribution over $(g_0,g_1,(g_0)^r,(g_1)^s)$ is identical to the distribution over $(g_0,g_1,(g_0)^r,(g_1)^{s+1})$. Thus, a straightforward reduction to the standard DDH assumption gives that \begin{equation} \left|\Pr[D(\mathbb{G},q,g_0,g_1,(g_0)^r,(g_1)^s)=1] - \Pr[D(\mathbb{G},q,g_0,g_1,(g_0)^r,(g_1)^{r+1})=1]\right| \leq \mu(n). \label{eq:ddh2} \end{equation} In order to see this, a distinguisher $D'$ receiving $(g_0,g_1,h_0,h_1)$ can run $D$ on $(g_0,g_1,h_0,h_1\cdot g_1)$. If $D'$ received $(g_0,g_1,(g_0)^r,(g_1)^r)$ then it generates a tuple of the form $(g_0,g_1,(g_0)^r,(g_1)^{r+1})$, and if $D'$ received $(g_0,g_1,(g_0)^r,(g_1)^s)$ then it generates a tuple of the form $(g_0,g_1,(g_0)^r,(g_1)^{s+1})$, which as we have mentioned is identical to $(g_0,g_1,(g_0)^r,(g_1)^s)$. Thus, if $D$ can distinguish with non-negligible probability in this last equation, then $D'$ can use $D$ to solve the standard DDH problem. Combining these last two equations, we obtain that the first equation (which is the DDH variant assumption) holds.

$\endgroup$

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.