#efi-pairs

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

← 返回所有主题
👥 作者: Atul Mantri

本文研究量子密码学中最基础的两类"最小假设"候选原语之间的关系。第一类是 EFI pairs(Brakerski、Canetti、Qian,ITCS 2023),指一对高效可制备的量子态:它们在统计上相距很远(可区分),但在计算上对任何多项式时间区分者都不可区分。第二类是 one-way puzzles(Khurana、Tomer,STOC 2024),即经典谜题:采样容易、求解困难。已知 one-way puzzle 可以推出 EFI pair,但反过来是否成立(EFI pair 能否推出 one-way puzzle)是公开问题。本文给出的答案是:在相对化(oracle)意义下不成立。作者构造了一个单一的经典 oracle,使得相对于该 oracle 不存在 one-way puzzle——即便允许验证者拥有无界计算能力;与此同时,一个 EFI pair 依然存在,并且对满足特定条件的任意区分者都保持不可区分。这个条件刻画得很细致:区分者可以全程只做经典查询、可以携带关于该 oracle 的任意 advice(预处理信息),但只允许在最后做一次叠加(superposition)查询。该 oracle 的设计有两部分作用:其一,它回答关于量子采样器输出概率分布的一切问题,从而彻底消除 one-way puzzle 存在的可能;其二,它隐藏一个 Haar 随机的半维子空间,用来承载仍然安全的 EFI pair。安全性证明的核心思路是把问题归约到通信复杂性:如果对手关于隐藏子空间的知识只能以经典查询答案的形式获得,那么对手就可以被嵌入到一个两方协议中,与真正持有该子空间信息的一方进行博弈并加以模拟,于是对手的优势不会超过 Vector-in-Subspace 问题(Klartag 与 Regev,STOC 2011)的最佳经典通信协议——而且这一结论与 oracle 具体计算什么都无关,具有强健的普适性。上述论证并不覆盖那一次叠加查询,作者转而使用随机矩阵理论的工具为其给出上界,从而完成整体证明。论文还指出同一攻击的一个副产品:在任何使用经典消息、且事先不共享纠缠的协议中,任意量子参与方都可以被经典模拟,因此相对于该 oracle 连"量子性证明"(proof of quantumness)也不存在。换言之,在经典输入与经典输出的任何任务上,量子多项式时间都不带来优势,而那两个量子态却始终不可区分。最后,作者就如何在后续工作中去掉对叠加查询的限制提出了若干猜想。

💡 推荐理由: 它直接触及量子密码学的"最小假设"边界:说明 one-way puzzle 并非 EFI pair 的等价刻画,并给出相对化下"经典 I/O 任务无量子优势"的强反例,会影响依赖这些原语的安全假设与量子性证明方案的可信度评估。

🎯 建议动作: 研究跟进:将其纳入密码学基础假设的文献跟踪,关注作者关于移除叠加查询限制的后续猜想与他人的验证/反驳工作。

排序因子: 影响边界/网络设备 (+5) | 来自 arXiv 其他板块 (+2) | Community 数据源 (+1) | LLM 评分加成 (+0.5)