# Looking for examples for “proof by reduction”

Im looking for examples for a proof by reduction. For example:

Let $A=(Gen, H)$ be a hash function. We define a new Hash function $A'=(Gen',H')$ with

Gen=Gen'

$H'_s(x)=H_s(H_s(x))$

It should be shown that if A is collision resistant, then A' is collision resistant too.

• I DONT LOOK FOR A SOLUTION FOR THIS QUESTION! *

Im looking for an idea how to construct a reduction so that i can solve this problem on my own.

-
(Gen, H) $\:$ seems like it would be a hash family, rather than a hash function. $\hspace{1.5 in}$ –  Ricky Demer Nov 25 '12 at 12:07
@Ricky: You are (formally) right. I have no idea how to add an upper s to H;-) But it is correct: in the line with H'(x)=H(H(x)) there are upper s missing on H. In "Katz/Lindell: Introduction to modern cryptography (Page 129)" (Gen, H) is called a Hash function in the definition; but its mentioned in the text that it is a familiy of Hash functions and s picks one function. –  twallutis Nov 25 '12 at 12:19
I may run the danger to be a bit out of topic but this is an interesting approach on rigorous proofs by reductions usually employed by cryptographers. It criticizes the too much effort on proofs by reductions which sometimes doesn't take into account all the attacker's window and consequently "tends to kick dust to eyes" –  curious Nov 26 '12 at 22:58
Also known as a keyed hash function. –  Paŭlo Ebermann Nov 29 '12 at 19:01
Did you find your solution? If so, please add it as an answer, so this question is more complete. Also, if one of the answers here has helped you, consider accepting it. –  Paŭlo Ebermann Nov 29 '12 at 19:03

In order to show that A' is collision resistant, you start with an attacker on the collision resistance of A' and show that you can build an attacker which will break the collision resistance of A. Specifically, you're given an oracle B' which will give values x' and y' such that H(H(x')) = H(H(y')) and you then need to construct an attacker B with the use of B' such that B returns two values x and y where H(x) = H(y).

-

When you try to reduce the security of one primitive (H') to the security of another primitive (H), you assume that there exists an adversary that could break H'. Then you show that existence of said adversary implies an adversary against H by describing an algorithm (the reduction) that uses the adversary to break H.

as a very simple example, consider the hash function $H$ and the hash function $H'(x) = H (x \oplus 1^{|x|})$ (with $\oplus$ being XOR and $1^{n}$ denoting the string of $n$ ones).

Now assume there exists an adversary $\mathcal{A}$ against the collision resistance of $H'$, i.e. there exists a ppt algorithm $\mathcal{A}$ that on input $s$ (and potentially a security parameter) will output $x$, $x'$ such that $H'(x)=H'(x')$ (with non-negligible probability).

Now your reduction needs to transform such a collision into a collision for $H$. If you look at how $H'$ is constructed, you can easily see that this can be done by computing $y = x\oplus 1^{|x|}$ and $y' = x'\oplus 1^{|x|}$ and outputting $y,y'$.

So your reduction is the algorithm that runs $\mathcal{A}$, flips all the bits in $\mathcal{A}$'s output and returns it. You can easily verify, that this reduction is successful whenever $\mathcal{A}$ is successful. As $H$ is collision resistant, the probability that $\mathcal{A}$ is successful must therefore be negligible and thus $H'$ is collision resistant.

So the problem you need to solve for your case is basically the question "How can I turn a collision of $H'$ into a collision of $H$?" When you think a moment about the way $H'$ is constructed, I am sure you will see an obvious way to do that.

-
Sorry for the delay; end-of-year stress;-) Here is my answer (so far i have no response; so i dont know if it is correct): Lets assume that A' is not collision-resistent. We write H'=H(y) instead of H'=H(H(x)). Then "collision-resistant" means: there exists y,y' with H(y)=H(y'), y<>y' When we now look at A, then H: {0,1}* -> {0,1}^l (arbitrary length -> fixed-length l) H': {0,1}^l -> {0,1}^l (fixed-length -> fixed-length) If H' is not collision-resistant, then we have y,y' with H(y)=H(y'). That is a special case of H and that would mean that H is not collision-resistant too. –  twallutis Dec 23 '12 at 14:58
The only problem: this solution looks too easy... –  twallutis Dec 23 '12 at 14:58