Rényi divergence-based uniformity guarantees for $k$-universal hash functions
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911348791705600 |
|---|---|
| author | Pathegama, Madhura Barg, Alexander |
| author_facet | Pathegama, Madhura Barg, Alexander |
| contents | 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 $α$-R{é}nyi divergence for all $α\in (1,\infty]$. For $1\le α\le k$ we show that it is possible to convert all the randomness of the source measured in $α$-\Renyi 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_16459 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Rényi divergence-based uniformity guarantees for $k$-universal hash functions Pathegama, Madhura Barg, Alexander Information Theory Cryptography and Security 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 $α$-R{é}nyi divergence for all $α\in (1,\infty]$. For $1\le α\le k$ we show that it is possible to convert all the randomness of the source measured in $α$-\Renyi 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. |
| title | Rényi divergence-based uniformity guarantees for $k$-universal hash functions |
| topic | Information Theory Cryptography and Security |
| url | https://arxiv.org/abs/2410.16459 |