#matching-vector-family

共收录 1 条相关安全情报。

← 返回所有主题
👥 作者: Aparna Gupte, Seyoon Ragavan

本文研究私密信息检索(PIR)协议的通信复杂度问题。PIR 允许用户在不向服务器泄露查询内容的情况下,从分布式数据库中检索一条记录。经典结果要求服务器数量与通信量之间存在权衡。本文在数论猜想(广义重单位猜想或 Schinzel 假设 H)成立的前提下,构造了对于任意常数 s 的 s 服务器 PIR 协议,其通信复杂度为 exp(O((log n)^{1/s} (log log n)^{1-1/s})),其中 n 为数据库大小。此前达到相同通信量的协议需要 2^{O(s)} 台服务器。核心创新在于构建了仅含 k+1 个非零系数的 S-解码多项式(模 k 个素数的特殊乘积),解决了 Ghasemi 和 Kopparty 提出的开放问题,该稀疏性已被证明是最优的。作者还通过实验验证了构造的正确性,并使得对于 s ≤ 15 的结果无条件成立。此外,对于随 n 增长的 s,在更强的数论猜想下,本文证明了匹配向量 PIR 的通信复杂度可较先前最优结果实现超多项式改进。主要结果(常数 s)及其证明由作者在 GPT-5.5 Pro 对话中发现。该工作属于理论计算复杂性领域,为高效 PIR 协议的设计提供了新的代数工具。

💡 推荐理由: 本工作显著降低了 PIR 协议的服务器数量要求,在理论层面推动隐私检索算法的进展,可能间接影响安全多方计算和隐私保护数据查询系统的效率。

🎯 建议动作: 研究跟进

排序因子: 来自 arXiv 其他板块 (+2) | Community 数据源 (+1) | LLM 评分加成 (+0.5)