HCC: A Hash Function Using Error Correcting Codes
Sami Harar · 2005
1 I n t r o d u c t i o n Many computat ionally fast complete decoding algorithms are available for error correcting codes. By completing the decoding process, tha t is extracting of information bits of a decoded vector, the decoding process can be seen as a compressive function which could be used for hashing of data. Good hash functions are compressive functions for which collisions are hard to find. This is not the case of the preceding scheme. However, the collisions can be characterized: they are all the error vectors of low weight. By using extra transformations on the da ta to be hashed it is possible to eliminate all the potentially weak collisions, why preserving the advantages of error correcting codes: the estimation of the complexity of finding collisions. This work is a contribution for defining a hash function HCC (hash with codes and correlations) using the decoding function of error correcting codes having a 'divide and conquer ' approach for calculating the hash, while having an exponential complexity for the search of collisions. 2 General Constraints A possible way to define a hash function is to use a complete decoding algorithm of an error correcting code C. The da ta to be hashed is decoded and the hash of the da ta is the set of information bits. Operat ing in this way leads to a hash function for which some collisions are easy to find for two arguments. T h e l i n e a r s t r u c t u r e . Given a string of da ta dn and the corresponding hash H(dn) obtained in this manner , it is easy to obtain new sets of da ta with a known hash if the generator matr ix G of the code is known.