More Efficient Privacy Amplification With Less Random Seeds via Dual Universal Hash Function
Masahito Hayashi, Toyohiro Tsurumaru · IEEE Transactions on Information Theory · 2016
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(n log n) for input length n. The key idea is the concept of dual universal2hash function introduced recently. We also use a new method for constructing extractors by concatenating δ-almost dual universal2hash 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 universal2hash function, as well as to the conventional universal2hash functions.