量子科技中心_量科网

伪随机函数（PRF）是经典密码学中最基本的原语之一。另一方面，在量子密码学中，虽然PRF可能不存在，但其量子类似物可能存在，并且仍然能够支持许多应用，包括对称密钥加密（SKE）、消息认证码（MAC）、承诺、多方计算等。伪随机酉算子（PRU）[Ji, Liu, Song, Crypto 2018]、伪随机等距算子（PRI）[Ananth, Gulati, Kaleoglu, Lin, Eurocrypt 2024]以及伪随机函数类态生成器（PRFSG）[Ananth, Qian, Yuen, Crypto 2022]是PRF的主要量子类似物。PRU蕴含PRI，PRI蕴含PRFSG，但反向蕴含关系仍然未知。一个重要的问题是这些自然的PRF量子类似物是否等价。本文通过排除它们的黑盒构造来部分解决这个问题： 1. 不存在从PRFSG到使用O(log λ)辅助比特的PRU的黑盒构造。 2. 不存在从PRFSG到具有O(log λ)扩展的O(log λ)辅助比特PRI的黑盒构造。 3. 不存在从具有Ω(λ)扩展的PRI到具有O(log λ)扩展的O(log λ)辅助比特PRI的黑盒构造。 此处，O(log λ)辅助比特意味着生成算法最多使用O(log λ)个辅助量子比特。具有s(λ)扩展的PRI是指将λ个量子比特映射到λ+s(λ)个量子比特的PRI。为了排除上述黑盒构造，该团队构建了一个酉预言机来分离它们。对于这些分离，研究人员基于量子奇异值变换构建了一个敌手，这一方法具有独立的研究价值，并且应该对量子密码学中的其他预言机分离问题有用。