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

2013/11/30 by Masahito Hayashi, Toyohiro Tsurumaru
Computer Science · Engineering · Mathematics · Physics and Astronomy · #Advanced Steganography and Watermarking Techniques #Biology #Chaos-based Image/Signal Encryption #Computer science #Computer security #Dual (grammatical number) #Function (biology) #Genetics #Hash function #Mathematics #Random function #Random variable #Statistics #Theoretical computer science #Wireless Communication Security Techniques #cs.CR #cs.IT #math.IT #quant-ph

paper · pdf · doi:10.1109/tit.2016.2526018

published as IEEE Transactions on Information Theory, Volume 62, Issue 4, 2213 - 2232 (2016) · 33 pages, no figure, 1 table; v3: revised arguments with new hash functions proposed additionally, v4: minor corrections and clarifications, some new references added, v5: minor corrections, and enhanced arguments related with applications

arxiv created 2015/08/18 · openalex publication_date 2016/02/04 · arxiv updated 2016/03/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

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.

Citations

• Trevisan's Extractor in the Presence of Quantum Side Information
• A modular framework for randomness extraction based on Trevisan's construction
• New hash functions and their use in authentication and set equality
• Loss-tolerant quantum cryptography with imperfect sources
• A Pseudorandom Generator from any One-way Function
• Security analysis of the decoy method with the Bennett–Brassard 1984 protocol for finite key lengths
• Dual Universality of Hash Functions and Its Applications to Quantum Cryptography
• Upper bounds of eavesdropper’s performances in finite-length code with the decoy method
• Tight finite-key analysis for quantum cryptography
• Finite-Length Analyses for Source and Channel Coding on Markov Chains