LogoTeluq
English
Logo
Répertoire de publications
de recherche en accès libre

The universality of iterated hashing over variable-length strings [r-libre/233]

Lemire, Daniel (2012). The universality of iterated hashing over variable-length strings. Discrete Applied Mathematic, 160 (4-5), 604–617. https://doi.org/10.1016/j.dam.2011.11.009

Fichier(s) associé(s) à ce document :
[img]  PDF - 1008.1715v5.pdf  
Catégorie de document : Articles de revues
Évaluation par un comité de lecture : Oui
Étape de publication : Publié
Résumé : Iterated hash functions process strings recursively, one character at a time. At each iteration, they compute a new hash value from the preceding hash value and the next character. We prove that iterated hashing can be pairwise independent, but never 3-wise independent. We show that it can be almost universal over strings much longer than the number of hash values; we bound the maximal string length given the collision probability.
Adresse de la version officielle : http://www.sciencedirect.com/science/article/pii/S...
Déposant: Lemire, Daniel
Responsable : Daniel Lemire
Dépôt : 03 sept. 2014 18:33
Dernière modification : 16 juill. 2015 00:46

Actions (connexion requise)

RÉVISER RÉVISER