3
$\begingroup$

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.

| improve this question | |
$\endgroup$
  • $\begingroup$ You probably could use a direct proof for this, but why should you if a contrapositive one is so much easier? $\endgroup$ – SEJPM♦ Mar 21 '17 at 11:50
  • $\begingroup$ 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. $\endgroup$ – yyyyyyy Mar 21 '17 at 12:34
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.