Remarks on Gödel's code as a hash function
Abstract
In this paper we will analyze a simple hash function introduced in a popular book PopCo by Scarlett Thomas that is based on well known GÄodel's numbering function.
The numbering function is very slow for practical use today, however it had been widely used in the past. We show that the properties of the suggested hash function (computing the hash as a "shorter digest" of the long GÄodel's number code) are not su±cient enough. Although the preimage resistance of this hash function holds against the rational reconstruction method, we introduce two ways how to construct meaningful collisions and in special cases also second-preimages. Further we propose a simple improvement of this hash function which prevents the simpler of the attacks, however this hasn't been successful for the second attack.
The numbering function is very slow for practical use today, however it had been widely used in the past. We show that the properties of the suggested hash function (computing the hash as a "shorter digest" of the long GÄodel's number code) are not su±cient enough. Although the preimage resistance of this hash function holds against the rational reconstruction method, we introduce two ways how to construct meaningful collisions and in special cases also second-preimages. Further we propose a simple improvement of this hash function which prevents the simpler of the attacks, however this hasn't been successful for the second attack.
Full Text:
PDFDOI: https://doi.org/10.2478/tatra.v47i0.52