该论文提出了一种在量子随机预言机模型（QROM）下实现无条件安全认证随机性的协议。该协议是非交互式的，且可由经典验证者公开验证，其设计基于 Yamakawa 和 Zhandry 在 JACM'24 上提出的量子性证明（proof of quantumness）技术。与以往依赖额外结构（如 Aaronson-Ambainis 猜想）或仅能抵御低查询深度攻击者的方案不同，本协议的安全性证明针对的是能够对随机预言机进行亚指数次自适应量子查询的 adversaries，且不依赖任何未经证明的猜想，实现了‘无条件安全’（即安全性仅基于量子力学基本定律和随机预言机模型的形式化假设）。论文的核心贡献在于：第一，首次在仅有经典验证者且协议为单轮的情况下，实现了对强量子攻击者的可证明安全随机性生成；第二，消除了此前工作中需要的结构化假设或对查询深度的限制；第三，为量子计算优势的验证提供了新的理论工具。该工作属于量子密码学与计算复杂性理论的前沿研究，适用于量子安全协议设计、随机性生成基础设施以及量子计算能力认证等研究方向。

本文研究 Kac 游走（Kac's walk）的伪混合性质，该游走是 SO(n) 上的一种马尔可夫链，在每次迭代中随机选取两个坐标并应用一个随机旋转。伪混合的概念由 Vaikuntanathan 和 Zamir 提出猜想，关注的是：在低复杂度的测试下，短时间演化的轨迹是否与 Haar 测度（即 SO(n) 上的均匀分布）不可区分。这一性质对于随机化算法和密码学中的熵提取具有重要意义。文章首先证明了 Kac 游走的前 k 列在固定精度下，经过 O(n(k+log n)log n) 步后在 Wasserstein 距离上混合，从而解决了 Oliveira 的一个猜想。随后，作者结合表示论中的方差界，证明了若步数 T = ω(nk(k+log n)log n)，则任何归一化到单位 Haar 方差的 k 次多项式，在 T 步后的分布下的期望与在 Haar 测度下的期望相差 o(1)。这一结果表明，低阶多项式统计量无法区分 Kac 游走的短轨迹与 Haar 测度，即伪混合性质成立。作为应用，作者展示了该伪混合估计可用于证明快速 Johnson-Lindenstrauss 变换的有效性，且目标维度与通常的维度相同。该工作为理解 Kac 游走这类高维随机过程的伪随机性提供了理论保证，并可能对设计更高效、更安全的随机化算法有潜在贡献。适合理论计算机科学、随机矩阵理论、密码学以及机器学习理论方向的研究者阅读。

该论文提出并形式化了“可验证随机采样”（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。这些结果刻画了哪些结构化偏差能被有限公共记录检测到，以及所需样本量。