The universality of iterated hashing over variable-length strings

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

Authors: Daniel Lemire 

Publication date: 4 May 2012

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

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.

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

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

zbMATH Keywords

permutationsfinite fieldshashing stringsiterated hashing

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20)

Cites Work

• Title not available (Why is that?)
• Universal classes of hash functions
• On Fast and Provably Secure Message Authentication Based on Universal Hashing
• Universal hashing and k-wise independent random variables via integer arithmetic without primes
• Title not available (Why is that?)
• Cuckoo hashing
• Faster integer multiplication
• Title not available (Why is that?)
• Universal hashing and authentication codes
• Bucket hashing and its application to fast message authentication
• Title not available (Why is that?)
• Title not available (Why is that?)
• Constructing an Ideal Hash Function from Weak Ideal Compression Functions
• A trade-off between collision probability and key size in universal hashing using polynomials
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

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)