Remarks on Gödel's Code as a Hash Function

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F10%3A00351385" target="_blank" >RIV/67985807:_____/10:00351385 - isvavai.cz</a>

Výsledek na webu

<a href="http://www.sav.sk/journals/uploads/0317151904m-s.pdf" target="_blank" >http://www.sav.sk/journals/uploads/0317151904m-s.pdf</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Remarks on Gödel's Code as a Hash Function

Popis výsledku v původním jazyce

In this paper we analyze a simple hash function introduced in a popular book PopCo by Scarlett Thomas that is based on well known Gödel's numbering function. The numbering function is very slow for practical use, however it is widely used in foundationsof logic and computability theory. We show that the properties of the suggested hash function (computing the hash as a "shorter digest" of the 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 simpler of the attacks, however this hasn't been successful for the second attack.

Název v anglickém jazyce

Remarks on Gödel's Code as a Hash Function

Popis výsledku anglicky

In this paper we analyze a simple hash function introduced in a popular book PopCo by Scarlett Thomas that is based on well known Gödel's numbering function. The numbering function is very slow for practical use, however it is widely used in foundationsof logic and computability theory. We show that the properties of the suggested hash function (computing the hash as a "shorter digest" of the 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 simpler of the attacks, however this hasn't been successful for the second attack.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GAP202%2F10%2F1333" target="_blank" >GAP202/10/1333: NoSCoM: Nestandardní výpočetní modely a jejich aplikace ve složitosti, lingvistice a učení</a><br>

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2010

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Tatra Mountains Mathematical Publications

ISSN

1210-3195

e-ISSN

—

Svazek periodika

47

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

SK - Slovenská republika

Počet stran výsledku

14

Strana od-do

67-80

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—