Treffer: On Universal Classes of Extremely Random Constant-Time Hash Functions: On universal classes of extremely random constant-time hash functions

Title:
On Universal Classes of Extremely Random Constant-Time Hash Functions: On universal classes of extremely random constant-time hash functions
Authors:
Alan Siegel
Source:
SIAM Journal on Computing. 33:505-543
Publisher Information:
Society for Industrial & Applied Mathematics (SIAM), 2004.
Publication Year:
2004
Subject Terms:
limited independence, optimal speedup, Randomized algorithms, hash functions, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, hashing, storage-time tradeoff, PRAM emulation, Information storage and retrieval of data, Graph theory (including graph drawing) in computer science, 0202 electrical engineering, electronic engineering, information engineering, Analysis of algorithms, universal hash functions, Parallel algorithms in computer science
Document Type:
Fachzeitschrift Article
File Description:
application/xml
Language:
English
ISSN:
1095-7111
0097-5397
DOI:
10.1137/s0097539701386216
Accession Number:
edsair.doi.dedup.....f25a3d0bca4ae5aa13f8dc2af862590c
Database:
OpenAIRE

Weitere Informationen

Summary: A family of functions \(F\) that map \([0,m-1]\) into \([0,n-1]\) is said to be \(\kappa\)-wise independent if any tuple of \(\kappa\) distinct points in \([0,m-1]\) have a corresponding image, for a randomly selected \(f\in F\), that is uniformly distributed in \([0,n-1]^{\kappa}\). This paper shows that for suitably fixed \(\varepsilon