该论文研究量子密码学中伪随机态(PRS)构造的可实现性问题,属于量子计算复杂性理论中的黑盒分离(oracle separation)研究。已知结论表明,存在从量子安全单向函数(quantum-secure OWF)构造 PRS 生成器的黑盒构造方案,因此直觉上"存在量子安全 OWF"应当蕴含"存在 PRS"。本文作者 Minki Hhan、Changhun Oh、Vaughn Sohn 构造了一类量子 oracle,相对于该 oracle 同时满足两个条件:量子安全单向函数存在,但输出长度超过对数量级(superlogarithmic)的伪随机态(PRS)不存在。这表面上与已知的黑盒构造矛盾,作者指出关键在于对 oracle 的访问模型:他们的分离使用的是"经典可访问"(classical-accessible)的随机 oracle,即即便是量子算法也只能以经典方式查询该 oracle,无法进行量子叠加式(相干)查询。作者进一步证明,这一 PRS 的不可能性结论实际上适用于替换随机 oracle 的任意经典可访问经典 oracle,而保持 oracle 的另一组成部分不变,从而说明构造 PRS 必须依赖相干访问(coherent access)能力。此外,作者证明相对于同一组 oracle,对数量级输出长度的伪随机函数类态(PRFS)是存在的,由此给出"经典可访问的对数长度 PRFS"与"超对数长度 PRS"之间的 oracle 分离。综合这些结果,论文表明:任何完全黑盒的、把 PRS 输出长度从对数量级扩展到超对数长度的构造,都必须对底层的短 PRS 使用相干访问。该工作厘清了量子密码原语黑盒构造中访问模型(经典 vs 相干)这一此前被忽视的关键维度,对理解 PRS/PRFS 与 OWF 之间的相对关系、以及量子密码安全性归约的边界具有理论意义。
💡 推荐理由: 它指出黑盒归约中"经典访问 vs 相干访问"的差异会导致结论反转,提醒安全工程师:量子时代原语的安全性证明与构造假设不能想当然地沿用传统黑盒直觉,需重新审视依赖经典访问随机预言机的方案。
🎯 建议动作: 研究跟进