本文提出并研究了在差分隐私保护下释放层次重击者（Hierarchical Heavy Hitters, HHH）的问题。层次重击者是经典重击者问题的推广，最早由Cormode等人在VLDB 2003中引入，用于在数据流中识别在层次结构上显著的项。尽管数据流中的HHH查找已被广泛研究，但在底层数据包含隐私信息时，如何安全地释放HHH结果尚未被探索。本文分别考察了非流式（静态数据集）和流式两种场景。在非流式设置中，作者发现了一个令人惊讶的结果：对于任何前缀，估计残差计数（residual count）的相对误差与层次的高度以及流中重击者的数量无关。这意味着即使在复杂的层次结构下，相对精度也能保持稳定。在流式设置中，虽然HHH的精确版本具有较低的全局灵敏度（因为计数查询是1-敏感的），但用于流式处理的近似函数却导致了较高的全局灵敏度，该灵敏度与可用空间呈线性关系。尽管如此，作者证明在流式设置中，估计频率的绝对误差与可用空间无关，从而突破了空间限制带来的障碍。本文的主要贡献包括：首次系统性地研究差分隐私HHH释放问题；在非流式场景中证明了一个与层次规模无关的误差界；在流式场景中给出了绝对误差独立于空间的证明。读者需要具备差分隐私、数据流算法以及层次重击者问题的基础知识。

本文研究动态有序集合（支持插入、删除、成员查询、前驱后继、最小值最大值等操作）的回顾性审计问题。集合由不可信方维护，被动审计者（auditor）仅需存储 5 个机器字和 1 个标志位，并在每次操作时接收一个常量大小的公开 tally 记录。审计阶段，维护者披露声称的活跃空区间（live vacant intervals）。方法的核心是利用最大间隙（maximal gaps）表示顺序语义：间隙有出生、引用、消费、时间戳等状态，同时两个隐藏域累加器分别对出生账本和消费账本进行相等性测试。诚实执行以概率 1 被接受；若包含 T 次操作的会话中存在错误回答，接受概率至多为 (4T+1)/p（p 为秘密域元素大小，对计算能力无限制的维护者有效）。论文证明确定性或可见硬币审计器需要线性状态，并发现移除时间戳规则会导致精确重放伪造。实现方面，采用叶导向的 (2,4)-树作为维护者数据结构，每个操作最坏情况 O(log n) 时间，每个元素额外存储一个字，且再平衡事件在 m 次更新上具有可审计的 O(m) 包络。检查点审计可通过加法误差组合。本文适合研究可验证计算、数据完整性审计及信任最小化系统的研究人员阅读。

本文研究持续观察下私有化发布k维向量更新的问题。初始向量为零向量，在时间点t_i上通过添加x^{(i)}进行更新，其中t_i∈[T]，x^{(i)}在k维单位球B_k内。两个数据集被认为是相邻的，如果它们的对称差大小不超过1。持续发布需要在每个时间步t=1,...,T输出累加和A^{(t)} = ∑_{i: t_i ≤ t} x^{(i)}。经典方法可以O(kT)时间、polylog(T)噪声幅度释放近似值。本文考虑每个时间步仅需发布A^{(t)}的子集，提出一种快速高斯机制，能够在常数时间内采样噪声向量中任意指定条目，同时精确复制二叉树机制下高斯噪声的分布。该改进基于布朗桥构建的新数据结构，突破了已知O(log T)时间界限。文章展示了两个数据管理应用：1) 正交范围计数查询的动态数据结构，在隐私/准确性/空间权衡上优于先前结构；2) 连接大小估计，同时改进了高概率界。本文适合对差分隐私、数据流算法和数据结构设计感兴趣的研究者。

该论文研究了数论变换（NTT）的不确定性原理，并证明了在某些素数条件下，非零函数与其NTT变换的支撑集大小之和至少为q+1（q为给定素数，p为满足p≡1 mod q的素数）。这意味着一稀疏函数（k-稀疏）的变换支撑集至少为q-k+1。进一步，作者还证明了在p=q^{O(1)}范围内的素数平均意义上的概率版本不确定性原理。作为应用，该原理被用于构造一个黑盒身份测试算法，用于验证至多k-稀疏、度数不超过d的指数多项式，在q适度大于k时具有零声音误差。该研究为多项式恒等测试提供了新的理论工具，对密码学、编码理论等领域中涉及NTT的应用有潜在影响。

本文首次研究了差分隐私下的范围子图计数问题（DPRSC）。子图计数是图分析中的基本问题，传统方法通常计算整个图中特定模式的出现次数。然而，实际应用常需对由多维属性范围选中的顶点诱导子图进行查询，同时保护隐私。差分隐私子图计数面临重大挑战：子图计数是非线性函数且敏感度高，单个边的修改可能影响大量子图出现次数。为此，本文提出了一种高效算法，通过引入子图投影，将DPRSC转化为加权正交范围计数问题。利用范围树和局部敏感度估计，实现了低加性误差的私有查询响应。此外，还通过将重构攻击归约为DPRSC并利用离散理论，证明了任何差分隐私算法都必须承受随维度指数增长的加性误差。实验表明，所提算法在准确性和运行时间上显著优于基线方法，同时保持强隐私保证。该研究为图数据分析中的隐私保护提供了新工具，尤其适用于社交网络、生物信息学等需敏感数据查询的场景。

