基于Rényi散度的均匀性保证：用于k-通用哈希函数

《IEEE Transactions on Information Theory》：Rényi Divergence-Based Uniformity Guarantees for k-Universal Hash Functions

通用哈希函数的Leftover Hash Lemma扩展分析，建立基于min-熵的α-Rényi散度估计，研究低熵源通过k-通用哈希转化为均匀比特的机制，包括内在随机性提取和确定性函数应用。

　　

摘要：

通用哈希函数将源数据的输出映射到有限字母表上的随机字符串，旨在逼近这些字符串集合上的均匀分布。关于这类函数的一个经典结果被称为“剩余哈希引理”（Leftover Hash Lemma），它根据对源数据最小熵的假设，给出了偏离均匀分布程度的估计。我们证明了几个关于该引理扩展的结果，这些扩展适用于一类被称为k?-通用的函数，即对于所有满足2 ≤ l ≤ k的函数，它们都具备均匀性。我们的结果提供了一个共同的特性：它们能够根据α-Rényi散度来估计这些函数与均匀分布的接近程度，其中α ∈ (1, ∞)。对于1 ≤ α ≤ k的情况，我们展示了如何将源数据中的所有随机性（以α-Rényi熵衡量）转换为具有几乎相同随机性的均匀比特。对于足够大的k值，我们证明了可以生成接近均匀的随机比特（通过最小熵来衡量）。此外，我们还将这些结果扩展到了带有辅助信息的哈希算法中。

引言

均匀随机比特串是计算机科学和密码学中的基本资源。在计算机科学中，许多算法利用随机化来更高效地解决问题[24]。此外，在许多密码学应用中，如随机加密方案[29]、秘密共享[30]、比特承诺[9]和零知识证明[15]等，均匀随机比特是不可或缺的。为了从低熵的随机源中获得均匀分布，人们尝试将其随机性转换为均匀比特。从随机源中可提取的最大均匀比特量被称为“内在随机性”[37]；如果源数据的分布已知，那么一个确定性函数可以将大部分熵转换为均匀的q进制符号。