More Efficient Privacy Amplification With Less Random Seeds Via Dual Universal Hash Function

Hayashi Masahito, Tsurumaru Toyohiro. IEEE Transactions on Information Theory Volume 2013

[Paper]    
Independent

We explicitly construct random hash functions for privacy amplification (extractors) that require smaller random seed lengths than the previous literature, and still allow efficient implementations with complexity $O(nlogn)$ for input length $n$. The key idea is the concept of dual universal${}_2$ hash function introduced recently. We also use a new method for constructing extractors by concatenating $\delta$-almost dual universal${}_2$ hash functions with other extractors. Besides minimizing seed lengths, we also introduce methods that allow one to use non-uniform random seeds for extractors. These methods can be applied to a wide class of extractors, including dual universal${}_2$ hash function, as well as to conventional universal${}_2$ hash functions.

Similar Work

• Sharp Rate For The Dual Quantization Problem
• Compressed Spaced Suffix Arrays
• Shockhash Near Optimal-space Minimal Perfect Hashing Beyond Brute-force
• Comparison Of Modified Dual Ternary Indexing And Multi-key Hashing Algorithms For Music Information Retrieval