该论文针对安全多方计算（MPC）中实现数据无关的二分搜索这一难题展开研究。传统的二分搜索算法直接应用于MPC时会泄露数据访问模式，先前的工作依赖混淆RAM（ORAM）来隐藏访问模式，但ORAM开销很高。本文首次尝试使用基于秘密共享的常规安全计算技术来实现二分搜索。作者提出了一系列具有不同属性和结构的协议，用于通过私密数值键搜索包含m个元素的私有数据集。这些协议仅使用标准且易用的秘密共享操作，可实现O(m)和O(√m)的通信复杂度（前者为线性扫描，后者为改进方案）。协议进一步扩展支持写操作，即二分搜索后对选中元素进行不透明更新，并实现了两种变体：更新非键字段和更新键字段。实验结果表明，即使对最快的ORAM构造应用已知及自有的优化，对于最多2^30个元素的数据集，本文方案的性能仍优于优化后的ORAM方案，速度提升可达两个数量级。该工作为在MPC中高效实现二分搜索开辟了新途径，对隐私保护数据查询有重要推动。

本文针对隐私保护机器学习（PPML）与机器学习审计这两个此前大多独立研究的领域进行了交叉探索。随着PPML技术（如安全多方计算、同态加密、差分隐私等）的发展，使得对高度敏感数据（例如医疗、金融记录）进行机器学习分析成为可能，然而严格的隐私法规（如GDPR）要求对数据使用做出解释和问责，因此对PPML系统进行审计的需求日益增长。现有PPML方案缺乏透明度，难以验证计算中使用的输入数据是否与用户承诺一致，且审计过程本身可能泄露隐私。为此，作者提出了Arc——一个用于审计隐私保护机器学习的MPC（安全多方计算）框架。Arc的核心是一个新的高效协议，能够在大规模下通过简洁的承诺（succinct commitments）验证MPC输入的一致性。具体而言，该协议允许审计方在不获取原始数据的前提下，确认每个参与方提供的输入与其先前提交的承诺匹配，从而确保数据完整性。作者将该一致性协议与基于哈希和基于同态承诺的方法进行了性能对比，实验表明，Arc在速度上最高可快10^4倍，在通信简洁性上最高可优10^6倍。该工作为构建可问责、可审计的PPML系统迈出了重要一步，适用于需要既保护隐私又符合监管要求的场景。

本文继续研究一类称为“快速函数”的线性大小电路可计算的函数，这些函数共享随机函数的有用性质，但更具确定性，适合密码学应用。作者在两个主要方向上进行了推广和改进： 1. 构造了任意常数 t 的快速 t-独立哈希函数，其代数次数为 log2 t（在 F2 上），同时在渐近电路大小和次数上达到最优。这优于之前的工作，降低了电路深度，同时保持线性大小。 2. 简化并改进了 ITCS 2026 中关于快速码及其快速对偶的构造，使其满足 Gilbert-Varshamov 界，且失败概率可忽略，支持一般域和码率、系统编码以及快速通用编码器。此外，还强化了组合列表解码等更强随机性质，通过构造快速线性函数族实现：对于任意常数 t，任意 t 个线性无关的输入映射为均匀且统计独立的输出，此前仅对 t=1 已知。 作者展示了这些结果在密码学中的应用，包括：第一个在完美安全多方计算中电路复杂度与参与方数量线性缩放的非平凡协议，以及计算加密矩阵-向量乘积的最优渐近电路复杂度的协议。 本文适合密码学理论研究者、安全多方计算协议设计者以及对伪随机函数和编码理论感兴趣的学者阅读。