Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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 ?

share|improve this question

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.

DDH

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

share|improve this answer
    
Ups, I read CDH. Should have finished the morning coffee before :/ –  DrLecter Mar 12 at 9:06
    
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. $\;$ –  Ricky Demer Mar 12 at 9:08
    
@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 :) –  DrLecter Mar 12 at 9:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.