The universality of iterated hashing over variable-length strings

DOI10.1016/J.DAM.2011.11.009zbMATH Open1237.68079OpenAlexW1717515755WikidataQ56115222 ScholiaQ56115222MaRDI QIDQ412371FDOQ412371

Authors Daniel Lemire 

Publication date 4 May 2012

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1008.1715

zbMATH Keywords

permutationsfinite fieldshashing stringsiterated hashing

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20)

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.

Recommendations

• Advances in Cryptology – CRYPTO 2004
• Variationally universal hashing
• Variants of multicollision attacks on iterated hash functions
• Multicollision attacks and generalized iterated hash functions
• Generalized iterated hash fuctions revisited: new complexity bounds for multicollision attacks

Cites work

• scientific article; zbMATH DE number 1676651 (Why is no real title available?)
• scientific article; zbMATH DE number 1689861 (Why is no real title available?)
• scientific article; zbMATH DE number 3877077 (Why is no real title available?)
• scientific article; zbMATH DE number 3965971 (Why is no real title available?)
• scientific article; zbMATH DE number 1024070 (Why is no real title available?)
• scientific article; zbMATH DE number 1099195 (Why is no real title available?)
• scientific article; zbMATH DE number 1406775 (Why is no real title available?)
• scientific article; zbMATH DE number 1445340 (Why is no real title available?)
• A trade-off between collision probability and key size in universal hashing using polynomials
• Bucket hashing and its application to fast message authentication
• Constructing an Ideal Hash Function from Weak Ideal Compression Functions
• Cuckoo hashing
• Faster integer multiplication
• On fast and provably secure message authentication based on universal hashing
• String hashing for linear probing
• Tabulation based 4-universal hashing with applications to second moment estimation
• Universal classes of hash functions
• Universal hashing and \(k\)-wise independent random variables via integer arithmetic without primes
• Universal hashing and authentication codes

Cited in

(1)

• Practical evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch tries

This page was built for publication: The universality of iterated hashing over variable-length strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q412371)