
Open access research
publication repository
publication repository
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
File(s) available for this item:PDF - 1008.1715v5.pdf |
|
Item Type: | Journal Articles |
---|---|
Refereed: | Yes |
Status: | Published |
Abstract: | 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. |
Official URL: | http://www.sciencedirect.com/science/article/pii/S... |
Depositor: | Lemire, Daniel |
Owner / Manager: | Daniel Lemire |
Deposited: | 03 Sep 2014 18:33 |
Last Modified: | 16 Jul 2015 00:46 |
![]() |
RÉVISER |