# Looking for a detailed example of proof by reduction

I'm looking for a very detailed example of proof by reduction. Say we have two or three protocols (that have been proven secure) and we construct a new protocol. We want to provide a proof of security for this new protocol.

For instance, we can consider the following simple example: we have a (secure) signature algorithm $D$ and a (secure) hash function $H$ and we construct the following signature algorithm (denoted $N$) that takes input the secrey key $sk$ for $D$ and a message $M$ :

• We compute $d=H(M)$;
• We compute $s=D.Sign_{sk}(d)$ and ouput $s$.

(We can deduce the verification algorithm)

This kind of new algorithm is not usefull (we add a hash function to a signature algorithm that has already a hash function embedded in it) but I think it can be used to show an example of proof by reduction.

So, we have an adversary $A$ that can break $N$ in time $t$, with $q$ queries and an advantage less that $\epsilon$. We want to show that:

• we can build an adversary $A'$ against $D$ that runs in time $t'$, with $q'$ queries and having an advantage $\epsilon'$

• we can build an adversary $A''$ against $H$ that runs in time $t''$ with $q''$ queries and having an advantage $\epsilon''$

What is a correct proof by reduction ? How to use $A$ to build $A'$ and $A''$ ? and what is the relation between the times $t$, $t'$, $t''$, the relation between the avantages, etc ?

-
@Minkus CNB It's not surprising that this looks like a homework. –  Dingo13 Mar 24 '14 at 13:36
Can the reduction use the oracle for $H$ and the oracle for $D$ to respond to queries from $N$ ? –  Dingo13 Mar 24 '14 at 17:23