# Why the contrapositive proves a given hash is collision resistant?

So I am working on a problem as follows, it's a pretty basic standard question that I think I figured out, but I am confused as to why it works out the way it does.

Essentially, we are given a hash function $H$ that is collision resistant and maps to a fixed output length.

We want to create a new hash $H'$ such that

$H'(n) = H(n)||x$

Where we say, $x$ is just a random string of a given arbitrary length $m$.

Now what I think is the right thing to do is to use the contrapositive to say, if $H'$ is not collision resistant, than we can build an adversary to work in time ε. Thus we can alter our adversary easily by just cutting off the last m bites to get an adversary to solve for $H$

My question is that why can't we just use a direct proof to solve this? Must we use a contrapositive? I believe that it has to do with proving something is secure is a lot harder than proving it isn't, but I'm unsure.

• You probably could use a direct proof for this, but why should you if a contrapositive one is so much easier? – SEJPM Mar 21 '17 at 11:50
• Any implication is logically equivalent to its contrapositive, so you could (always) rephrase the proof to not use the contrapositive — but it often makes it easier to formulate and understand the arguments in a proof. – yyyyyyy Mar 21 '17 at 12:34

## 1 Answer

The reason is that you are trying to make a statement about the hardness of a problem. You want to prove

A is hard $\Rightarrow$ B is hard

This is a statement about the non-existence of an easy solution. Every solution for A is hard. You want to show

every solution for A is hard $\Rightarrow$ every solution for B is hard

Constructively tackling this problem would require showing that ALL solutions for B are hard but you probably do not even know all solutions.

By inverting the problem you get

there is a non-hard solution for B $\Rightarrow$ there is a non-hard solution for A

which only requires a statement about all solutions of A. Which you happen to already have. Namely that there is no non-hard solution.

• why didn't you fusion your answers ? :) – Biv Mar 21 '17 at 13:16
• Is that a thing? I thought it might be easier to just create a new one and delete the other. – Elias Mar 21 '17 at 13:22
• Well the edit button is there for that ^^. :) – Biv Mar 21 '17 at 13:24