Timeline for Examine whether a hash function is collision-resistant
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 11, 2023 at 19:41 | answer | added | tonythestark | timeline score: -1 | |
| Dec 2, 2020 at 10:36 | review | Close votes | |||
| Dec 23, 2020 at 3:05 | |||||
| Dec 2, 2020 at 10:05 | vote | accept | Paris | ||
| Dec 2, 2020 at 9:57 | answer | added | ambiso | timeline score: 2 | |
| Dec 2, 2020 at 9:46 | history | edited | kelalaka | CC BY-SA 4.0 |
edited title
|
| Dec 2, 2020 at 9:46 | comment | added | kelalaka | Hint: if you swap the positions of $x_2$ and $x_3$ can you find new $\bar x_1$ and $\bar x_4$ that will result in the same hash? | |
| Dec 2, 2020 at 9:38 | comment | added | Paris | @Krystian What about the second? Is it correct to assume that if we easily found $y_1$, $y_2$ such that $h(g(y_1)) = h(g(y_2))$ then $g(y_1) = g(y_2)$ (almost surely)? | |
| Dec 2, 2020 at 9:29 | comment | added | Kris | @Paris: In the first reasoning you need to use properties of the function g(). For example, if g(x1||x2||x3||x4)=0 for all x (constant function) h1 would not be collision resistant but h could still be collision resistant. | |
| Dec 2, 2020 at 9:25 | history | edited | Paris | CC BY-SA 4.0 |
added 20 characters in body
|
| Dec 2, 2020 at 9:23 | comment | added | fgrieu♦ | One of the many nice things at crypto-SE (compared to usenet's sci.crypt) is that it's possible to edit questions and replace a term by a more accurate one. Update: that works in the title too! Hint: one way to solve a problem involving a statement is to prove that it's false by constructing a counterexample. Here you'd assume $h$ is collision-resistant, and nevertheless exhibit a collision for $h_1$. | |
| Dec 2, 2020 at 9:18 | comment | added | Paris | Yes, 'resistant' is a more accurate term. | |
| Dec 2, 2020 at 9:09 | history | edited | Paris | CC BY-SA 4.0 |
added 6 characters in body
|
| Dec 2, 2020 at 9:05 | comment | added | ambiso | Okay, I wasn't sure, because collision-resistant is the terminology I'm used to, since by the pigeon principle $h$ cannot be "free" from collisions. | |
| Dec 2, 2020 at 9:04 | comment | added | Paris | $h(x)$ is collision-free if it's computationally hard to find $x,x'$ such that $h(x) = h(x')$. In other words, an efficient algorithm (solving a $P$-problem) has negligible probability of finding such $x, x'$. | |
| Dec 2, 2020 at 8:59 | comment | added | ambiso | what do you mean by "collision-free"? | |
| Dec 2, 2020 at 8:55 | history | asked | Paris | CC BY-SA 4.0 |