本文研究差分隐私（DP）约束下的多目标子模最大化（MOSM）问题，旨在从敏感数据集中选择一个最多包含 k 个元素的子集，以最大化 d 个单调子模函数的最小值，同时满足 ε-差分隐私。虽然差分隐私单目标子模最大化和非隐私的多目标子模最大化已有大量研究，但据作者所知，本文是首个将差分隐私与多目标子模最大化相结合的工作。作者提出了两种新算法：第一种扩展了经典贪心算法，第二种采用截断技术，两者均集成了差分隐私机制以实现隐私保护，并给出了针对 MOSM 的近似保证。最后，作者在多目标设置下，针对最大覆盖和设施选址两个子模最大化应用进行了数值实验，验证了所提算法的有效性和效率。该工作主要面向对差分隐私、子模优化理论感兴趣的算法研究人员。

该论文研究了在差分隐私约束下，使用e值进行假设检验时的最优速率问题。E值作为一种灵活的工具，近年来在允许任意有效和自适应数据分析中受到广泛关注，其应用常涉及隐私或敏感数据。作者提出了一个核心问题：给定两个分布P和Q，在满足ε-差分隐私的e值检验中，最大化e-power（即检验功效）的最优速率是多少？论文给出了该问题的特征描述，并提出了一个达到最优速率的算法。在序列设置中，当观测值逐个到达且分析师选择何时停止时，作者给出了任何私有e-process的停止时间的匹配上下界。数值实验证实了算法的实用性，在多种序列测试问题和隐私水平下，该算法所需的数据量少于近期提出的DP-SPRT方法。本研究为差分隐私假设检验提供了理论最优性和实用算法，适用于需要隐私保护的统计推断场景。

该论文研究差分隐私下单调统计量的高效估计算法。单调统计量指随着新观测数据增加而单调变化的统计量（如分位数、累积分布函数等）。传统方法采用子采样-聚合（subsample-and-aggregate）框架：将数据集分成多个子块，分别计算统计量，再用差分隐私机制聚合结果。该方法适用性广但样本效率低下。本文针对单调统计量提出改进算法，在样本复杂度上节省了因子t（t>0为可调参数），但运行时间增加了e^t倍。通过查询复杂度下界证明该算法本质最优。应用案例包括私有特征值估计、私有损失估计以及高维模型中单参数（如线性回归系数）的私有估计。实验表明新算法在保持同等隐私保障下需更少样本，适合数据稀缺场景。

该论文研究了差分隐私（DP）中的广义私有测试问题，该问题由 Liu 和 Talwar 在 STOC 2019 中提出。给定一个数据集 X 和一个序列的黑盒 ε_t-DP 机制 M_t，分析者需要以 DP 方式接受第一个成功概率 p_t = Pr[M_t(X)=+1] 超过给定阈值 p^* 的机制。准确度由 p^* 和拒绝阈值 bar{p} 之间的间隙衡量，要求高概率下判断正确。为了提升此项任务的样本复杂度和精度，论文引入了广义阈值机制（GTM）。GTM 是纯 ε-DP 机制，可以处理任意 (ε_t, δ_t)-DP 机制序列，并实现了近最优的精度和样本复杂度下界。通过 GTM，作者给出了从持续观察（CO）设置到批处理设置的 DP 优化黑盒归约，首次为多种最大化问题（如子模最大化）提供了 DP-CO 算法。此外，GTM 允许自适应选择接受阈值 p_t^*，解决了先前工作中（如 Papernot 和 Steinke, ICLR 2022）用于超参数优化的挑战。论文主要贡献包括：提出了 GTM 算法，证明了其近最优性，建立了 CO 到批处理的归约，并展示了广义私有测试在自适应阈值选择方面的灵活性。适合对差分隐私理论、算法设计以及私有优化感兴趣的研究人员阅读。

本文是'模格安全性'系列论文的第三部分，聚焦于分圆域Q(ζ_{2^k})的对数单位格上的结构化最近向量问题（CVP）距离。论文首先证明了从随机短环元素到对数单位格的L^2 CVP距离渐近收敛到(π/(2√6))√n，其中n=2^{k-1}。对于k≥4，该目标位于原点的Voronoi胞内。在L^∞范数下，n个子高斯坐标的最大值产生O(√log n)的边界，这转化为短生成元问题的次多项式近似因子。文章还提出了'粗格定理'：Babai算法对所有结构化目标返回零，但能精确恢复任意大小的单位扰动。对于模行列式理想，进一步证明了Trigamma定理，揭示了内在不平衡性σ_{g_0}=O(1)与模q无关。最后，结合前两部分，将ML-KEM的CDPR因子从exp(Õ(√n))降低到次多项式值。该工作为评估后量子密码标准ML-KEM的安全性提供了更紧的理论界。

本文从变分与优化原理的角度重新审视格约简（Lattice Reduction）中的核心机制。格约简通过局部交换操作（如 Lovász 交换）平滑 Gram-Schmidt 轮廓，作者使用 majorization（优化）理论精确刻画了这一过程：每个非退化 Lovász 交换等价于对数范数轮廓上的一个 T-变换，因此任何严格 Schur-凸的轮廓扩散度量都会在该交换下严格减小。这一视角带来两个结构性结论：首先，最坏情况 GSA（几何序列假设）包络线具有变分解释，它是唯一在 Lovász 间隙几何约束下具有最小方差的轮廓，其斜率仅由 LLL 参数决定；其次，实际的交换轨迹满足一个精确的方差耗散伸缩恒等式。该框架还帮助组织深度插入启发式策略，提出了一族基于热力学的 Schur-凸评分规则，并激励在该族内进行自适应选择。基于此，作者设计了两种具体选择器：Thermal-Adaptive（在扁平轮廓上相比 SS-GG 减少操作次数，在 q-ary 输入上恢复 SS-GG 性能）和 Geodesic Deep-LLL（在结构化格上减少等效交换次数，但墙钟时间更高）。实验结果验证了方法的有效性。该工作主要面向理论密码学与算法设计研究者，为格基密码的安全性评估提供了新的理论工具。