Re:Amulet – a short poem with a lucky SHA-256 hash
by p1mrx on Tuesday April 27, 2021 @09:42PM
(#26964392)
Well, if I were God, I would just define a canonical encoding and hash function as part of the message. Mathematicians would study the algorithm over the years, but never find any flaws.
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?
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).
However, the measurement technique was somewhat underdetermined, which is a problem akin to p-hacking (as you could look for many possible anomalies and only publish the ones that you successfully find).
> anyone could verify that it was authored by someone with more computing power than the universe
I never thought of this that way, but that's an excellent way to put it! (Although you also need to assume that the hash is extremely strongly preimage-resistant, which we don't have good mathematical techniques to prove today.)
One challenge for this: what is the canonical text encoding and canonicalization, and what is the canonical hash function?