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 ?


1 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.


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

  • $\begingroup$ Ups, I read CDH. Should have finished the morning coffee before :/ $\endgroup$
    – DrLecter
    Mar 12, 2014 at 9:06
  • $\begingroup$ I thought you were doing CDH to make the OP do a little thinking on his own, because of suspicion that this question is homework. $\;$ $\endgroup$
    – user991
    Mar 12, 2014 at 9:08
  • $\begingroup$ @Ricky Demer it seems that I did this without being aware of it. But having these ideas it should be easy for the OP to derive the solution to his problem :) $\endgroup$
    – DrLecter
    Mar 12, 2014 at 9:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.