量子科技中心_量科网

该团队研究了构建具有可扩展安全性的伪随机酉变换（PRU）问题，即安全参数可独立于维度（或输入比特长度）变化的酉族。目前尚不清楚能否构造可扩展的PRU。本文证明，如果通过当前分析PRU的主流范式能够构造可扩展的PRU，那么这将为Aaronson-Kuperberg酉合成问题提供正面解答——该问题是量子复杂性理论中长期悬而未决的问题，探讨实现任意酉变换能否有效归约为计算布尔函数。具体而言，该团队形式化了ROM-PRU的概念，即在随机预言机模型（ROM）中具有统计安全性的PRU。此前所有已知的密码学安全PRU构造均基于ROM-PRU构造。该团队证明了ROM-PRU、近似酉设计、酉群上的ε-网以及酉合成问题之间的全新关联。特别地，该团队证明任何酉合成算法（因此也包括任何ROM-PRU）必须使用输入长度为(2 - o(1)) log d比特的经典预言机，其中d为待实现酉变换的维度。这一界排除了现有文献中所有可扩展PRU的候选方案。这些关联共同表明，ROM-PRU为研究伪随机酉变换提供了富有成效的理想化模型。