Number of the records: 1  

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

  1. 1.
    0351385 - ÚI 2012 RIV SK eng J - Journal Article
    Mikuš, M. - Savický, Petr
    Remarks on Gödel's Code as a Hash Function.
    Tatra Mountains Mathematical Publications. Roč. 47, č. 3 (2010), s. 67-80. ISSN 1210-3195
    R&D Projects: GA ČR GAP202/10/1333
    Institutional research plan: CEZ:AV0Z10300504
    Keywords : Gödel numbering function * hash function * rational reconstruction * integer relation algorithm
    Subject RIV: BA - General Mathematics
    http://www.sav.sk/journals/uploads/0317151904m-s.pdf

    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 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 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.
    Permanent Link: http://hdl.handle.net/11104/0191151

     
     
Number of the records: 1  

  This site uses cookies to make them easier to browse. Learn more about how we use cookies.