Lemire, Daniel 
ORCID: https://orcid.org/0000-0003-3306-6922
(2012).
The universality of iterated hashing over variable-length strings. Discrete Applied Mathematics, 160 (4-5), 604–617. 10.1016/j.dam.2011.11.009
| 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 : | 05 nov. 2026 20:33 |
|
RÉVISER |
