该论文提出并形式化了“可验证随机采样”（Verifiable Random Sampling, VRS）这一新概念，旨在解决传统可验证随机函数（VRF）在公共密钥发布后其输出变为确定性函数所带来的安全问题。VRF虽然广泛用于需要公开可验证伪随机输出的场景，但其确定性使得攻击者可以预先计算并选择性利用某些输入输出对，从而发起合谋（collusion）或研磨（grinding）式攻击，破坏公平性与不可预测性。为克服这些局限，作者引入VRS，其核心目标是：验证者的最终输出是一个统计上接近指定目标分布的随机样本，同时保持公开可验证性，并且每次采样都具备“新鲜性”（freshness），即不可被预测或预先计算。论文提出了一种基于随机量子电路采样（Random Circuit Sampling, RCS）的具体构造，并指出该构造可在当前的量子计算设备上执行。VRS支持多方协议，其中验证者能够对采样结果进行公开验证，但无法在采样前操控输出。作者在构造性密码学（Constructive Cryptography, CC）框架下对该构造进行了建模并证明了其安全性，从而保证了与其他密码协议的可组合性。总体而言，该工作为需要不可预测、新鲜随机性且同时要求公开可验证公平性的应用提供了一种机制。适合对密码学、量子计算、区块链共识、随机信标以及安全多方计算感兴趣的研究人员阅读。

该论文研究了自适应数据分析（Adaptive Data Analysis, ADA）中的基本问题：随机性是否必要？ADA 问题形式化了在数据集被重复使用时防止虚假发现和过拟合的挑战。输入是一个包含 n 个独立同分布样本的数据集，来自未知分布 P，目标是回答 k 个自适应选择的统计查询。主要问题是如何支持尽可能多的查询（即 k 多大），主要取决于样本数 n。先前工作已充分理解了随机化机制：存在计算高效的机制支持 k ≈ n^2 个查询，且没有计算高效机制能回答 k >> n^2 个查询。然而，随机性是否必要？尽管 ADA 研究已进行十年，该问题仍未解决。一个早期观察是，当分析师计算能力受限时，随机性不是必需的。但对于计算能力无界的分析师，随机性的必要性仍未知。本文的主要贡献是在信息论随机预言机模型中解决了这一差距。令人惊讶的是，论文证明随机性是严格必要的：当分析师无界时，任何确定性机制在仅 k = O~(n) 个查询后就会失败。这表明随机化在抵御无界分析师的自适应查询中扮演关键角色。结果适用于理论计算机科学、数据隐私和机器学习中的自适应数据分析场景。适合理论研究者、密码学及差分隐私领域从业者阅读。

该论文研究了从有限公开记录中审计组合随机性的问题。公共随机性是一种安全原语，但其实际行为往往只能通过有限的记录片段观察。作者针对从 m 个标签中无放回均匀抽取 k 个子集（共 C(m,k) 种可能）这一过程，在精确均匀无放回零假设下进行黑盒审计。传统的均匀性检验需要 Θ(√(C(m,k))/ε²) 个样本，这是仅凭记录认证的信息论极限。为应对结构化偏差，作者设计了与生成器无关的审计方法，包括基于边际卡方、配对最大值、序列重叠、锚定框差异以及低维零假设/最小生成树几何的检验，所有检验均在精确组合零假设下校准。同时，作者证明了有限样本保证，其样本复杂度与审计的见证数量呈对数关系，而非全支撑集大小。通过 GPU 蒙特卡洛实验（每个条件最多 30 万零假设和 6 万备择假设复制），发现边际保持偏差可逃逸一维检验，但通过联合几何仍可检测。例如，在 n=1,956 时，强度 0.04 的块簇备择假设下，配对最大值的检验功效为 0.638，而边际卡方仅为 0.051；强度 0.08 的带排斥备择假设下，锚定框的检验功效为 0.741。这些结果刻画了哪些结构化偏差能被有限公共记录检测到，以及所需样本量。