Timeline for Examine whether a hash function is collision-resistant
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 12, 2023 at 20:25 | comment | added | ambiso | h1 is not CR because a counterexample exists: you can give a CR h (of any structure) and two inputs that collide. The proof attempt can help you find out what that counterexample may look like. @tonythestark | |
| Feb 11, 2023 at 19:07 | comment | added | tonythestark | @cisnjxqu I am a little confused with the conclusion. At the start of the answer you are saying that h1 is not collision resistant . At case 2.1 , you say that you cannot construct a collision from this. Therefore I guess, if $g(x^a) = g(x^b)$ then x= x', but that contradicts the initial hypothesis, that $x^a \neq x^b$ so ,from that you conclude that h1 is not collision resistant? | |
| Dec 2, 2020 at 11:16 | comment | added | Paris | @kelalaka My question was focused on the verification of the method for proving that a hash function is collision-resistant. Unfortunately, the example I gave was not on point. I wasn't seeking the 'solution' to this specific example, but rather an elaboration on the reasoning. | |
| Dec 2, 2020 at 10:35 | comment | added | kelalaka | @cisnjxqu there is no remove, it is on the history of the answer and the OP already got it :). In any case, the HW question need not be answered. We had long chat conversions for some OPs to be consistent with our current policy. If you don't like the current policy you can vote against it or write another answer so that the community can upvote or downvote. bests. | |
| Dec 2, 2020 at 10:30 | comment | added | ambiso | @kelalaka I have removed the counter example, which was likely the solution to the homework. I can remove the complete answer if so desired. However, I feel like seeing how the proof would break down can help you in identifying why something is not true (and this proof would not have fit into the comments). There were also some issues with the askers attempt at proving the statement, so they can learn from the proof attempt laid out here. Do you think it is acceptable to leave the answer as it is now? | |
| Dec 2, 2020 at 10:27 | history | edited | ambiso | CC BY-SA 4.0 |
deleted 693 characters in body
|
| Dec 2, 2020 at 10:18 | comment | added | kelalaka | As far as I can see this is homework and per our policy, we only provide hints for those in the comments. | |
| Dec 2, 2020 at 10:09 | comment | added | Paris | Thanks! One quick last question: if for $h_1$ we had something like: $$h_1(x_1 || x_2 || x_3 || x_4) = h(h(x_1||x_2) || h(x_3 ||x_4))$$ is it valid to apply my second method and yield $y_1 = y_2$? (I'm asking because I want to know if this method works for proving a function collision resistant.) | |
| Dec 2, 2020 at 10:05 | vote | accept | Paris | ||
| Dec 2, 2020 at 9:57 | history | answered | ambiso | CC BY-SA 4.0 |