How can I show that the DDH problem is self-reducible?

Question

I have trouble to understand how I can show that the Decisional Diffie-Hellman problem (DDH) is self-reducible.

I found this as a description of a random self-reducible problem.

Given an instance I1, it can be solved as follows:
(a) transform I1 into a uniformly random instance I2
(b) solve I2 and
(c) transform the solution for I2 into a solution for I1

Can someone (try) to explain me how I can show that the Decisional Diffie-Hellman problem (DDH) is random self-reducible based on these 3 steps ?

Answer 1

What we have to show for random self reducibility is that we can reduce an efficient algorithm for solving an arbitrary (worst-case) instance to an algorithm that solves a random instance efficiently. Consequently, an efficient algorithm for the average case implies an efficient algorithm for the worst case. You already have outlined how this is technically done in your question and I'll show you a construction for the computational version of this problem.

Example CDHP

Let $G$ be a group (w.l.o.g. of prime order $p$) generated by $g$. The CDH is given two elements $g^a$ and $g^b$ and to  compute $g^{ab}$. 

Lets say we have a solver $\cal A$ for CDHP in $G$, then we can construct an algorithm $\cal B$ that uses $\cal A$ as an oracle and $\cal B$ solves any instance of the CDHP in $G$ with the same probability as $\cal A$ and only requires "a little" more time than $\cal A$ (see below the time required for the sampling of the elements and the extra arithmetic that has to be done).

It goes like this:

$\cal B$ receives $(u=g^a,v=g^b)$ as input and does the following:

1. Choose uniformly at random elements $x,y$ from ${\mathbb Z}_q$
2. Compute $u'=ug^x$, $v'=vg^y$ and run $\cal A$ on $(u',v')$
3. Take the output $w'$ of $\cal A$ and do the following: compute $w=w'\cdot u^{-y}\cdot v^{-x}\cdot g^{-xy}$

4. Output $w$ as solution to the CDHP for instance $(u,v)$.

   Observe that if $\cal A$ solves the CDHP then also $\cal B$ solves the CDHP, since then

   $w'=g^{(a+x)(b+y)=ab+ay+xb+xy}$ and thus

   $$w=g^{ab+ay+xb+xy}\cdot u^{-y}\cdot v^{-x}\cdot g^{-xy}=g^{ab+ay+xb+xy-ay-xb-xy}=g^{ab}.$$

Note that due to the "blinding" in step $2$, the instance for $\cal A$ is uniformly distributed and independent from the original instance to the CDHP $(u,v)$, i.e., a "fresh" random instance.

I only have argued informally and let the exercise to write the analysis down formally to you.

DDH

Having this example it should not be too hard to devise such a reduction for the DDH.