Re:Amulet – a short poem with a lucky SHA-256 hash
by readyplayeremma on Tuesday April 27, 2021 @10:20PM
(#26964712)
Isn't that cheating though? By controlling the hash function you can alter the function itself until your message will meet the requirements, even though someone later on would find it impossible to compute a new message that meets the same?
[ Parent
| on HN ]
Re:Amulet – a short poem with a lucky SHA-256 hash
by p1mrx on Tuesday April 27, 2021 @11:09PM
(#26965090)
Presumably, God could foresee the cryptographic flaws of any algorithm, and could therefore design a simpler secure hash function than any human. In this case, "secure" means that there exists no algorithm to compute a preimage faster than brute force.
This would be a "nothing up my sleeve" function, in contrast to something like https://en.wikipedia.org/wiki/Dual_EC_DRBG that cryptographers would identify as sketchy.
Hypothetical question: What is the Kolmogorov complexity of a secure 256-bit hash function?
Re:Amulet – a short poem with a lucky SHA-256 hash
by Y_Y on Wednesday April 28, 2021 @03:46AM
(#26966806)
Hence God must have computational power greater than a Turing machine, at least if he wants to prove His hash function minimises Kolmogorov complexity.
For a rough upper bound, there are some examples at [0], which could be less than 100 characters of C (once golfed).