On Universal Classes of Extremely Random Constant-Time Hash Functions

DOI10.1137/S0097539701386216zbMath1082.68129MaRDI QIDQ4651478

Alan R. Siegel

Publication date: 21 February 2005

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

universal hash functionshashinghash functionslimited independenceoptimal speedupPRAM emulationstorage-time tradeoff

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Information storage and retrieval of data (68P20) Randomized algorithms (68W20)

Related Items (16)

Randomized OBDD-based graph algorithms ⋮ Dynamic dictionaries for multisets and counting filters with constant time operations ⋮ Balanced allocation and dictionaries with tightly packed constant size bins ⋮ Quicksort, Largest Bucket, and Min-Wise Hashing with Limited Independence ⋮ Polynomial Data Structure Lower Bounds in the Group Model ⋮ Derandomized constructions of \(k\)-wise (almost) independent permutations ⋮ Connecting tweakable and multi-key blockcipher security ⋮ Hardness-preserving reductions via cuckoo hashing ⋮ Universal Hashing via Integer Arithmetic Without Primes, Revisited ⋮ Unnamed Item ⋮ Quantum key distribution with PRF(Hash, Nonce) achieves everlasting security ⋮ A combinatorial approach to quantum random functions ⋮ Explicit and efficient hash families suffice for cuckoo hashing with a stash ⋮ Dynamic dictionaries for multisets and counting filters with constant time operations ⋮ On an Almost-Universal Hash Function Family with Applications to Authentication and Secrecy Codes ⋮ Sampling Lower Bounds: Boolean Average-Case and Permutations

This page was built for publication: On Universal Classes of Extremely Random Constant-Time Hash Functions