About random self-reducibility of DDH

Question

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.

Answer 1

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.