Facebook Instagram Twitter RSS Feed Back to top

Remarks on Gödel's code as a hash function

In: Tatra Mountains Mathematical Publications, vol. 47, no. 3
Michal Mikuš - Petr Savicky
Detaily:
Rok, strany: 2010, 67 - 80
Kľúčové slová:
Gödel numbering function, hash function, integer relation algorithm, rational reconstruction.
O článku:
In this paper we analyze a simple hash function introduced in a popular book \emph{PopCo} by Scarlett Thomas that is based on well known Gödel's numbering function. The numbering function is very efficient for practical use, however it is widely used in foundations of logic and computability theory. We show that the properties of the suggested hash function (computing the hash as a ``shorter digest" of the \emph{long} Gödel's number code) are not sufficient for cryptography. 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 simplest of the attacks, however it does not eliminate the other attacks.
Ako citovať:
ISO 690:
Mikuš, M., Savicky, P. 2010. Remarks on Gödel's code as a hash function. In Tatra Mountains Mathematical Publications, vol. 47, no.3, pp. 67-80. 1210-3195.

APA:
Mikuš, M., Savicky, P. (2010). Remarks on Gödel's code as a hash function. Tatra Mountains Mathematical Publications, 47(3), 67-80. 1210-3195.