Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 ?

share|improve this question
@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

Your Answer


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

Browse other questions tagged or ask your own question.