EUVIMEDEUVIMED entdecken
Crossref

Rényi Divergence-Based Uniformity Guarantees for k -Universal Hash Functions

Madhura Pathegama, Alexander Barg

IEEE Transactions on Information Theory · 2025-12 · 71 (12) · 9203-9214

DOI: 10.1109/tit.2025.3619440 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Transactions on Information Theory, 2025-12. Verfasst von Madhura Pathegama und 1 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 37 Literaturangaben. Gefördert von: NSF.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Universal hash functions map the output of a source to random strings over a finite alphabet, aiming to approximate the uniform distribution on the set of strings. A classic result on these functions, called the Leftover Hash Lemma, gives an estimate of the distance from uniformity based on the assumptions about the min-entropy of the source. We prove several results concerning extensions of this lemma to a class of functions that are $k^{\ast } $ -universal, i.e., $l$ -universal for all $2\le l\le k$ . As a common distinctive feature, our results provide estimates of closeness to uniformity in terms of the $\alpha $ -Rényi divergence for all $\alpha \in (1,\infty $ ]. For $1\le \alpha \le k$ we show that it is possible to convert all the randomness of the source measured in $\alpha $ -Rényi entropy into approximately uniform bits with nearly the same amount of randomness. For large enough $k$ we show that it is possible to distill random bits that are nearly uniform, as measured by min-entropy. We also extend these results to hashing with side information.

Förderung

  • NSF

Zitieren

APA

Pathegama, M., & Barg, A. (2025). Rényi Divergence-Based Uniformity Guarantees for k -Universal Hash Functions. IEEE Transactions on Information Theory, 71(12), 9203-9214. https://doi.org/10.1109/tit.2025.3619440

Vancouver

Pathegama M, Barg A. Rényi Divergence-Based Uniformity Guarantees for k -Universal Hash Functions. IEEE Transactions on Information Theory. 2025;71(12):9203-9214. doi:10.1109/tit.2025.3619440

BibTeX
@article{Pathegama2025,
  author = {Pathegama, Madhura and Barg, Alexander},
  title = {Rényi Divergence-Based Uniformity Guarantees for k -Universal Hash Functions},
  journal = {IEEE Transactions on Information Theory},
  year = {2025},
  volume = {71},
  number = {12},
  pages = {9203--9214},
  doi = {10.1109/tit.2025.3619440}
}
Kostenlos starten →