Timeline for How easy is it to know how many preimages an image might have, given that there's at least one (preimage, image) pair?
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 31, 2022 at 11:37 | vote | accept | Mark S | ||
| Aug 31, 2022 at 5:32 | answer | added | fgrieu♦ | timeline score: 2 | |
| Aug 31, 2022 at 1:49 | comment | added | Mark S | @kodlu but yes, truncating the last $m$ bits of SHA256, or any other hash function that could theoretically be implemented on a quantum computer, is where I was going. | |
| Aug 31, 2022 at 1:46 | comment | added | Mark S | @kodlu, yes, in general. On average each of the $2^m$ images should have two preimages, but some have one, some have none, some have more than two, I suspect following the Poisson distribution with $\lambda=2$. It’s interesting even if $\lambda=1$ or even $\lt 1$, but two-to-one on average is ok to start. How can I find a (preimage,image) pair where there is know to only be one preimage? Or even find one image which is known to only have one preimage, for a hash like SHA? I can do a birthday attack to find an image with at least two preimages, but can I do anything to find just one preimage? | |
| Aug 31, 2022 at 1:12 | comment | added | kodlu | So are you still talking about $m+1$ bits mapping to $m$ bits in the final question? Thus restricting SHA256 to $m+1$ bit inputs and truncating the output to $m$ bits? | |
| Aug 30, 2022 at 20:35 | history | edited | Mark S | CC BY-SA 4.0 |
added 153 characters in body
|
| Aug 30, 2022 at 19:35 | history | edited | Mark S | CC BY-SA 4.0 |
deleted 316 characters in body
|
| Aug 30, 2022 at 13:17 | history | asked | Mark S | CC BY-SA 4.0 |